Coloration

Attribuer des salles à des cours qui se chevauchent, des fréquences à des antennes voisines, des registres à des variables : trois problèmes, une seule question. Combien de catégories faut-il au minimum pour que deux éléments en conflit ne se retrouvent jamais dans la même ? C'est la coloration de graphe : un problème très difficile en général, et pourtant facile sur des familles de graphes qu'on rencontre souvent, comme ceux qui naissent d'intervalles de temps. Les graphes cordaux et l'algorithme LexBFS, qui expliquent cette facilité, sont l'objet du chapitre suivant ; le parcours Mathématiques appliquées mène le même sujet sur un seul cas, les canaux d'un réseau de bornes radio, dans Théorie des graphes : parcours, coloration et ordonnancement.

Le problème

Définitions

Une coloration propre attribue une couleur à chaque sommet de sorte que deux sommets adjacents n'aient jamais la même.

Le nombre chromatique $\chi(G)$ est le plus petit nombre de couleurs permettant de colorer proprement $G$ .

Graphe non orienté6 sommets, 7 arêtes

Deux triangles reliés par l'arête C-D. Chacun exige trois couleurs, et la coloration montrée n'en emploie pas davantage.

Trois couleurs suffisent ici, et l'on va voir qu'aucune coloration à deux couleurs n'existe. Une arête ne relie jamais deux sommets de même teinte : c'est tout ce qu'exige la définition.

Modéliser un conflit

La règle de traduction est toujours la même : une arête signifie « ces deux-là ne peuvent pas partager ». Une couleur devient une salle, une fréquence, un serveur, un créneau.
Le nombre chromatique est alors le nombre minimal de ressources. Cette phrase mérite d'être écrite avant tout calcul, parce qu'elle contient toute la modélisation.

Problème réel	Sommet	Arête	Couleur
Emploi du temps	un cours	deux cours ayant un élève commun	un créneau
Antennes	une antenne	deux antennes qui se brouillent	une fréquence
Compilation	une variable	deux variables vivantes en même temps	un registre
Ordonnancement	une tâche	deux tâches qui se chevauchent	une machine

Vérification rapideon peut se reprendre

Une coloration à 4 couleurs est exhibée. Qu'a-t-on prouvé ?

Quelques valeurs à connaître

Graphe	$\chi$	Pourquoi
Graphe complet $K_n$	$n$	tous adjacents deux à deux
Cycle pair $C_{2k}$	2	on alterne
Cycle impair $C_{2k+1}$	3	l'alternance échoue à la fermeture
Arbre (au moins une arête)	2	on alterne par profondeur
Graphe biparti (au moins une arête)	2	c'est la définition même

Graphe non orienté5 sommets, 5 arêtes

Le cycle à cinq sommets. L'alternance tient de A à D, et E, voisin de D et de A, exige une troisième couleur.

Sur ce cycle à cinq sommets, l'alternance tient jusqu'à D, puis E se retrouve coincé entre D et A qui portent déjà les deux couleurs. Il en faut une troisième : $\chi(C_5) = 3$ .

Vérification rapideon peut se reprendre

Que vaut le nombre chromatique d'un cycle à 7 sommets ?

Prouver qu'on ne peut pas faire mieux

Trouver une coloration à $k$ couleurs prouve seulement que $\chi \leq k$ . Pour établir l'optimalité, il faut aussi une minoration, et la clique en fournit une, la plus courante.

Minoration par la clique

\chi(G) \geq \omega(G)

Dans une clique de taille $k$ , chaque sommet est adjacent à tous les autres : il leur faut $k$ couleurs distinctes. Il en faut donc au moins autant pour le graphe entier.

La structure d'une preuve d'optimalité, en deux temps.

Exhiber une minoration, le plus souvent une clique de taille $k$  : elle prouve $\chi \geq k$ .
Exhiber une coloration à $k$ couleurs : elle prouve $\chi \leq k$ .
Les deux ensemble donnent $\chi = k$ , et c'est une preuve complète.
Une coloration seule ne prouve jamais l'optimalité : elle ne fournit qu'une majoration. C'est l'erreur la plus fréquente.

Application au graphe du début

