Coloration

Où on va

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 des rares problèmes dont on sait à la fois qu'il est très difficile en général, et très facile sur les graphes qu'on rencontre vraiment.

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

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

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	2	c'est la définition même

Graphe non orienté5 sommets, 5 arêtes

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

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 la fournit.

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 de preuve attendue, en deux temps

1. Exhiber une clique de taille $k$ : cela prouve $\chi \geq k$.
2. Exhiber une coloration à $k$ couleurs : cela 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 en devoir.

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$.
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é est garantie 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.

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. Mais rarement optimale : tout dépend de l'ordre.

Graphe non orienté6 sommets, 7 arêtes

0 / 6

Rien n'est encore visité.

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 : la couleur numéro $\Delta$ est toujours disponible.

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

L'ordre décide de tout

main.py

Sortie

>_ Prêt à exécuter…

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. En pratique, cela donne souvent un bon résultat, mais rien ne le garantit : ce n'est pas un algorithme exact.

Vérification rapidesans note, on peut se reprendre

1.Vous exhibez une coloration à 4 couleurs. Qu'avez-vous prouvé ?

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

3.L'algorithme glouton sur un graphe biparti…

Pourquoi c'est difficile

NP-complétude

Déterminer $\chi(G)$ pour un graphe quelconque est un problème NP-complet. 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.

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 l'approximation : le glouton donne immédiatement une solution valide, souvent proche.
Restreindre la famille de graphes : sur les graphes d'intervalles, sur les graphes cordaux, le problème redevient linéaire et exact.
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.
Utilisez 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…

Graphe non orienté7 sommets, 8 arêtes

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.

Exercices type

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, et le moyen standard est d'exhiber une clique de taille 4 : elle prouve $\chi \geq 4$ .

Les deux ensemble donnent $\chi = 4$ . Sans la clique, 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 : il existe des graphes où Welsh-Powell dépasse l'optimum. 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.

La méthode

Écris la phrase de modélisation : une arête signifie « ne peuvent pas partager ».
Cherche une clique avant de colorer : elle donne la minoration.
Colore ensuite, et compare le nombre de couleurs à la taille de la clique.
Conclus à l'optimalité seulement si les deux nombres coïncident.
Trie les sommets avant le glouton, par degré décroissant à défaut de mieux.
Ne présente jamais une coloration comme une preuve d'optimalité.
Cherche la famille du graphe avant de conclure que le problème est difficile.

En résumé

Une coloration propre interdit deux voisins de même couleur.
$\chi(G)$ est le nombre minimal de couleurs ; une arête modélise un conflit.
$\chi(K_n) = n$ , $\chi(\text{arbre}) = 2$ , $\chi(C_n) = 2$ ou 3 selon la parité.
Minoration : $\chi \geq \omega$ , prouvée en exhibant une clique.
Une coloration prouve seulement $\chi \leq k$  : il faut les deux pour conclure.
Le glouton est en $O(n + m)$ , toujours valide, rarement optimal.
Borne : $\chi \leq \Delta + 1$ , atteinte seulement par $K_n$ et les cycles impairs.
Welsh-Powell trie par degré décroissant : bonne heuristique, aucune garantie.
Le problème est NP-complet dès 3 couleurs, facile avec 2 (test de bipartisme).

Et ensuite ? Le glouton donne l'optimum si l'ordre est bien choisi. Le chapitre suivant montre sur quelles familles de graphes un tel ordre existe, et comment le calculer.

Ce que ce chapitre apporte