Coloration de graphe

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. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. 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

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 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)

La notion de coloration n'est définie que pour les graphes simples sans boucles et sans arêtes multiples.

Etant donné un graphe simple G = (S, A), un stable de G est un sous-ensemble de S dont les sommets sont deux-à-deux non-adjacents, et une k-coloration de G est une partition de S en k stables.

Une k-coloration de G est une fonction c de S vers {1, 2, … , k}, telle que pour tout couple de sommets adjacents u et v de S, c(u) ≠ c(v).

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

Propriétés et conjectures

Nombre chromatique et le degré maximal

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.

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.

Conjecture de Hadwiger

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 de 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

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].

Ce nombre chromatique 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

« 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 ou 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 χ(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)\leq \chi (G)$ (où $\omega (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 : $\theta (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)\leq \theta ({\overline {G}})\leq \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).

Exemples d'application

Télécommunications

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 entraîner un coût important). Ce problème est un cas particulier du problème de la coloration de graphe.

Précisons que les contraintes techniques 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é

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

Problèmes algorithmiques

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

Pour tout k strictement supérieur à 2, 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, et ce, quel que soit le rapport d'approximation recherché^[11]. Autrement dit, le problème n'est pas dans la classe APX.

Cas polynomiaux

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

Si k est fixé à 2, le problème de décision consiste à décider si G est biparti ou non. Ceci est faisable en vérifiant la non-présence de cycle impair avec un parcours en largeur^{[réf. nécessaire]}.
Pour les graphes d'intervalles, on résout le problème en temps linéaire avec un algorithme glouton^[12].
Plus généralement, les graphes triangulés (les graphes d'intervalles en sont) le problème se résout en temps linéaire ^{[réf. nécessaire]}.
Les graphes triangulés sont des graphes parfaits. 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) ^{[réf. nécessaire]}.
pour les graphes planaires, le théorème des quatre couleurs permet de décider l'existence d'une k-coloration dès que k est plus grand que 4 (en temps constant car il en existe toujours une). De plus, on sait trouver une telle 4-coloration en temps quadratique^{[réf. nécessaire]}. Par contre, le problème reste NP-complet pour k = 3^{[réf. nécessaire]}.

Algorithmes

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

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

Repérer le degré de chaque sommet.
Ranger les sommets par ordre de degrés décroissants (dans certains cas plusieurs possibilités).
Attribuer au premier sommet (A) de la liste une couleur.
Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
Continuer jusqu'à ce que la liste soit finie.
Prendre une deuxième couleur pour le premier sommet (D) non encore coloré de la liste.
Répéter les opérations 3 à 7.
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

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

On assimile les couleurs à des entiers naturels dans les algorithmes qui suivent. On se donne un graphe $G=(S,A)$ .

Pour tout $s\in S$ :

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

Ainsi, on obtient un coloriage de G, qui utilise au plus Δ(G) + 1 couleurs, avec Δ(G) le degré du graphe G.

Correction de l'algorithme

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

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

Donc ses voisins utiliseraient déjà Δ(G) + 1 couleurs différentes. Or, ce sommet a au plus Δ(G) voisins, ce qui serait absurde.

Algorithme de 2-coloriage

On considère un graphe $G=(S,A)$ 2-coloriable.

Pour chaque composante connexe de $G,$ on se donne un sommet $s\in S,$ on lui attribue la couleur $0$ et on attribue la couleur $1$ à ses voisins. Pour chacun de ses voisins, on attribue la couleur $0$ à 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

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

L'algorithme de Wigderson est un algorithme de complexité en temps polynomiale, qui colore avec $O({\sqrt {n}})$ couleurs les graphes 3-coloriables.

Algorithme distribué

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 $\Omega (\log ^{*}n)$ étapes pour faire une 3 coloration d'un cycle de longueur $n$ (même pour un algorithme utilisant de l’aléa), où $\log ^{*}$ est le logarithme itéré^[15].

Notes et références

