1. L’histoire de la coloration des graphes
Les premiers résultats de coloration de graphes concernent presque exclusivement la coloration des cartes. En cherchant à mettre en couleurs une carte des comtés d’Angleterre, Francis Guthrie (mathématicien et botaniste sud-africain 1831 − 1899) postule en 1852 la conjecture des quatre couleurs : il remarqua en effet qu’il n’y avait besoin que de quatre couleurs pour que deux comtés ayant une frontière commune soient de couleurs différentes.
En 1879, Alfred Kempe (mathématicien anglais 1849 − 1922) publia ce qu’il prétendit en être une démonstration et pendant une décennie, on crut que le problème des quatre couleurs était résolu.
En 1890, Percy John Heawood (mathématicien anglais 1861 − 1955) fit remarquer que la démonstration de Kempe était fausse. Il montra quant à lui le théorème des cinq couleurs en reprenant des idées de Kempe.
De nombreux travaux ont été publiés lors du siècle suivant pour réduire le nombre de couleurs à quatre, jusqu’à la démonstration finale de Kenneth Appel (mathématicien américain né en 1932) et Wolfgang Haken (mathématicien allemand né en 1928). Il s’agit aussi de la première preuve majeure utilisant massivement l’ordinateur.
Outre le problème de cartes, la coloration des graphes intervient également pour les problème d’optimisation avec contraintes (planning, incompatibilités), dans les réseaux, la cryptographie. . . Aucune formule miracle permet de déterminer le nombre chromatique d’un graphe quelconque.
La plupart du temps, il faut se contenter d’un encadrement, autrement dit d’un minorant et d’un majorant du nombre chromatique.
Il existe plusieurs algorithmes de coloration, que nous allons voir plus en détail.
2. Algorithme glouton
Les algorithmes glouton sont couramment utilisés dans la résolution de problèmes.
Le principe de tels algorithmes consiste à choisir des solutions locales optimales d’un problème dans le but d’obtenir une solution optimale globale au problème.
Dans le cas du coloriage de graphe, cela va consister à colorier les sommets un par un avec la plus petite couleur possible ; l’ensemble des couleurs possibles étant donné par les couleurs de ses voisins. L’ordre dans lequel les sommets sont traités définit les différentes variantes de d’algorithme. Une méthode est de colorer les sommets par ordre de difficultés décroissantes.
Exemple :
| Entrée : liste ordonnée V des n sommets d’un graphe G liste ordonnée C de couleurs Pour i variant de 1 à n v = V[i] couleur = la première couleur de C non utilisée par les voisins de v colorier(v, couleur) Fin pour |
L’algorithme glouton le plus utilisé est l’algorithme de Welsh-Powel que nous allons étudier plus en profondeur dans une paragraphe dédié.
Néanmoins, il existe d’autres algorithmes reposant sur le principe glouton, moins connu, comme DSATUR et RLF, ayant des limites.
3. Algorithme DSATUR
DSATUR est un algorithme de coloration de graphes créé par Daniel Brélaz en 1979 à l’EPFL (École polytechnique fédérale de Lausanne).
Il s’agit d’un algorithme de coloration séquentiel par heuristique. DSAT est l’abréviation de dégré saturation.
Propriété :
On considère un graphe G=(V,E) simple connexe et non-orienté. Pour chaque sommet v de V, on calcule le degré de saturation DSAT(v) de la manière suivante:
- Si aucun voisin de x est colorié, alors DSAT(x) = le degré de x
- Sinon, DSAT(x) = le nombre de couleurs différentes utilisées dans le voisinage de x
L’algorithme DSATUR est un algorithme de coloration séquentiel, au sens ou il colorie un seul sommet à la fois et tel que:
- Au départ le graphe n’est pas colorié
- On colorie un sommet non-déjà colorié
- On stoppe DSATUR quand tous les sommets de G sont coloriés.
Méthode d’application de l’algorithme :
- Ordonner les sommets par ordre décroissant de degré.
- Colorer un sommet de degré maximum avec la couleur 1.
- Choisir un sommet non coloré avec DSAT maximum. Si conflit choisir celui avec degré maximum.
- Colorer ce sommet par la plus petite couleur possible
- Si tous les sommets sont colorés alors stop. Sinon aller en 3.
Exemple :
Exemple :
Soit les couleurs hiérarchisées :
On prend le sommet de plus haut degré, soit le sommet 1.
On lui attribue la couleur minimale, soit C1 :
Puis, on regarde plus un voisin du sommet 1 étant de plus haut degré: Nous allons prendre le sommet 6.
Il faut lui attribuer une couleur minimale, mais différente de la couleur du sommet : On prend C2 :
On fait la même chose pour le voisin du sommet étant de plus haut degré : le sommet 5. On lui attribue une couleur minimale différente de celle de ses voisins : la couleur C3 :
On réédite l’opération pour tous les autres sommets, puis on obtient :
4. Algorithme RLF
L’algorithme RLF construit les classes de couleur les unes après les autres. Pour chaque classe, le premier sommet à en faire partie est choisi au hasard parmi ceux ayant un nombre maximum de sommets adjacents non colorées. La classe est alors complétée de la manière suivante. Soit W ⊆ U l’ensemble des sommets non colorées qui ne peuvent plus faire partie de la classe en construction (car ils sont adjacents à au moins un sommet de cette classe).
Le prochain sommet introduit dans la classe est un sommet faisant partie de U mais pas de W , et ayant un nombre maximum de sommets adjacents dans W . Lorsque U =W , on passe a la classe de couleur suivante.
Cet Algorithme est basé sur la méthode DSATUR
Les différentes étapes de l’algorithme :
- Choisir un sommet x de degré maximum;
- Choisir un voisin de ce sommet y tel que vc(x,y) soit maximum;
- Contracter y en x;
- Répéter 2 et 3 jusqu’à ce que x soit voisin à tous les autres sommet;
- Enlever le sommet x et reprendre à l’étape 1;
Exemple :
Tout d’abord, il faut repérer le sommet de plus au degré : c’est le sommet 1.
Nous allons donc lui attribuer une couleur, et « éliminer » tous ses sommets adjacents. Ceux qui ne le sont pas prendront la couleur du sommet 1 :
Puis, nous allons étudier un sous-graphe où les deux premiers sommets coloriés sont exclus, et choisir un nouveau sommet (le sommet 5) et lui attribuer une autre couleur :
On remarque qu’il faut aussi exclure les sommets adjacents de l’autre sommet (sommet 3) de même couleur que notre sommet choisi.
On réédite à nouveau les étapes ci-dessus, pour obtenir le graphe suivant (il ne reste plus que deux sommets indépendants) :
M6 Coloration des graphes 