Le triangle A, B, C est une clique de taille 3, donc

\chi \geq 3

.
La coloration donnée utilise 3 couleurs, donc

\chi \leq 3

.
Conclusion :

\chi = 3

, et c'est démontré, pas constaté.

La clique ne suffit pas toujours

\chi \geq \omega

est une inégalité, pas une égalité. Le cycle

C_5

le montre : sa plus grande clique est une simple arête, donc

\omega = 2

, alors que

\chi = 3

. La minoration vient alors d'ailleurs : c'est le cycle impair lui-même, et non une clique, qui prouve

\chi(C_5) \geq 3

, puisque l'alternance à deux couleurs échoue à la fermeture.
L'écart se retrouve un cran plus haut. Ajouter au cycle

C_5

un sixième sommet, relié aux cinq autres, donne la roue à cinq rayons : sa plus grande clique est un triangle,

\omega = 3

, et pourtant il faut quatre couleurs. Le bord est un cycle impair, qui en exige trois, et le centre, voisin de tous les sommets du bord, ne peut reprendre aucune d'elles. Chercher une clique de taille 4 y serait peine perdue : la minoration est un raisonnement.
Il existe même des graphes où l'écart est énorme, sans le moindre triangle et pourtant impossibles à colorer avec peu de couleurs. Les graphes où l'égalité vaut pour le graphe et pour chacun de ses sous-graphes induits forment une famille particulière, les graphes parfaits, objet du chapitre suivant.

L'algorithme glouton

Principe

Parcourir les sommets dans un ordre donné et attribuer à chacun la plus petite couleur non utilisée par ses voisins déjà colorés.

C'est un algorithme glouton au sens du chapitre sur les arbres : chaque sommet reçoit sa couleur une fois pour toutes, et l'algorithme ne revient jamais sur un choix.

Algorithme

Entrée : G = (V, E), et un ordre v₁, v₂, …, vₙ des sommets

Sortie : une couleur par sommet

couleur ← dictionnaire vide

Pour chaque sommet v dans l'ordre donné Faire

interdites ← { couleur[u] | u voisin de v et déjà coloré }

couleur[v] ← plus petit entier ≥ 0 absent de interdites

FinPour

Retourner couleur

Il tourne en $O(n + m)$ et produit toujours une coloration valide. Optimale, elle peut l'être : il existe toujours un ordre qui y mène, mais rien ne dit lequel, et un mauvais ordre coûte cher.

Voici le glouton sur le graphe du début. La figure s'ouvre sur l'ordre alphabétique : A, B, C, D, E, F. L'ordre est une simple liste, fixée avant de commencer ; le glouton ne suit pas les arêtes, et il aurait pu aussi bien traiter A, D, B, E, C, F.

Coloration gloutonne6 sommets, 7 arêtes

Ordre :

0 / 6

Rien n'est encore coloré : avancer d'une étape, ou cliquer un sommet pour choisir soi-même le suivant.

Le graphe du début, colorié par le glouton. Au-dessus du dessin, l'ordre suivi et la couleur prise par chaque sommet ; en dessous, ce que le sommet traité voit.

À manipuler

Dérouler l'ordre alphabétique pas à pas. À chaque sommet, la figure épaissit les arêtes vers ses voisins déjà colorés, écrit les couleurs qu'ils interdisent, puis la couleur prise : D ne voit que C, qui porte 2, et reprend donc 0. À la fin, trois couleurs, exactement la coloration de la première figure du chapitre.
Passer ensuite à l'ordre « D en dernier », puis composer un ordre à la main en cliquant les sommets l'un après l'autre. La figure ne dit combien de couleurs suffisent, et ce qui le prouve, qu'une fois tous les sommets colorés.

Sur ce petit graphe, 640 des 720 ordres possibles mènent à trois couleurs. Les 80 autres en font employer quatre : dans l'ordre « D en dernier », A, B, C, E, F, D, E et F reçoivent 0 et 1 avant que D arrive, et D, qui voit alors les couleurs 2, 0 et 1, doit en ouvrir une quatrième.

La borne du glouton

\chi(G) \leq \Delta(G) + 1

