Théorie des graphes : parcours, coloration et ordonnancement

Un centre de données doit exécuter des tâches, chacune sur un créneau horaire imposé, chaque serveur ne pouvant en traiter qu'une à la fois. Combien de serveurs faut-il allumer au minimum ? Posée ainsi, la question paraît relever de l'organisation. Traduite en graphe, elle devient un problème de coloration, et se résout exactement, en temps linéaire, par un algorithme de six lignes. Ce chapitre fait ce trajet complet : le vocabulaire, les représentations, les parcours, puis la coloration et son application à l'ordonnancement. Le parcours Théorie des graphes consacre un chapitre entier à chacune de ces étapes, avec des figures qui se manipulent ; celui-ci les enchaîne d'un bout à l'autre sur un seul cas.

Il referme le parcours et prend le contre-pied du chapitre sur la cryptographie : là, un problème restait difficile et c'était heureux ; ici, un problème réputé difficile s'effondre dès que les données ont la bonne structure.

Ce chapitre et le parcours Théorie des graphes

Le parcours Théorie des graphes pose chaque notion en détail, avec les dessins, les parcours animés, les arbres couvrants, les plus courts chemins, les flots et les couplages. Ce chapitre-ci n'en reprend que ce qu'exige un problème d'ingénierie précis : le dimensionnement d'un parc de serveurs. Il le suit de bout en bout, de la modélisation à l'algorithme, puis jusqu'à la preuve que la solution trouvée est la meilleure possible.

Les sections renvoient aux chapitres du parcours qui développent leurs notions : si une idée résiste ici, c'est là qu'il faut aller la chercher.

Vocabulaire

Définition

Un graphe $G = (V, E)$ est la donnée d'un ensemble fini de sommets $V$ et d'un ensemble $E$ de paires de sommets, appelées arêtes si le graphe est non orienté, arcs s'il est orienté.

On note $n = |V|$ l'ordre du graphe et $m = |E|$ sa taille.

