Bonjour, j'ai un devoir de spé demain mais je ne comprend pas un point sur la coloration des graphe.
Si j'ai bien compris, (mais en fait, c'est ici que ça pose problème), le but de la coloration est de trouver un maximum de sous graphe stables non??

Avec l'algorithme de Welsh et Powel, une fois que l'on a classé les sommet par ordre décroissant des degrés, on prend le premier sommet et on colorie tous les sommets qui ne sont pas adjacent à ce premier sommet. Mais que faire lorsque deux sommets qui ne sont pas adjacent à ce premier sommet le sont entre eux?? Ma prof nous a dit que ça ne changeait rien et qu'on doit les colorier de la mm couleur, mais du coups, deux sommet adjacent n'ont pas forcément deux couleurs différentes... Moralité, je ne comprend pas l'intérêt de colorier les sommet, car les couleurs ne donnent pas forcément un sous graphe stable, donc je ne comprend pas l'intérêt de ces couleurs...

Si quelqu'un peu m'expliquer, ça serait très gentil, car j'en aurais besoin demain matin...