où $\Delta$ est le degré maximal. En effet, quand le glouton colore un sommet, celui-ci a au plus $\Delta$ voisins, donc au plus $\Delta$ couleurs lui sont interdites : parmi les $\Delta + 1$ couleurs $0, 1, \ldots, \Delta$ , l'une au moins reste libre, et le glouton n'emploie jamais de numéro supérieur à $\Delta$ .

Le théorème de Brooks précise que, pour un graphe connexe, cette borne n'est atteinte que par les graphes complets et les cycles impairs : pour tous les autres, $\chi \leq \Delta$ .

L'ordre décide de tout

main.py

Sortie

>_ Prêt à exécuter…

Le même graphe, dessiné en deux colonnes, les g à gauche et les d à droite : chaque g est relié à tous les d, sauf à celui qui porte son numéro.

Coloration gloutonne8 sommets, 12 arêtes

Ordre :

0 / 8

Rien n'est encore coloré : avancer d'une étape, ou cliquer un sommet pour choisir soi-même le suivant.

Le graphe biparti du programme. Deux couleurs suffisent toujours : une par colonne.

À manipuler

Dérouler l'ordre alterné. g1 et d1, qui ne sont pas voisins, prennent tous deux la couleur 0 ; g2 et d2 prennent 1, g3 et d3 prennent 2, et chaque nouvelle paire trouve toutes les couleurs précédentes déjà prises en face : g4 et d4 finissent sur la couleur 3. Quatre couleurs pour un graphe qui en demande deux.
Passer à l'ordre « par côté » : deux couleurs. Welsh-Powell en trouve deux aussi, mais par chance, comme le dit l'encadré ci-dessous : tous les degrés valent 3, et c'est le nom qui a rangé les d avant les g.

Welsh-Powell. L'heuristique la plus connue consiste à trier les sommets par degré décroissant avant d'appliquer le glouton.
L'intuition : les sommets très connectés sont les plus contraints, autant les traiter quand toutes les couleurs sont encore disponibles. Rien ne le garantit, et le tri est aveugle quand les degrés sont égaux. Sur le graphe ci-dessus, où tous valent 3, c'est le nom qui a décidé : les d passent avant les g, ce qui revient par chance à l'ordre « par côté ». Renommés de façon que l'ordre alphabétique alterne les deux côtés, les mêmes sommets font employer 4 couleurs à Welsh-Powell.
L'heuristique échoue même sur un simple chemin de six sommets, B, A, F, E, D, C : les quatre sommets intérieurs ont le degré 2, l'ordre obtenu est A, D, E, F, B, C, et le glouton y met trois couleurs (A et D reçoivent 0, E reçoit 1, puis F, entre A et E, reçoit 2) là où deux suffisent.
Une variante plus fine, DSATUR, choisit à chaque pas le sommet dont les voisins déjà colorés portent le plus de couleurs différentes. Elle n'est pas exacte non plus, mais sur un graphe biparti elle trouve toujours les deux couleurs.

Coloration gloutonne6 sommets, 5 arêtes

Ordre :

0 / 6

Rien n'est encore coloré : avancer d'une étape, ou cliquer un sommet pour choisir soi-même le suivant.

Le chemin B, A, F, E, D, C. Ses quatre sommets intérieurs ont le degré 2, ses deux bouts le degré 1.

À manipuler

Dérouler Welsh-Powell : A passe en premier, puis D, que rien ne relie à A et qui reprend la couleur 0. E prend 1 à côté de D, et F, coincé entre A (0) et E (1), ouvre une troisième couleur. Trois arêtes séparent A de D : dans une coloration à deux couleurs, ils doivent différer, et le tri par degré les a coloriés les premiers, sans rien entre eux.
Suivre ensuite le chemin d'un bout à l'autre : les couleurs 0 et 1 alternent, et deux suffisent.

Pourquoi c'est difficile

NP-complétude

Décider si un graphe quelconque se colore avec $k$ couleurs est un problème NP-complet, et calculer $\chi(G)$ est donc NP-difficile. On sait vérifier rapidement qu'une coloration proposée est valide, mais on ne connaît aucun algorithme qui en trouve une optimale en temps polynomial.

