Accède gratuitement à cette vidéo pendant 7 jours
Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !
Fiche de cours
Colorier un graphe
On souhaite colorier un graphe avec un minimum de couleurs en ayant comme contrainte que deux sommets voisins aient des couleurs différentes. Le nombre minimal de couleurs est appelé le nombre chromatique.
On dispose du drapeau suivant que l'on souhaite colorier.
Pour se faire, on réécrit ce drapeau sous forme d'un graphe dont les sommets représentent les différentes zones et les arêtes traduisent que deux zones se touchent.
On écrit sur chaque sommet son degré.
Pour colorier le graphe, on utilise l'algorithme de Welsh-Powell.
On classe par ordre décroissant du degré les différents sommets sur la première ligne du tableau et par ordre alphabétique.
On associe au sommet de plus haut degré la première couleur $c_1$ puis on donne &agra
Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur
lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.