Coloration de graphe

En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l'utilisation d'un nombre minimal de couleurs, dit nombre chromatique. Ce problème peut être complexifié en ne cherchant plus une mais plusieurs couleurs par sommets et en associant des coûts à chacune des couleurs. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'allocation de fréquences (en) dans les télécommunications ou la conception de puces électroniques.

Historique

Article détaillé : Théorème des quatre couleurs.

Les premiers résultats de coloration de graphe concernent presque exclusivement les graphes planaires : il s'agissait alors de colorier des cartes. En cherchant à mettre en couleurs une carte des comtés d'Angleterre, Francis Guthrie postula 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. Le frère de Guthrie transmit la question à son professeur de mathématiques, Auguste de Morgan de l'University College de Londres. De Morgan mentionna ce problème dans une lettre adressée à William Hamilton en 1852. Arthur Cayley évoqua cette question lors d'un colloque de la London Mathematical Society en 1879. La même année, Alfred Kempe 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. Kempe fut élu membre de la Royal Society et devint ensuite président de la London Mathematical Society^[1].

En 1890, Percy John Heawood fit remarquer que la démonstration de Kempe était fausse. Il montra quant à lui le théorème des cinq couleurs (en) 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 et Wolfgang Haken. La preuve réutilisait les idées d'Heawood et Kempe et pratiquement pas les développements ultérieurs^[2]. Il s'agit aussi de la première preuve majeure utilisant massivement l'ordinateur.

Définition (nombre chromatique)

Une coloration du graphe de Petersen avec 3 couleurs.

La notion de coloration n'est définie que pour les graphes sans boucle, et la multiplicité des arêtes ne joue aucun rôle. Donc, soit G un graphe simple (sans boucle ni arête multiple), un stable de G est un sous-ensemble de sommets deux-à-deux non-adjacents, et une coloration de G est une partition de son ensemble de sommets en stables.

La définition originale de la coloration est la suivante:

« une coloration de G est une fonction associant à tout sommet de G une couleur, généralement un élément de l'ensemble d'indices des couleurs {1,2,...,n}, telle que deux sommets adjacents n'ont pas la même couleur (où n est le nombre de sommets du graphe). »

On lui préfère généralement la définition que nous avons donnée en premier, car, pour la plupart des questions liées au concept de coloration, on ne souhaite pas différencier les colorations qui ne sont distinctes qu'à permutation des indices de couleurs près (ce qui est le cas pour le problème central lié à la coloration, celui de déterminer le nombre minimum de couleur dans une coloration de G, c'est-à-dire son nombre chromatique). Par-exemple, si G est constitué de deux sommets u et v et d'une arête les reliant, alors les deux fonctions f et g avec f(u)=1, f(v)=2, et g(u)=2, g(v)=1 sont des colorations différentes pour la deuxième définition mais équivalentes pour la première.

Dans ses différents ouvrages (en français ou en anglais), Berge a utilisé les deux notations γ(G) et χ(G) pour désigner le nombre chromatique de G^[3]. De nos jours, la plupart des ouvrages adoptent le symbole χ(G) (tandis que γ(G) concerne plutôt un invariant lié au concept de cycle).