Un graphe est simple s'il n'a ni boucle (arête d'un sommet vers lui-même) ni arête multiple. Sauf mention contraire, tous les graphes de ce chapitre sont simples et non orientés.

Orienté ou non : la question à se poser

La relation est-elle symétrique ? « Ces deux tâches se chevauchent » l'est : si A chevauche B, B chevauche A, graphe non orienté. « Cette tâche doit finir avant que celle-là commence » ne l'est pas, graphe orienté. Poser cette question dès la modélisation évite d'avoir à tout reprendre.

Les deux situations mènent à deux problèmes d'ordonnancement différents. Les contraintes de précédence, avec leurs dates au plus tôt et leur chemin critique, sont traitées dans le chapitre sur les graphes orientés. Ce chapitre-ci traite l'autre : des tâches aux horaires imposés, qui se disputent des serveurs.

Degré

Le degré $d(v)$ d'un sommet est son nombre de voisins. Dans un graphe orienté, on distingue le degré entrant et le degré sortant.

Lemme des poignées de main

$\sum d(v) = 2m$

La somme des degrés vaut deux fois le nombre d'arêtes, puisque chaque arête est comptée à ses deux extrémités.

La conséquence, qu'on utilise sans cesse

La somme des degrés étant paire, le nombre de sommets de degré impair est nécessairement pair. Dans toute assemblée, le nombre de personnes ayant serré un nombre impair de mains est pair, d'où le nom du lemme. C'est le premier outil pour prouver qu'un graphe donné ne peut pas exister.

Chemins, cycles, connexité

Définitions

Une chaîne est une suite de sommets consécutivement reliés. Elle est simple si elle ne répète aucune arête, élémentaire si elle ne répète aucun sommet.

Un cycle est une chaîne qui revient à son point de départ. Dans un graphe orienté, on parle de chemin et de circuit.

Un graphe est connexe si toute paire de sommets est reliée par une chaîne. Sinon, il se décompose en composantes connexes.

Un arbre est un graphe connexe sans cycle. Il possède exactement $n - 1$ arêtes.

Sous-graphes et cliques

Un sous-graphe induit par une partie $W \subseteq V$ est le graphe formé de $W$ et de toutes les arêtes de $G$ dont les deux extrémités sont dans $W$ . On ne choisit pas les arêtes : elles viennent avec les sommets.

Définition

Une clique est un ensemble de sommets deux à deux adjacents. On note $\omega (G)$ la taille de la plus grande clique de $G$ .

La clique jouera un rôle central : c'est elle qui donnera la borne inférieure du nombre de couleurs nécessaires.

Représenter un graphe en machine

Trois représentations, et le choix a des conséquences mesurables.

Les trois classiques

Liste d'adjacence : pour chaque sommet, la liste de ses voisins. En Python, un dictionnaire de set. Occupe $O(n + m)$ .

Matrice d'adjacence, un tableau $n \times n$ où $A[i][j] = 1$ si l'arête existe. Occupe $O(n^2)$ , quel que soit le nombre d'arêtes.

Liste d'arêtes, la simple liste des paires. Occupe $O(m)$ , compacte mais lente à interroger.

Opération	Liste d'adjacence	Matrice	Liste d'arêtes
$u$ et $v$ sont-ils voisins ?	$O(1)$ avec un `set`	$O(1)$	$O(m)$
Parcourir les voisins de $u$	$O(d(u))$	$O(n)$	$O(m)$
Ajouter une arête	$O(1)$	$O(1)$	$O(1)$
Mémoire	$O(n + m)$	$O(n^2)$	$O(m)$

Comment choisir

Un graphe est creux quand $m$ est de l'ordre de $n$ , dense quand il approche $n^2/2$ . Les graphes réels sont presque toujours creux : réseaux, dépendances, chevauchements de tâches.

Pour un graphe creux, la liste d'adjacence gagne sur tous les tableaux : mémoire et temps de parcours. La matrice ne se justifie que sur un graphe dense, ou quand on veut exploiter ses propriétés algébriques.

Ce que la matrice sait faire et que la liste ne sait pas

Le coefficient $(i, j)$ de $A^k$ donne le nombre de chaînes de longueur exactement $k$ entre les sommets $i$ et $j$ . Une multiplication de matrices répond ainsi à une question de dénombrement de chemins, impossible à formuler aussi simplement avec une liste d'adjacence.

Voici les deux représentations du petit graphe suivant, écrites à partir des mêmes arêtes.

Graphe non orienté6 sommets, 7 arêtes

Six sommets, sept arêtes. Deux triangles, A B C et D E F, reliés par la seule arête C-D.

Ce qu'il faut repérer sur ce dessin, ce sont les deux triangles et le sommet qui les relie. Chaque triangle est un groupe de trois sommets reliés deux à deux : c'est la plus petite structure qui interdira plus loin de se contenter de deux couleurs. Et l'arête C-D est le seul passage entre les deux moitiés : la retirer couperait le graphe en deux morceaux sans aucun lien.

Matrice d'adjacence
	A	B	C	D	E	F	d
A	0	1	1	0	0	0	2
B	1	0	1	0	0	0	2
C	1	1	0	1	0	0	3
D	0	0	1	0	1	1	3
E	0	0	0	1	0	1	2
F	0	0	0	1	1	0	2

Liste d'adjacence

A: : {B, C}
B: : {A, C}
C: : {A, B, D}
D: : {C, E, F}
E: : {D, F}
F: : {D, E}

Liste d'arêtes

(A, B)
(A, C)
(B, C)
(C, D)
(D, E)
(D, F)
(E, F)

Les trois écritures du graphe ci-dessus, calculées à partir des mêmes arêtes que le dessin. Aucune n'est recopiée à la main : elles ne peuvent donc pas se contredire. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

Trois lectures du même objet, et trois usages. La matrice répond en une case à « ces deux sommets sont-ils voisins ? ». La liste donne d'un coup tous les voisins d'un sommet, ce que la matrice ne fait qu'en parcourant une ligne entière. La liste d'arêtes est la plus compacte, et c'est celle qu'on écrit dans un fichier.

Deux propriétés se constatent sur les degrés affichés plutôt que de s'admettre : leur somme vaut 14, soit deux fois les sept arêtes, parce que chaque arête est comptée à ses deux extrémités ; et le nombre de sommets de degré impair est pair, ce qui en découle immédiatement.

Le bloc suivant refait le même travail en Python, pour qui veut la manière de le produire plutôt que le résultat, et pousse jusqu'à $A^2$ , que la figure ne calcule pas.

main.py

Sortie

>_ Prêt à exécuter…

Parcourir un graphe

Deux parcours, une seule différence

Le parcours en largeur (BFS) explore les sommets par distances croissantes : d'abord tous les voisins, puis les voisins des voisins. Il utilise une file (premier entré, premier sorti).

Le parcours en profondeur (DFS) s'enfonce aussi loin que possible avant de revenir en arrière. Il utilise une pile, ou la récursion.

Les deux visitent chaque sommet une fois et chaque arête deux fois : leur complexité est $\Theta (n + m)$ avec des listes d'adjacence. Avec une matrice elle tombe à $\Theta (n^2)$ , puisqu'il faut alors examiner toute une ligne pour trouver les voisins d'un sommet. Le chapitre sur les parcours les déroule pas à pas et en tire les composantes connexes, le test de biparti et la détection de cycle ; seul l'essentiel sert ici.

Lequel pour quoi

BFS : plus court chemin en nombre d'arêtes, distance à un sommet, graphe biparti. Il donne la distance parce qu'il explore par couches.

DFS : détection de cycle, tri topologique, composantes fortement connexes. Il donne la structure parce qu'il suit les branches jusqu'au bout.

Dijkstra et Prim sont des variantes où la file devient une file de priorité, ce qui permet de tenir compte de poids sur les arêtes.

Un parcours en largeur, déroulé sur le graphe précédent auquel on a ajouté un sommet G au bout. Dérouler les étapes une à une.

Graphe non orienté7 sommets, 8 arêtes

0 / 7

Rien n'est encore visité.

Parcours en largeur depuis A. Les arêtes s'allument dans l'ordre où elles font découvrir un sommet neuf ; celles qui ne découvrent rien restent éteintes.

Ce qu'il faut y voir : les sommets s'allument par vagues, et chaque vague est à une arête de plus de A. B et C d'abord, puis D, puis E et F, puis G. Les arêtes qui restent éteintes, comme B-C, sont celles qui mènent à un sommet déjà découvert : elles sont parcourues, mais n'apprennent rien. Le rang de la vague où un sommet s'allume est sa distance à A, et c'est la seule raison pour laquelle le parcours en largeur donne les plus courts chemins.

main.py

Sortie

>_ Prêt à exécuter…

Marquer à l'enfilement, pas au défilement

En BFS, un sommet doit être marqué « vu » au moment où on l'ajoute à la file. Si on attend de le retirer, il peut être ajouté plusieurs fois par des voisins différents : le parcours reste correct mais devient quadratique sur un graphe dense, et les distances calculées peuvent être fausses.

Pas de Dijkstra sur un graphe non pondéré

Quand toutes les arêtes se valent, le plus court chemin est celui qui en compte le moins, et c'est exactement ce que calcule un parcours en largeur, en $\Theta (n + m)$ .

Dijkstra donnerait la même réponse, avec une file de priorité en plus, donc un facteur logarithmique payé pour rien. Le réflexe à prendre : regarder les poids avant de choisir l'algorithme. Poids identiques, BFS ; poids positifs, Dijkstra ; poids négatifs possibles, Bellman-Ford.

Coloration et nombre chromatique

Colorier d'abord, on expliquera après

Une seule règle : deux sommets reliés par une arête ne peuvent pas porter la même couleur. Cinq teintes sont proposées ; en utiliser le moins possible.

Le faire vraiment, avant de lire la suite. Et retenir le nombre de couleurs du premier essai, celui où les sommets ont été coloriés à mesure qu'ils se présentaient : c'est de ce nombre-là que parle tout le reste de la section.

Sept tâches, onze conflits. Combien de serveurs au minimum ?

PinceauRecliquer un sommet de la même couleur l'efface.

Couleurs utilisées : 0Sommets à colorier : 7

Choisir une couleur, puis cliquer les sommets. La règle tient en une ligne : deux sommets reliés par une arête ne peuvent pas porter la même couleur. Chercher à en employer le moins possible, et relever combien il en a fallu au premier essai — c'est ce nombre-là que la suite du chapitre explique.

Deux choses se remarquent en jouant, et ce sont les deux questions de la section.

La première : l'ordre dans lequel on colorie change le résultat. En prenant les sommets de A à G et en donnant à chacun la première couleur libre, on en utilise quatre. Trois suffisent pourtant. Rien n'a changé dans le graphe, seulement l'ordre de passage.

La seconde, plus gênante : une fois trois couleurs trouvées, comment sait-on qu'on ne peut pas descendre à deux ? Avoir réussi avec trois prouve qu'il en suffit trois. Cela ne prouve pas qu'il en faut trois. Les deux affirmations sont différentes, et il en manque une.

Définitions

Une coloration 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 $G$ .

Le chapitre sur la coloration développe ces notions sur d'autres conflits (salles, fréquences, registres) ; celui-ci les applique à des serveurs, et va jusqu'à la preuve d'optimalité.

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

Comment on prouve qu'une coloration est optimale

En deux temps :

Exhiber une clique de taille $k$  : cela prouve $\chi \geq k$  ;
Exhiber une coloration à $k$ couleurs : cela prouve $\chi \leq k$ .

Les deux ensemble donnent $\chi = k$ . Une coloration seule ne prouve jamais l'optimalité : elle ne fournit qu'une majoration.

Un problème NP-complet

Déterminer $\chi (G)$ pour un graphe quelconque est NP-complet. Deux faits se combinent. Vérifier qu'une coloration proposée est valide se fait rapidement, mais aucun algorithme connu n'en trouve une optimale en temps polynomial. Et si l'on en trouvait un, il résoudrait du même coup tous les problèmes de la classe NP.

NP-complet ne veut pas dire « insoluble »

Cela veut dire qu'aucune méthode générale et rapide n'est connue. Deux échappatoires bien réelles : accepter une solution approchée (l'algorithme glouton en fournit une immédiatement) ou se restreindre à une famille de graphes particulière, où le problème redevient facile. C'est exactement ce que fera ce chapitre, et c'est ce qui rend le cas ci-dessous résoluble de façon optimale.

L'algorithme glouton

Principe

Un algorithme glouton fait à chaque étape le choix qui paraît le meilleur localement, sans jamais revenir en arrière.

Pour la coloration : on parcourt les sommets dans un ordre donné et on attribue à 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

Tout se joue sur l'avant-dernière ligne. Elle construit l'ensemble des couleurs interdites, c'est-à-dire déjà prises par un voisin, puis prend la plus petite qui reste. Les voisins pas encore colorés n'y figurent pas : l'algorithme décide sans rien savoir de ce qui vient après lui. C'est de là que viendront à la fois sa rapidité et son défaut.

Il est en $O(n + m)$ et produit toujours une coloration valide. Mais pas forcément optimale : le résultat dépend entièrement de l'ordre choisi, et l'écart n'est pas anecdotique.

L'ordre décide de tout

Voici un graphe de six sommets où les $A_i$ ne sont reliés qu'aux $B_j$ d'indice différent. Il est biparti : les $A$ d'un côté, les $B$ de l'autre, aucune arête à l'intérieur d'un groupe. Deux couleurs suffisent donc, et deux couleurs sont nécessaires puisqu'il y a au moins une arête.

Graphe non orienté6 sommets, 6 arêtes

L'optimum : deux couleurs, une par côté de la bipartition.

Le même graphe, colorié par le glouton dans l'ordre $A_1, B_1, A_2, B_2, A_3, B_3$  :

Graphe non orienté6 sommets, 6 arêtes

Le même graphe et le même algorithme, dans l'ordre A1, B1, A2, B2, A3, B3 : trois couleurs.

Pourquoi le glouton se piège ici

$A_1$ arrive en premier et prend la couleur 0. $B_1$ suit ; ses voisins sont $A_2$ et $A_3$ , pas encore colorés, donc rien ne l'empêche de prendre la couleur 0 lui aussi.

C'est ce choix, parfaitement légal et parfaitement local, qui coûte cher. $A_2$ voit alors $B_1$ en 0 et doit passer en 1. $B_2$ voit $A_1$ en 0 et passe en 1 à son tour. Le couple suivant se retrouve donc avec 0 et 1 déjà interdits, et une troisième couleur devient inévitable.

Le glouton n'a rien fait de faux : il a seulement décidé sans savoir ce qui venait après. C'est la définition même d'un algorithme glouton, et sa limite.

L'écart peut être aussi grand qu'on veut

Ce graphe se prolonge : avec $A_1 \ldots A_k$ et $B_1 \ldots B_k$ reliés dès que les indices diffèrent, le même ordre alterné fait consommer $k$ couleurs au glouton, là où deux suffisent toujours. Un mauvais ordre ne coûte donc pas « une couleur de trop » : il peut coûter la moitié des sommets.

Ce qu'on garde du glouton

Il ne dépasse jamais $\Delta + 1$ couleurs, où $\Delta$ est le degré maximal : au moment de colorer un sommet, il a au plus $\Delta$ voisins, donc au plus $\Delta$ couleurs interdites.
Il existe toujours un ordre pour lequel il trouve l'optimum. Le trouver est aussi difficile que le problème de départ, ce qui ne rend pas ce résultat très utile en pratique.
D'où les heuristiques d'ordre. La plus connue, Welsh-Powell, trie les sommets par degré décroissant : les sommets les plus contraints sont traités quand il reste encore des couleurs libres. Souvent bien meilleure que l'ordre arbitraire, sans aucune garantie.

Vérification

Vérification rapideon peut se reprendre

1.Une matrice d'adjacence sur un graphe de 10 000 sommets et 30 000 arêtes occupe…

2.Le parcours en largeur donne les plus courts chemins, pas le parcours en profondeur. Pourquoi ?

3.Une clique de taille 4 dans un graphe prouve que…

Un cas complet : planifier des tâches

Voici la modélisation. Chaque tâche devient un sommet. Deux tâches sont reliées par une arête si leurs intervalles se chevauchent, elles ne peuvent alors pas tourner sur le même serveur. Une couleur est un serveur. Le nombre minimal de serveurs est le nombre chromatique.

Le test de chevauchement

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

\text{chevauchement} \iff \max(d_1, d_2) < \min(f_1, f_2)

En clair : deux intervalles se rencontrent si le plus tardif des deux débuts précède la plus précoce des deux fins. Sur $[0, 4)$ et $[2, 6)$  : le plus tardif des débuts est 2, la plus précoce des fins est 4, et $2 < 4$ , donc ils se chevauchent.

Pourquoi cette formule plutôt qu'une disjonction de cas

On serait tenté d'écrire «  $d_1 < f_2$ et $d_2 < f_1$  », ou pire, d'énumérer les positions relatives des deux intervalles. La forme $\max(\text{débuts}) < \min(\text{fins})$ dit la même chose en une ligne, sans cas particulier, et se lit directement : l'intersection est non vide si elle commence avant de finir. L'inégalité est stricte : deux tâches dont l'une finit à l'instant où l'autre commence ne se chevauchent pas.

Un graphe construit ainsi s'appelle un graphe d'intervalles, et il a des propriétés remarquables.

main.py

Sortie

>_ Prêt à exécuter…

Le même algorithme, deux résultats

L'ordre alphabétique donne 3 serveurs, l'ordre défavorable en donne 4, sur le même graphe. Le décompte du recouvrement, lui, ne dépend d'aucun ordre. À $t = 2$ , trois tâches tournent (A, B, C) ; à $t = 8$ , trois également (D, E, F) ; nulle part il n'y en a quatre à la fois. Donc $\omega = 3$ . Or 3 serveurs suffisent (l'ordre alphabétique le montre) et sont nécessaires (la clique de taille 3 le prouve). Le glouton n'est pas en cause : c'est l'ordre qui décide. Toute la question devient donc : peut-on choisir un ordre qui garantisse l'optimalité ?

Le graphe des chevauchements, coloré : trois couleurs, donc trois serveurs, et le triangle mis en évidence prouve qu'on ne peut pas faire mieux.

Graphe non orienté7 sommets, 8 arêteschemin mis en évidence

Le graphe des chevauchements, colorié en trois couleurs. Le chemin surligné A-B-C-A est le triangle qui prouve qu'on ne peut pas descendre en dessous de trois.

Deux choses à regarder, et elles sont de nature différente. La coloration d'abord : aucune arête ne relie deux sommets de même couleur, ce qui se vérifie arête par arête et prouve que trois serveurs suffisent. Le triangle surligné ensuite : ses trois sommets sont reliés deux à deux, donc il leur faut trois couleurs à eux seuls, ce qui prouve que trois serveurs sont nécessaires. Les deux ensemble, et seulement les deux ensemble, donnent $\chi = 3$ .

Graphes cordaux, graphes parfaits, LexBFS

Le glouton donne une coloration valide, mais on ne sait pas dire si elle est la meilleure, et compter le recouvrement maximal ne donne qu'une borne inférieure. Il manque une raison de croire que cette borne est atteinte. Cette raison n'est pas dans l'algorithme, elle est dans la forme du graphe : certaines familles de graphes garantissent que la borne de la clique est exacte. Les deux définitions qui suivent nomment ces familles.

Trois définitions liées

Un graphe est cordal (ou triangulé) si tout cycle de longueur au moins 4 possède une corde, une arête reliant deux sommets non consécutifs du cycle. Autrement dit, ses seuls cycles sans corde sont des triangles.

Un graphe est parfait si, pour tout sous-graphe induit $G'$ , on a $\chi (G') = \omega (G')$ . La borne inférieure par la clique y est donc toujours atteinte.

Ces familles, avec les graphes bipartis et planaires, sont étudiées dans le chapitre sur les familles remarquables. Pour le problème des serveurs, seule compte la chaîne d'implications qui le débloque :

graphe d'intervalles ⟹ graphe cordal ⟹ graphe parfait ⟹ $\chi = \omega$

Il suffit donc de compter le recouvrement maximal pour connaître le nombre exact de serveurs. Reste à trouver une coloration qui l'atteigne.

Le glouton ne se trompe que dans un cas : quand il colorie un sommet dont il verra plus tard qu'il aurait fallu le traiter autrement. Il faudrait donc un ordre où chaque sommet, au moment où on l'atteint, n'a autour de lui que des voisins déjà coloriés et tous reliés entre eux. Le glouton n'y verrait alors qu'une clique, et ne dépenserait jamais plus de couleurs qu'elle n'en exige. Un tel ordre porte un nom, ordre parfait d'élimination, il existe sur tout graphe cordal, et l'algorithme ci-dessous le produit.

LexBFS

Le parcours en largeur lexicographique est un BFS où, à chaque étape, on choisit le sommet dont l'étiquette est la plus grande dans l'ordre lexicographique. Chaque sommet retenu ajoute son numéro à l'étiquette de ses voisins non encore traités.

Sur un graphe cordal, l'ordre produit, lu à l'envers, est un ordre parfait d'élimination : chaque sommet forme une clique avec ceux de ses voisins qui le précèdent dans le parcours. L'algorithme glouton appliqué dans l'ordre du parcours ne voit donc jamais, autour d'un sommet, que les membres d'une clique : il n'utilise pas plus de $\omega$ couleurs, et la coloration est optimale, en temps linéaire.

La mise à jour des étiquettes est la seule partie qui résiste à la lecture. Elle se suit mieux sur quatre sommets : un triangle A, B, C, plus un sommet D accroché à C.

Graphe non orienté4 sommets, 4 arêtes

0 / 4

Rien n'est encore visité.

Le parcours en largeur lexicographique sur un triangle et un sommet pendant. L'ordre obtenu est D, C, B, A.

Trois choses se lisent sur cette trace.

L'étiquette n'est pas un compteur mais une suite de numéros, comparée dans l'ordre du dictionnaire : $(4, 2)$ passe avant $(4)$ , et $(4)$ avant $(3, 3)$ . C'est ce qui donne son nom à l'algorithme.

Un sommet n'inscrit son numéro que chez ses voisins non encore traités. Le travail total est donc borné par le nombre d'arêtes, d'où le coût en $O(n + m)$ .

Enfin, l'ordre D, C, B, A colorié gloutonnement donne trois couleurs, et le triangle A, B, C en exige trois : la coloration est optimale, et on peut le prouver sans essayer d'autres ordres.

Ce qui vient d'être gagné

Le problème général de coloration est NP-complet. En reconnaissant que ce graphe est un graphe d'intervalles, donc cordal, donc parfait, on obtient une solution exacte en $O(n + m)$ . On n'a pas trouvé un meilleur algorithme général : on a identifié la structure du problème particulier. C'est le mouvement le plus rentable de toute l'algorithmique.

main.py

Sortie

>_ Prêt à exécuter…

Et la même chose en images : les intervalles d'un côté, le graphe coloré de l'autre. Sur le dessin de gauche, vérifier qu'aucune barre d'une même ligne n'en recouvre une autre : une ligne sans recouvrement, c'est un serveur qui tient son planning. Sur celui de droite, vérifier qu'aucune arête ne relie deux sommets de même couleur. Les deux contrôles portent sur la même information, lue une fois dans le temps et une fois dans le graphe.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapideon peut se reprendre

1.« Le problème est NP-complet » signifie…

2.Sur un graphe d'intervalles, le nombre minimal de serveurs est…

3.Colorer un graphe quelconque avec un nombre minimal de couleurs est NP-complet, et pourtant le chapitre le fait en temps linéaire. Pourquoi ?

4.Un graphe est parfait quand…

5.L'algorithme glouton de coloration donne un résultat qui dépend de l'ordre des sommets. Comment obtenir l'optimum sur un graphe d'intervalles ?

Exercices type

Un graphe a 6 sommets de degré 3. Combien d'arêtes ? Un graphe à 5 sommets de degré 3 existe-t-il ?

Par le lemme des poignées de main, $\sum d(v) = 2m$ , donc $6 \times 3 = 18 = 2m$ et $m = 9$ .

Pour 5 sommets de degré 3 : $5 \times 3 = 15$ , qui devrait valoir $2m$ , or 15 est impair. Un tel graphe n'existe pas.

C'est le schéma de preuve d'impossibilité le plus court de toute la théorie des graphes : la somme des degrés est toujours paire.

Quelle structure de données pour un réseau social de 10⁹ utilisateurs ayant chacun ~200 amis ?

Liste d'adjacence, sans hésitation.

La matrice demanderait $(10^9)^2 = 10^{18}$ cases, soit 125 pétaoctets même à un bit par case : matériellement impossible.

La liste stocke $m = 10^9 \times 200 / 2 = 10^{11}$ arêtes. Chacune apparaît chez ses deux extrémités, soit $2 \times 10^{11}$ identifiants ; à 8 octets l'identifiant, cela fait 1,6 téraoctet : grand, mais réel.

Le rapport entre le nombre de cases de la matrice et le nombre d'arêtes est de $10^7$  : le graphe est extrêmement creux, et c'est le cas de tous les graphes réels de grande taille.

Combien de couleurs faut-il pour un cycle à 5 sommets ? à 6 sommets ?

Cycle de longueur paire (6 sommets) : $\chi = 2$ . On alterne les deux couleurs le long du cycle, et l'alternance retombe juste au bouclage.

Cycle de longueur impaire (5 sommets) : $\chi = 3$ . L'alternance échoue au dernier sommet, qui se retrouve voisin de deux couleurs différentes ; une troisième est indispensable.

Résultat général : un graphe est biparti (donc 2-coloriable) si et seulement s'il ne contient aucun cycle impair. Et un BFS le détecte en $O(n + m)$ , en colorant par parité de distance et en vérifiant qu'aucune arête ne relie deux sommets de même parité.

Les deux cas, côte à côte. Sur le cycle de longueur paire, l'alternance se referme proprement.

Graphe non orienté4 sommets, 4 arêteschemin mis en évidence

Un cycle de longueur paire. En suivant le chemin surligné et en alternant deux couleurs, A et C en reçoivent une, B et D l'autre : le retour sur A tombe juste.

Sur le cycle de longueur impaire, elle échoue : en revenant au départ, le dernier sommet se retrouve voisin d'un sommet de la même couleur que lui.

Graphe non orienté5 sommets, 5 arêteschemin mis en évidence

Un cycle de longueur impaire. La même alternance donne A, C puis E d'un côté, B et D de l'autre ; or E touche A, et tous deux auraient la même couleur.

Le geste à retenir vaut pour les deux figures : parcourir le cycle en alternant, puis regarder uniquement la dernière arête, celle qui referme la boucle. C'est elle, et elle seule, qui décide si deux couleurs suffisent.

On remarquera au passage que le cycle impair n'est pas parfait, puisque $\omega = 2$ mais $\chi = 3$ .

Cinq tâches : T1 sur

[0, 3)

, T2 sur

[1, 4)

, T3 sur

[2, 5)

, T4 sur

[4, 7)

, T5 sur

[6, 9)

. Combien de serveurs ?

Chevauchements : T1-T2 ( $\max(0, 1) = 1 < \min(3, 4) = 3$ ✓), T1-T3 ( $2 < 3$ ✓), T2-T3 ( $2 < 4$ ✓), T3-T4 ( $4 < 5$ ✓), T4-T5 ( $6 < 7$ ✓). T2-T4 : $\max(1, 4) = 4 < \min(4, 7) = 4$ est faux, elles ne se chevauchent pas.

À l'instant $t = 2$ , trois tâches tournent : T1, T2, T3. C'est une clique de taille 3, donc $\chi \geq 3$ .

Coloration : T1→0, T2→1, T3→2, T4→0, T5→1. Trois couleurs suffisent, donc $\chi = 3$  : trois serveurs.

Les deux étapes sont indispensables : la clique donne la borne inférieure, la coloration la borne supérieure.

Pourquoi la coloration est-elle facile sur un graphe d'intervalles alors qu'elle est NP-complète en général ?

Parce qu'un graphe d'intervalles est cordal, donc parfait : $\chi = \omega$ sur lui et sur tous ses sous-graphes induits. Le nombre chromatique se lit alors directement comme le recouvrement maximal des intervalles, sans rien explorer.

Et LexBFS fournit en temps linéaire un ordre pour lequel l'algorithme glouton atteint cette borne. On obtient donc l'optimum en $O(n + m)$ .

Le point de méthode, transposable : la NP-complétude est une propriété du problème général. Reconnaître que l'instance appartient à une famille structurée peut la ramener au domaine du facile, et c'est presque toujours plus rentable que d'optimiser un algorithme exponentiel.

L'algorithme glouton peut-il donner un résultat très éloigné de l'optimum ?

Oui, arbitrairement. Il existe des graphes bipartis (donc $\chi = 2$ ) sur lesquels un ordre bien choisi force le glouton à utiliser $n/2$ couleurs.

Deux garanties partielles seulement. Le glouton n'utilise jamais plus de $\Delta + 1$ couleurs, où $\Delta$ est le degré maximal. Et il existe toujours un ordre pour lequel il atteint $\chi$ , mais le trouver est aussi difficile que le problème de départ.

D'où les heuristiques d'ordre, comme Welsh-Powell qui trie les sommets par degré décroissant : souvent bien meilleure que l'ordre arbitraire, sans aucune garantie d'optimalité. Sur les graphes cordaux, en revanche, LexBFS donne cette garantie.

La méthode

Dire ce que sont les sommets et ce que sont les arêtes, en français, avant tout dessin. « Un sommet = une tâche ; une arête = deux tâches qui se chevauchent. »
Décider orienté ou non en testant si la relation est symétrique.
Choisir la représentation selon la densité : liste d'adjacence pour un graphe creux, matrice pour un graphe dense ou un calcul de chemins.
Vérifier le lemme des poignées de main : la somme des degrés doit valoir $2m$ .
Pour colorer, chercher d'abord une clique : elle donne la borne inférieure, et souvent la réponse.
Encadrer $\chi$  : une clique de taille $k$ puis une coloration à $k$ couleurs. Les deux, sinon rien n'est prouvé.
Repérer la famille du graphe. Intervalles, cordal, biparti, arbre : chacune a un algorithme exact rapide.
Contrôler la coloration en parcourant les arêtes : aucune ne doit relier deux sommets de même couleur.

Synthèse

$G = (V, E)$ , $n$ sommets, $m$ arêtes. Orienté si la relation n'est pas symétrique.
Lemme des poignées de main : $\sum d(v) = 2m$ , donc le nombre de sommets de degré impair est pair.
Chaîne, cycle, connexité. Un arbre est connexe sans cycle et a $n - 1$ arêtes.
Un sous-graphe induit emporte toutes les arêtes entre les sommets retenus.
Clique : sommets deux à deux adjacents. $\omega (G)$ est la taille de la plus grande.
Représentations : liste d'adjacence $O(n+m)$ pour un graphe creux, matrice $O(n^2)$ pour un graphe dense. $A^k$ compte les chaînes de longueur $k$ .
BFS (file) donne les distances ; DFS (pile) donne la structure. Les deux en $\Theta (n + m)$ .
Coloration : deux voisins de couleurs différentes. $\chi (G)$ est le minimum de couleurs.
$\chi (G) \geq \omega (G)$  : la clique minore toujours. Pour prouver l'optimalité, exhiber une clique et une coloration.
Déterminer $\chi$ est NP-complet en général, mais pas sur des familles structurées.
Glouton : $O(n + m)$ , toujours valide, optimal seulement pour un bon ordre.
Intervalles ⟹ cordal ⟹ parfait ⟹ $\chi = \omega$ . LexBFS donne l'ordre qui rend le glouton optimal.
Ordonnancement : une tâche = un sommet, un chevauchement = une arête, une couleur = un serveur. Chevauchement si $\max(\text{débuts}) < \min(\text{fins})$ .

Et ensuite

Ce chapitre referme le parcours Sciences appliquées. Les sept chapitres auront tourné autour d'un même geste : chercher la quantité, ou la représentation, qui rend une question calculable. Un reste modulo 4 à la place d'un arbre de parties, une droite à la place d'un nuage de points, une loi continue à la place d'un fichier de mesures, la notation de Landau à la place d'un chronomètre, un ordre d'élimination à la place d'un essai-erreur.

Chercher l'invariant avant de dérouler : c'est le réflexe que ce parcours voulait installer.

Ce que ce chapitre apporte

Vocabulaire

Degré

Chemins, cycles, connexité

Sous-graphes et cliques

Représenter un graphe en machine

Parcourir un graphe

Coloration et nombre chromatique

Colorier d'abord, on expliquera après

Un problème NP-complet

L'algorithme glouton

L'ordre décide de tout

Vérification

Un cas complet : planifier des tâches

Graphes cordaux, graphes parfaits, LexBFS

Exercices type

La méthode

Synthèse

Et ensuite

Mettre en pratique

Théorie des graphes : parcours, coloration et ordonnancement

Ce que ce chapitre apporte

Vocabulaire

Degré

Chemins, cycles, connexité

Sous-graphes et cliques

Représenter un graphe en machine

Parcourir un graphe

Coloration et nombre chromatique

Colorier d'abord, on expliquera après

Un problème NP-complet

L'algorithme glouton

L'ordre décide de tout

Vérification

Un cas complet : planifier des tâches

Graphes cordaux, graphes parfaits, LexBFS

Exercices type

La méthode

Synthèse

Et ensuite

Mettre en pratique

Un cas complet : planifier des tâches