Sous-graphes d'un graphe coloré

[mkrzemin]

Bonjour,

Voici mon problème... J'ai un graphe G=(V, E). V représente l'ensemble des sommets, tandis que E désigne l'ensemble des arêtes. Les arêtes sont colorées, et plusieurs couleurs peuvent être affectées à la même arête. Je précise que ce graphe est quelconque.

1. Comment trouver le plus grand sous-graphe connecté qui ne contienne pas plus d'une fois la même couleur (Donc, il peut ne pas contenir une des couleurs du graphe original).

2. La même question, mais disons que je cherche l'ensemble des sous-graphes connectés qui contienne, disons au moins 70% du nombre de couleurs du graphe G.

Merci par avance pour votre aide! :happy3:

Mickaël

[Ezra]

Dans la coloration de graphes, le polynôme chromatique est le nombre de manières de colorier un graphe donné avec couleurs, avec deux sommets adjacents qui n'ont pas la même couleur, menant au nombre chromatique qui est le nombre minimum de couleurs. Revois donc une introduction aux graphes...

[mkrzemin]

Merci Ezra pour cette fantastique intervention qui ne me sert à rien! Je tiens à préciser que je ne suis pas mathématicien, mais biologiste, et je pense que n'importe quel mathématicien, en lisant la façon dont mon énnoncé est posé, aurait compris que je n'ai rien d'un mathématicien avec tout son langage sophistiqué, ou tout du moins que ma connaissance de la théorie des graphes est pour le moins restrainte. Aujourd'hui, si les sciences avancent beaucoup plus vite qu'à l'époque, c'est grâce aux collaborations étroites entre différentes personnes dont les compétences sont diverses et variées. Je pensais que les scientifiques (en général) avaient assez de maturité pour comprendre cette évidence pour le moins intuitive...

J'ai fait l'effort de transformer mon problème biologique en un problème mathématique afin de le transmettre à des personnes dont les compétences sont en mathématiques (et non en biologie) et afin d'accélérer la possible résolution de mon problème, qui lui, fera certainement avancer le monde. Je m'attendais donc à une réponse avec une explication claire et des mots simples. A la place de cela, j'ai le droit à une réponse qui m'envoie limite dans les roses, sans même me faire avancer, de la part de quelqu'un qui, loin des personnes humbles de ce monde, donne bien cette impression d'aimer étaler ses connaissances plutôt que de les transmettre proprement!

[Ezra]

Bonsoir,

j'ai juste fourni un éclairage utile sur les graphes : le reste est à la portée de chacun habile au thème!

[mkrzemin]

Là, on avance un peu. Mais le lien que tu m'as fourni n'explique que les notions de base des graphes. Or, comme tu dois t'en douter, avant de poster, j'ai quand même été me renseigner un minimum ce que sont les graphes, et les quelques algorithmes qui y sont associés.

Le point que je soulève là, c'est que je n'ai toujours pas une réponse claire à ma question. Ne serait-ce qu'un "Non, ce n'est pas possible" (avec une belle référence pour la démonstration) me serait aussi intéressant car ça m'éviterait de chercher plus loin.

En attendant, je me suis penché sur le problème en utilisant une méthode heuristique qui a déjà fait ses preuves. Cependant, ce type de méthode dépend des paramètres de base et ne donne pas forcément la meilleure réponse, surtout lorsque la taille du système devient très grande.

Une idée pour une autre approche ? :happy2:

[Ben314]

Salut,
Un petit coucou juste pour dire que
1) J'ai lu ton post (comme a mon avis beaucoup d'autres) mais je n'ai pas de réponse.
2) Mais je n'ai pas de grandes connaissance en théorie des graphes.
3) A mon avis, le problème est passablement ardu.
4) A mon avis (toujours), il n'a absolument rien à voir avec les problème classiques de "coloration de graphe" et de nombre chromatique : le seul lien entre les deux me semble l'utilisation du vocable "couleur" donc "l'éclairage utile" de Ezra me semble aussi légèrement... surfait... :triste: