Coloration de graphe

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Une coloration du graphe de Petersen avec 3 couleurs.

En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. Ce problème peut être généralisé 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'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation.

Historique[modifier | modifier le code]

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 Rowan 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)[modifier | modifier le code]

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 et pour désigner le nombre chromatique de G[3]. De nos jours, la plupart des ouvrages adoptent le symbole (tandis que 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).

Propriétés et conjectures[modifier | modifier le code]

Nombre chromatique et le degré maximal[modifier | modifier le code]

Article détaillé : Théorème de Brooks.

Le théorème de Brooks établit que l'on peut colorer un graphe connexe en utilisant au maximum Δ couleurs, où Δ est le degré maximal du graphe, à l'exception des cas du graphe complet et du graphe cycle de longueur impaire, où il faut Δ + 1 couleurs.

Le fait que le graphe soit colorable avec au plus Δ + 1 couleurs se montre très facilement. En effet, il suffit de colorer les sommets un à un dans n'importe quel ordre : à chaque fois qu'on colore un sommet, il faut choisir une couleur différente de toutes celles qui ont déjà été utilisées pour les voisins de ce sommet qui ont déjà été colorés ; comme un sommet possède au plus Δ voisins, Δ + 1 couleurs sont toujours suffisantes.

Le mérite du théorème de Brooks est donc de réduire ce nombre de couleurs nécessaires à Δ pour la plupart des graphes.

Conjecture de Hadwiger[modifier | modifier le code]

Article détaillé : 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. La conjecture de Hadwiger est alors que :

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[modifier | modifier le code]

Le graphe de Golomb est distance-unité et nécessite 4 couleurs pour colorer ses sommets.
Article détaillé : 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 colorer tout graphe distance-unité ?

D'après Tommy Jensen et Bjarne Toft[5], le problème fut posé pour la première fois par Edward 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 5 et 7. La meilleure borne inférieure connue a longtemps été 4, avant d'être améliorée en 2018 par Aubrey de Grey, qui a construit un graphe distance-unité nécessitant 5 couleurs[8]. 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[modifier | modifier le code]

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

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.

Bornes inférieures de [modifier | modifier le code]

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 (où 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 : calculable en temps polynomial, et vérifiant le théorème du sandwich suivant (avec désignant le graphe complémentaire) : 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 à , 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).

Exemples d'application[modifier | modifier le code]

Télécommunications[modifier | modifier le code]

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'attribution 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.

Problèmes d'incompatibilité[modifier | modifier le code]

  • Organiser un examen suivant les matières que doit passer chaque étudiant. Comment mettre en parallèle plusieurs épreuves sans léser un candidat ?
  • Optimiser l'utilisation des machines de travail. Comment mettre en parallèle des fabrications utilisant plusieurs machines ?
  • Comment faire cohabiter des personnes ou des animaux en tenant compte de leur incompatibilité ?
  • La résolution du Sudoku peut se ramener à un problème de coloration de graphe.

Propriétés algorithmiques[modifier | modifier le code]

Problèmes algorithmiques[modifier | modifier le code]

Deux problèmes algorithmiques de coloration sont les suivants[10] :

  • problème de décision : étant donné G, un graphe, et k un entier, existe-t-il une coloration valide de G utilisant k couleurs ?
  • problème d'optimisation : étant donné G, quel est son nombre chromatique ?

NP-complétude[modifier | modifier le code]

Pour tout k supérieur à 3, le problème de coloriage avec k couleurs est NP-complet.

Déterminer le nombre chromatique d'un graphe est un problème NP-difficile dans le cas général. Ainsi, à moins que P=NP, il n'existe pas d'algorithme polynomial déterminant le nombre chromatique d'un graphe arbitraire. Ce problème est un problème d'optimisation posant la question suivante : soit G un graphe donné, quel est le nombre minimum de couleurs nécessaires pour avoir une coloration valide de G

Le problème d'approximation associé est lui aussi NP-complet, quel que soit le rapport d'approximation recherché[11]. Autrement dit le problème n'est pas dans la classe APX.

Cas polynomiaux[modifier | modifier le code]

Il existe des algorithmes polynomiaux si on se restreint à des classes de graphes.

Algorithmes[modifier | modifier le code]

Dans cette section, on cite quelques algorithmes (de complexité exponentielle dans le cas général) citons l'algorithme de Zykov[réf. nécessaire] (par la méthode de Branch and Bound).

Heuristiques[modifier | modifier le code]

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[Par qui ?][réf. nécessaire] des méthodes approchées générales : méta-heuristique (recuit simulé, recherche tabou), ou encore algorithme génétique.

Algorithme de Welsh et Powell[modifier | modifier le code]

  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 coloré de la liste.
  8. Répéter les opérations 3 à 7.
  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, son nombre chromatique est 2 (si n est pair) 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[modifier | modifier le code]

Article détaillé : DSATUR.

DSATUR est une heuristique qui consiste à colorer les sommets les uns après les autres, en s'appuyant sur un tri préalable des sommets. Une priorité est donnée aux sommets de grand degré, ainsi que les sommets dont les voisins ont déjà obtenu le plus couleurs différentes.

Algorithme glouton[modifier | modifier le code]

On assimile les couleurs à des entiers naturels dans les algorithmes qui suivent. On se donne un graphe .

