Coloration de graphe Article, Signification, Explication
| Table of contents |
|
2 Méthodes
2.1 Encadrement du nombre chromatique
3 Applications2.2 Algorithme de Welsh et Powell 2.3 Partition en sous-graphes stables |
Il existe deux façons de colorer un graphe.
Si D est le degré maximal du graphe, c'est-à -dire le plus grand degré parmi les degrés des sommets, alors le nombre chromatique est inférieur ou égal à 1 + D.
Le nombre chromatique est aussi supérieur ou égal à l'ordre du plus grand sous-graphe complet du graphe.
1 Repérer le degré de chaque sommet.
2 Ranger les sommets par ordre de degrés décroissants. (dans certains cas plusieurs possibilités)
3 Attribuer au premier sommet (A) de la liste une couleur.
4 Suivre la liste en attribuant la même couleur au premier sommet sommet (B) qui ne soit pas adjacent à (A).
5 Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
6 Continuer jusqu'Ã ce que la liste soit finie.
7 Prendre une deuxième couleur pour le premier sommet (D) non encore colorié de la liste.
8 Répéter les operations 4 à 6.
9 Continuer jusqu'à avoir colorié tous les sommets.
Cette méthode n'aboutit pas forcément à une coloration minimale. Il faut donc observer si on peut faire mieux (c'est-à -dire avec moins de couleurs).
Un sous-graphe stable est un sous-graphe dont les sommets ne sont pas adjacents. Ses sommets peuvent donc être colorés de la même couleur. Le but est de trouver un nombre minimal de sous-graphes stables pour utiliser le moins de couleurs possible.
En 1976, deux américains Kenneth Appel et Wolfgang Haken affirment avoir démontré le théorème des quatre couleurs. Leur démonstration partage la communauté scientifique : pour la première fois, en effet, la démonstration exige l'usage de l'ordinateur pour étudier les 1200 cas critiques. Le problème de la validation du théorème se trouve alors déplacé vers le problème de la validation :
Définition
Méthodes
Encadrement du nombre chromatique
Algorithme de Welsh et Powell
Partition en sous-graphes stables
Applications
Le théorème des quatre couleurs
On ne trouvait pas de contre-exemple de cette affirmation empirique. Restait à la démontrer.
Une démonstration publiée en 1879 par Kempe, s'est révélée comporter une erreur. Il a fallu attendre près d'un siècle de recherche pour voir aboutir une démonstration valide.
Depuis 1976, l'algorithme d'Appel et Haken a été repris et simplifié par d'autres chercheurs. D'autres programmes informatiques, écrits de façon indépendante du premier, aboutissent au même résultat.