Enfin, dans certains contextes, on parle aussi de coloration pour désigner une fonction associant une couleur aux sommets d'un graphe mais satisfaisant d'autres propriétés (e.g. dans le contexte de l'optimisation de la génération de code sur une machine comportant un grand nombre de registres).

Conjectures, questions ouvertes

Conjecture de Hadwiger

La plus célèbre des conjectures est sans doute celle de Hadwiger en 1943. Le nombre de Hadwiger d'un graphe G est égal au plus grand entier k tel que G ait un mineur isomorphe au graphe complet à k sommets. Pour tout graphe sans boucle G, le nombre chromatique de G est inférieur ou égal au nombre d'Hadwiger de G. La conjecture de Hadwiger est démontrée pour les graphes dont le nombre de Hadwiger est au plus 6, la preuve est basée sur le théorème des quatre couleurs^[4].

Problème de Hadwiger–Nelson

Déterminer le nombre chromatique du graphe dont les sommets sont les points du plan (euclidien) et tel que deux sommets sont adjacents si la distance qui les sépare vaut 1.

Une autre formulation est : Quel est le nombre minimal de couleurs qu'il faut pour pouvoir colorier tout graphe distance-unité ?

D'après Tommy Jensen et Bjarne Toft^[5], le problème fut posé pour la première fois par E. Nelson en 1950 et publié pour la première fois par Gardner en 1960^[6]. Hugo Hadwiger avait cependant publié un résultat en rapport avec le problème dès 1945^[7].

Actuellement, tout ce qu'on l'on peut dire c'est que ce nombre est compris entre 4 et 7. La borne inférieure s'obtient en remarquant que les sommets d'un triangle équilatéral de côté 1 sont nécessairement de trois couleurs différentes. Ainsi, si l'on pouvait colorier le plan avec uniquement 3 couleurs, on peut prouver en collant deux triangles équilatéraux de côté 1 par un côté commun que deux points distants de racine de 3 sont forcément de la même couleur ; on parvient alors à une contradiction en considérant un triangle isocèle dont deux côtés sont de longueur racine de 3 et un côté de longueur 1. La borne supérieure s'obtient à partir d'un pavage hexagonal du plan. Certains résultats concernant cette conjecture dépendent de l'axiome du choix.

Conjecture de Grünbaum

« Pour tout m>1 et n>2 il existe un graphe n-régulier de nombre chromatique m et de maille au moins n^[8]. »

Le résultat est trivial pour n=2 et m=2,3 mais pour m>3 seuls peu de graphes illustrant la conjecture sont connus. Le graphe de Chvátal est l'un d'eux.

Un exemple d'application : l'allocation de fréquences

Bien sûr, les applications concernent les graphes finis. Certains réseaux de télécommunication sont composés d'émetteurs émettant chacun sur une fréquence particulière. Lorsque deux émetteurs sont trop proches on ne peut leur allouer la même fréquence à cause des interférences (sauf si éventuellement une montagne les sépare).

On associe un graphe au réseau—chaque sommet est un émetteur et chaque arête spécifie que l'on ne veut pas allouer la même fréquence aux deux émetteurs correspondant à ses deux extrémités—et ainsi déterminer une allocation réalisable avec un minimum de fréquences (dont la licence d'exploitation peut entrainer un coût important). Ce problème est un cas particulier du problème de la coloration de graphe.

Précisons que les contraintes technologiques dépendant du relief géographique, on ne peut pas faire l'hypothèse qu'un graphe obtenu à partir des réseaux de télécommunications soit un graphe de disques.

Pour certains problèmes d'allocation de fréquences, on peut être amené à allouer plusieurs fréquences à un même émetteur; à imposer un écart minimum entre les fréquences allouées à deux émetteurs proches (et non plus seulement qu'elles soient distinctes); à imposer d'allouer à un émetteur une fréquence choisie parmi seulement un sous-ensemble des fréquences disponibles… La coloration apparaît alors comme un cas particulier de ces variantes.

Aspects algorithmiques généraux

Déterminer le nombre chromatique d'un graphe est un problème NP-complet dans le cas général. En fait, on peut en dire plus si l'on considère le problème de décision suivant : soit G un graphe et k un entier, peut-on colorer G avec moins de k couleurs ?

Si k=2 il s'agit de décider si G est biparti ou non. Ceci est facile car ces graphes sont caractérisés par la non-présence d'une structure interdite : celle de cycle impair. Par contre pour tout k fixé supérieur à 3 le problème devient NP-complet.

Ainsi, à moins que P=NP, il n'existe pas d'algorithme polynomial déterminant le nombre chromatique d'un graphe arbitraire. Pour certaines classes de graphes par contre de tels algorithmes existent. C'est notamment le cas pour les graphes triangulés dans lesquels le problème se résout en temps linéaire. Un résultat nettement plus difficile (de László Lovász et al.) établit (en développant toute une théorie) que l'on peut déterminer en temps polynomial le nombre chromatique de tout graphe parfait (pour une définition voir Théorème des graphes parfaits).

Parmi les algorithmes exacts (donc de complexité exponentielle dans le cas général) citons l'algorithme de Zykov (par la méthode de Branch and Bound). L'importance du problème a donné lieu à l'élaboration de nombreuses heuristiques spécifiques au problème, spécialement des algorithmes séquentiels de coloration sommet par sommet (DSATUR, cosine, maya, etc.). Elle a aussi suscité de nombreuses expérimentations des méthodes approchées générales : méta-heuristique (recuit simulé, recherche tabou), ou encore algorithme génétique.

Heuristiques

Algorithme de Welsh et Powell