Pour tout  :

  1. On regarde l'ensemble des couleurs déjà attribuées aux voisins de
  2. On en déduit le plus petit entier naturel qui n'appartient pas à cet ensemble.
  3. On attribue cette couleur à

Ainsi, on obtient un coloriage de , qui utilise au plus couleurs, avec le degré du graphe

Correction de l'algorithme[modifier | modifier le code]

L'algorithme glouton renvoie bien un coloriage. En effet, tous les sommets sont coloriés. Si deux sommets et sont voisins, on peut supposer que est traité avant . L'algorithme attribue la couleur à , puis quand est traité, l'algorithme choisit une couleur qui n'appartient pas à la liste de couleurs déjà utilisées pour les voisins de . Ainsi est différente de .

La coloration utilise au plus couleurs. En effet, si ce n'était pas le cas, on aurait un sommet qui aurait une couleur supérieure strictement à .

Donc ses voisins utiliseraient déjà couleurs différentes. Or, ce sommet a au plus voisins, ce qui serait absurde.

Algorithme de 2-coloriage[modifier | modifier le code]

On considère un graphe 2-coloriable.

Pour chaque composante connexe de on se donne un sommet on lui attribue la couleur et on attribue la couleur à ses voisins. Pour chacun de ses voisins, on attribue la couleur à ses voisins non coloriés, et ainsi de suite : on réalise ainsi un parcours en largeur du graphe, en coloriant les sommets rencontrés de la façon énoncée précédemment.

Correction de l'algorithme[modifier | modifier le code]

L'algorithme de 2-coloriage renvoie bien un coloriage si le graphe en entrée est 2-coloriable. En effet, si on prend 2 sommets voisins, l'un des sommets a été parcouru le premier. Le deuxième sommet est donc colorié de l'autre couleur par l'algorithme, et sa couleur n'est pas modifiée par la suite. De plus, l'algorithme effectue un parcours en largeur, donc tous les sommets sont coloriés.

Algorithme de Wigderson[modifier | modifier le code]

Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit un tel graphe. On note le nombre de sommets de

  1. On prend comme couleur initiale
  2. Pour tout non déjà colorié et avec au moins voisins non coloriés : on considère le sous graphe induit par l'ensemble des voisins de pas encore coloriés, et on le 2-colorie avec les couleurs et On ajoute à le nombre de couleurs utilisées.
  3. Avec l'algorithme glouton, on colorie le reste des sommets avec des couleurs plus grandes que

La complexité de l'algorithme de Wigderson est polynomiale en et détermine un coloriage de qui utilise couleurs[12].

Correction de l'algorithme de Wigderson[modifier | modifier le code]

L'algorithme de Wigderson renvoie bien un coloriage, car l'algorithme glouton et l'algorithme de 2-coloriage sont corrects, et que les sous-graphes considérés dans l'algorithme sont coloriés avec des ensembles de couleur disjoints.

Si on note le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins sommets. On a donc :

, i.e .

Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus . Ensuite, le degré du sous-graphe induit par les sommets non coloriés à la fin du point 2 est inférieur ou égal à . L'algorithme glouton utilise donc au plus couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus , il est donc en .

Exemple d'application de l'algorithme[modifier | modifier le code]

Le graphe suivant est 3-coloriable :

Graphe 3-coloriable

Application de l'étape 2[modifier | modifier le code]

Le sommet a 4 voisins non coloriés : on les 2-colorie, puis on fait de même pour les 4 voisins non coloriés du sommet .

Après ces opérations, il n'y a plus de sommet non colorié avec au moins voisins non coloriés.

Étape 2 de l'algorithme de Wigderson
Application de l'étape 3[modifier | modifier le code]

On applique l'algorithme glouton aux sommets restants.

Étape 3 de l'algorithme de Wigderson

Calcul distribué synchrone[modifier | modifier le code]

La coloration est un problème classique de calcul distribué synchrone[13]. Un résultat notable[14] est la borne inférieure de Nati Linial : il faut au moins étapes pour faire une 3 coloration d'un cycle de longueur (même pour un algorithme utilisant de l’aléa), où est le logarithme itéré[15].

Références[modifier | modifier le code]

  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, « Hadwiger's conjecture for -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, , p. 150–152
  6. (en) Martin Gardner, « Mathematical Games », Scientific American, vol. 203, no 4,‎ , p. 180
  7. (en) Hugo Hadwiger, « Überdeckung des euklidischen Raumes durch kongruente Mengen », Portugal. Math. (en), vol. 4,‎ , p. 238–242
  8. Aubrey D. N. J. de Grey, « The chromatic number of the plane is at least 5 », arXiv:1804.02385 [math],‎ (lire en ligne)
  9. (en) Branko Grünbaum, « A Problem in Graph Coloring- », Amer. Math. Monthly, vol. 77,‎ , p. 1088-1092
  10. (en) « Vertex Coloring » (consulté le 12 mars 2015)
  11. David Zuckerman, « Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number », Theory of Computing, vol. 3, no 1,‎ , p. 103-128
  12. (en) « Improving the performance guarantee for approximate graph coloring », sur https://dl.acm.org/, (consulté le 11 décembre 2018)
  13. Un ouvrage sur le sujet : Leonid Barenboim et Michael Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments, Morgan & Claypool Publishers, coll. « Synthesis Lectures on Distributed Computing Theory », (ISBN 9781627050180)
  14. Il a valu le prix Dijkstra à son auteur.
  15. L'article original : (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1,‎ , p. 193-201.

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]