↑ (en) M. Kubale (trad. du polonais), Graph Colorings, Providence (R.I.), AMS, 2004, 208 p. (ISBN 0-8218-3458-4), « History of graph coloring ».
↑ (en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001, 616 p. (ISBN 0-521-80340-3), chap. 33.
↑ Claude Berge, Hypergraphes. Combinatoires des ensembles finis, Bordas, 1987.
↑ (en) Neil Robertson, Paul Seymour et Robin Thomas, « Hadwiger's conjecture for $K_{6}$ -free graphs », Combinatorica, vol. 14,‎ 1993, p. 279-361 (lire en ligne).
↑ (en) Tommy R. Jensen et Bjarne Toft, Graph Coloring Problems, Wiley-Interscience, coll. « Series in Discrete Mathematics and Optimization », 1995, p. 150–152.
↑ (en) Martin Gardner, « Mathematical Games », Scientific American, vol. 203, n^o 4,‎ 1960, p. 180
↑ (en) Hugo Hadwiger, « Überdeckung des euklidischen Raumes durch kongruente Mengen », Portugal. Math. (en), vol. 4,‎ 1945, p. 238–242.
↑ (en) Aubrey D. N. J. de Grey, « The chromatic number of the plane is at least 5 », arXiv,‎ 2018 (arXiv 1804.02385).
↑ (en) Branko Grünbaum, « A Problem in Graph Coloring », Amer. Math. Monthly, vol. 77, n^o 10,‎ 1970, p. 1088-1092.
↑ (en) « Vertex Coloring » (consulté le 12 mars 2015).
↑ David Zuckerman, « Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number », Theory of Computing, vol. 3, n^o 1,‎ 2007, p. 103-128.
↑ Souhila YAHIA, Algorithmes Gloutons Optimaux pour les graphes d’indifférence, MOULOUD MAMMERI, TIZI-OUZOU (Algérie), 19 octobre 2011, 50 p. (lire en ligne), p. 11-19
↑ 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 », 2013 (ISBN 978-1-62705-018-0).
↑ Il a valu le prix Dijkstra à son auteur.
↑ L'article original : (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, n^o 1,‎ 1992, p. 193-201.

Voir aussi

Articles connexes

Lien externe

« Sujet Informatique A du concours X-ENS MPI 2018 »

[1] (en) M. Kubale (trad. du polonais), Graph Colorings, Providence (R.I.), AMS, 2004, 208 p. (ISBN 0-8218-3458-4), « History of graph coloring ».

[2] (en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001, 616 p. (ISBN 0-521-80340-3), 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 $K_{6}$ -free graphs », Combinatorica, vol. 14,‎ 1993, p. 279-361 (lire en ligne).

[5] (en) Tommy R. Jensen et Bjarne Toft, Graph Coloring Problems, Wiley-Interscience, coll. « Series in Discrete Mathematics and Optimization », 1995, p. 150–152.

[6] (en) Martin Gardner, « Mathematical Games », Scientific American, vol. 203, n^o 4,‎ 1960, p. 180

[7] (en) Hugo Hadwiger, « Überdeckung des euklidischen Raumes durch kongruente Mengen », Portugal. Math. (en), vol. 4,‎ 1945, p. 238–242.

[8] (en) Aubrey D. N. J. de Grey, « The chromatic number of the plane is at least 5 », arXiv,‎ 2018 (arXiv 1804.02385).

[9] (en) Branko Grünbaum, « A Problem in Graph Coloring », Amer. Math. Monthly, vol. 77, n^o 10,‎ 1970, 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, n^o 1,‎ 2007, p. 103-128.

[12] Souhila YAHIA, Algorithmes Gloutons Optimaux pour les graphes d’indifférence, MOULOUD MAMMERI, TIZI-OUZOU (Algérie), 19 octobre 2011, 50 p. (lire en ligne), p. 11-19

[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 », 2013 (ISBN 978-1-62705-018-0).

[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, n^o 1,‎ 1992, p. 193-201.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]