Voici un exemple qui, en plus, fournit une preuve constructive du théorème de Vizing, qui établit la formule : $\chi(G) \le \Delta(G)+1$, où Δ(G) représente le degré maximum d'un sommet de G (le degré d'un sommet étant le nombre des arêtes qui lui sont incidentes). Pour s'en convaincre, appliquons l'algorithme suivant (Welsh et Powell) :

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 (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 opérations 4 à 6.
9. Continuer jusqu'à avoir coloré tous les sommets.

Remarquons que cette méthode peut aboutir à la pire des colorations possibles, par-exemple si le graphe G a la structure de couronne à n sommets (voir http://en.wikipedia.org/wiki/Crown_graph), son nombre chromatique est 2 tandis que Welsh-Powell donne dans certains cas (selon l'ordre dans lequel sont rangés les sommets) une coloration utilisant n/2 couleurs ! L'heuristique DSATUR permet d'éviter ce problème et donne une coloration moins mauvaise dans le pire cas.

DSATUR

Article détaillé : DSATUR.

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 v n'est coloré alors
       DSAT(v)=degré(v) 
   sinon
       DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v 

L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens où il colorie un seul sommet à la fois et tel que:

   au départ le graphe n'est pas coloré 
   on colorie un sommet non déjà coloré 
   on stoppe DSATUR quand tous les sommets de G sont colorés. 

Dans un premier temps on voit bien d'une part que la preuve de terminaison est triviale et d'autre part que l'algorithme est séquentiel. Dans le détail l'algorithme est le suivant :

     1. Ordonner les sommets par ordre décroissant de degré.
     2. Colorer un des sommets de degré maximum avec la couleur 1.
     3. Choisir un sommet non coloré avec DSAT maximum. Si un sommet voisin a la même couleur (cad conflit), choisir un sommet parmi ceux de degré maximum.
     4. Colorer ce sommet par la plus petite couleur possible
     5. Si tous les sommets sont colorés alors stop. Sinon aller en 3.

Bornes inférieures de χ(G)

Si un graphe "G" contient une clique de taille "k" (un ensemble de "k" sommets reliés deux à deux), ces sommets requièrent "k" couleurs distinctes, ce qui implique que $\omega(G) \le \chi(G)$ (où ω(G) désigne la taille de la plus grande clique de "G"). Cette borne inférieure est toutefois elle aussi NP-difficile à obtenir. En 1979, un article de László Lovász a introduit une quantité associée à chaque graphe : θ(G) calculable en temps polynomial, et vérifiant le théorème du sandwich suivant (avec $\overline{G}$ désignant le graphe complémentaire) : $\omega(G) \le \theta(\overline{G}) \le \chi(G).$ L'égalité a lieu pour les graphes parfaits, entre autres, ce qui permet de calculer leur nombre chromatique.

Une autre borne inférieure est le nombre chromatique fractionnaire, toujours supérieur à $\theta(\overline{G})$, NP-difficile à calculer par génération de colonnes (c'est un programme linéaire dont les variables sont indexées par les stables du graphe, en nombre exponentiel).

Références

1. ↑ (en) M. Kubale, History of graph coloring, in Kubale 2004
2. ↑ van Lint et Wilson 2001, Chap. 33
3. ↑ Claude Berge, Hypergraphes. Combinatoires des ensembles finis, Bordas, 1987
4. ↑ (en) Neil Robertson, Paul Seymour et Robin Thomas (de), « Hadwiger's conjecture for K₆-free graphs », dans Combinatorica, 14, 1993, 279-361
5. ↑ (en) Tommy R. Jensen et Bjarne Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995, p. 150–152 
6. ↑ (en) Martin Gardner, Mathematical Games, vol. 203/4, 1960, p. 180 
7. ↑ (de) Hugo Hadwiger, « Überdeckung des euklidischen Raumes durch kongruente Mengen », dans Portugal. Math., vol. 4, 1945, p. 238–242 
8. ↑ (en) Branko Grünbaum (en), « A Problem in Graph Coloring », dans Amer. Math. Monthly 77, 1970, 1088-1092

Bibliographie

• (en) M. Kubale, Graph Colorings, American Mathematical Society, 2004 (ISBN 0-8218-3458-4) 
• (en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001 (ISBN 0-521-80340-3) 

Voir aussi

• Coloration des arêtes d'un graphe
• Théorème des quatre couleurs