Ce que cette classe signifie exactement est traité dans le chapitre NP-complétude et 3-SAT, et la coloration s'y retrouve d'ailleurs sous une autre forme : modéliser un problème en SAT la traduit en clauses, ce qui permet de la confier à un solveur plutôt qu'à un algorithme écrit pour elle.

Même la question restreinte « peut-on colorer ce graphe avec 3 couleurs ? » est NP-complète. Avec 2 couleurs, en revanche, c'est facile : cela revient à tester si le graphe est biparti, ce qu'un BFS fait en une passe.

NP-complet ne veut pas dire « insoluble »

Cela veut dire qu'aucune méthode générale et rapide n'est connue, et qu'il est très improbable qu'il en existe une.
Trois échappatoires bien réelles, et toutes utilisées :
Accepter une solution sans garantie : le glouton donne immédiatement une coloration valide, souvent proche de l'optimum en pratique, mais sans aucune borne sur l'écart.
Restreindre la famille de graphes : quand les conflits viennent d'intervalles de temps, comme dans le cas complet ci-dessous, le problème redevient exact et rapide ; le chapitre suivant en donne la raison.
Se contenter de petites instances : une recherche exhaustive intelligente traite sans peine quelques dizaines de sommets.
La deuxième voie est de loin la plus rentable, et c'est l'objet du chapitre suivant.

Un cas complet : des tâches qui se chevauchent

Voici la modélisation classique. Chaque tâche devient un sommet, deux tâches sont reliées si leurs intervalles se chevauchent, et une couleur est une machine.

Le test de chevauchement

Pour deux intervalles $[d_1, f_1)$ et $[d_2, f_2)$  :

\text{ils se chevauchent} \iff \max(d_1, d_2) < \min(f_1, f_2)

Pourquoi cette formule et pas une disjonction de cas

On serait tenté d'énumérer les positions relatives des deux intervalles. La forme max(début) < min(fin) dit la même chose sans aucun cas particulier, et se lit directement : l'intersection est non vide si elle commence avant de finir.
Utiliser l'inégalité stricte : deux tâches dont l'une finit à l'instant où l'autre commence ne se chevauchent pas.

main.py

Sortie

>_ Prêt à exécuter…

Coloration gloutonne7 tâches, 8 chevauchements

Ordre :

7 / 7

G : chevauche F (2) ; interdites : {2} → machine 0

Planning par machine

L'ordre « début croissant » : 3 machines, et c'est le minimum.

Il en faut bien 3 : A, B et C se chevauchent deux à deux, et tournent toutes à l'instant 2. Cette clique de taille ω = 3, reliée par les arêtes épaissies, exige 3 machines à elle seule.

Par début croissant, le glouton n'ouvre jamais plus de ω machines : c'est garanti pour des intervalles, quelles que soient les tâches.

Les sept tâches, reliées quand leurs intervalles se chevauchent, colorées par le glouton dans l'ordre choisi par les boutons d'ordre. Une couleur est une machine ; le planning, sous le graphe, montre ce qui tourne sur chacune.

À manipuler

Choisir l'ordre défavorable et le dérouler. Au moment de placer D, la bande tiretée du planning couvre son intervalle, [5, 9) : C, E et F y tournent déjà, sur les machines 2, 0 et 1, et ce sont exactement les couleurs interdites. D ouvre une quatrième machine.
Revenir au début croissant, puis essayer d'autres ordres, à la main : aucun ne descend sous trois machines, puisque A, B et C tournent ensemble à l'instant 2.

Le même algorithme, deux résultats

Trier par date de début donne 3 machines, ce qui est optimal puisque la clique vaut 3. L'ordre défavorable en donne 4.
Le glouton n'est pas en cause : c'est l'ordre qui décide. Toute la question devient donc : existe-t-il un ordre qui garantisse l'optimalité ? Pour cette famille de graphes, la réponse est oui, et c'est le sujet du chapitre suivant.

Vérification rapideon peut se reprendre

L'algorithme glouton sur un graphe biparti…

Mettre en pratique

Quel est le nombre chromatique d'un cycle à 7 sommets ?

Sur un cycle, on tente d'alterner deux couleurs. Cela fonctionne exactement quand la longueur est paire : en revenant au point de départ, on retombe sur la bonne couleur.

Avec 7 sommets, l'alternance échoue à la fermeture : le dernier sommet est voisin du premier et porterait la même couleur. Il en faut une troisième.

Règle générale : $\chi(C_n) = 2$ si $n$ est pair, 3 s'il est impair.

Une coloration à 4 couleurs a été trouvée. Est-elle optimale ?

On ne peut pas le dire. Une coloration ne fournit qu'une majoration : $\chi \leq 4$ .

Pour conclure à l'optimalité, il faut une minoration du même niveau, $\chi \geq 4$ . Le moyen le plus courant est d'exhiber une clique de taille 4, mais ce n'est pas le seul : la roue à cinq rayons n'a aucune clique de taille 4 et exige pourtant quatre couleurs, parce que son bord est un cycle impair et que son centre voit tout le bord.

La minoration et la coloration ensemble donnent $\chi = 4$ . Sans minoration, la coloration peut parfaitement être améliorable, comme le montre le glouton dans un mauvais ordre.

Pourquoi

\chi \geq \omega

, et pourquoi l'égalité n'est-elle pas garantie ?

L'inégalité vient de la définition de la clique : ses sommets sont deux à deux adjacents, donc ils portent tous des couleurs différentes. Une clique de taille $k$ force donc $k$ couleurs.

L'égalité n'est pas garantie parce que la difficulté d'un graphe ne tient pas seulement à ses cliques. Le cycle $C_5$ en est le contre-exemple minimal : $\omega = 2$ , car il n'a aucun triangle, et pourtant $\chi = 3$ .

Les graphes où l'égalité vaut pour tous les sous-graphes induits s'appellent les graphes parfaits.

Le glouton peut-il utiliser plus de couleurs que nécessaire ? De combien ?

Oui, et l'écart peut être arbitrairement grand.

Sur un graphe biparti, où 2 couleurs suffisent toujours, il existe des ordres qui font utiliser au glouton un nombre de couleurs proportionnel au nombre de sommets.

La borne générale reste $\Delta + 1$ couleurs, quel que soit l'ordre. Ce qui varie, c'est la distance entre ce résultat et l'optimum, et cette distance ne dépend que de l'ordre choisi.

À quoi sert l'heuristique de Welsh-Powell ?

À choisir un ordre plus favorable : les sommets sont triés par degré décroissant avant l'application du glouton.

L'intuition est que les sommets les plus contraints, ceux qui ont le plus de voisins, doivent être traités tant que le maximum de couleurs est encore disponible.

En pratique le résultat est souvent bon, mais ce n'est pas un algorithme exact : sur le chemin B, A, F, E, D, C, il emploie trois couleurs pour deux nécessaires. Et quand beaucoup de sommets ont le même degré, le tri ne décide presque rien : c'est la règle de départage des égalités qui fixe l'ordre, et elle peut aussi bien donner le pire. C'est une heuristique, pas une garantie.

Colorer avec 2 couleurs est facile, avec 3 c'est NP-complet. Pourquoi cette rupture ?

Parce que colorer avec 2 couleurs revient exactement à tester si le graphe est biparti, ce qu'un simple BFS bicolore décide en $\Theta(n + m)$  : chaque sommet n'a aucun choix, sa couleur est imposée par son découvreur.

Dès 3 couleurs, un choix apparaît à chaque sommet, et ce choix influence tout le reste du graphe. Il n'existe plus de propagation locale qui décide, et l'on retombe sur une exploration combinatoire.

Cette rupture entre 2 et 3 est un phénomène classique en complexité : elle se retrouve pour la satisfiabilité, facile en 2-SAT et NP-complète en 3-SAT.

Le problème

Quelques valeurs à connaître

Prouver qu'on ne peut pas faire mieux

L'algorithme glouton

L'ordre décide de tout

Pourquoi c'est difficile

Un cas complet : des tâches qui se chevauchent

Mettre en pratique

Dans la bibliothèque d'exercices

Un cas complet : des tâches qui se chevauchent