Théorie des graphes : parcours, coloration et ordonnancement

Où on va

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 cours complet est ailleurs

Ce chapitre reprend l'essentiel en un seul endroit. Le parcours Théorie des graphes les traite en neuf chapitres, avec les dessins, les parcours animés, les arbres couvrants, les plus courts chemins, les flots et les couplages.
Si une notion 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.

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. 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ᵏ 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 : argument classique en devoir, et impossible à formuler aussi simplement avec une liste d'adjacence.

Graphe non orienté6 sommets, 7 arêtes

Voici le graphe manipulé dans le bloc ci-dessous : six sommets, sept arêtes, deux triangles.

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, contre $\Theta (n^2)$ avec une matrice, puisqu'il faut alors examiner toute une ligne pour trouver les voisins d'un sommet.

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.

Graphe non orienté7 sommets, 8 arêtes

0 / 7

Rien n'est encore visité.

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.

Vérification rapidesans note, on peut se reprendre

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

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

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

Ne sors pas 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

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

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, et c'est la structure de preuve attendue :
1. Exhiber une clique de taille k : cela prouve χ ≥ k ;
2. Exhiber une coloration à k couleurs : cela prouve χ ≤ k.
Les deux ensemble donnent χ = 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 : 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, 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

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.

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

ils se chevauchent ⟺ max(d₁, d₂) < min(f₁, f₂)

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

On serait tenté d'écrire « d₁ < f₂ et d₂ < f₁ », ou pire, d'énumérer les positions relatives des deux intervalles. La forme max(début) < min(fin) 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. Utilise l'inégalité 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 : pour un graphe où 3 suffisent, comme le prouve la clique de taille 3. 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

Graphes cordaux, graphes parfaits, LexBFS

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.

La chaîne d'implications qui débloque le problème :

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.

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 est un ordre parfait d'élimination : l'algorithme glouton appliqué dans cet ordre donne une coloration optimale, en temps linéaire.

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.

main.py

Sortie

>_ Prêt à exécuter…

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 un exaoctet même à un bit par case : matériellement impossible.

La liste stocke $m = 10^9 \times 200 / 2 = 10^{11}$ arêtes, soit de l'ordre de quelques téraoctets : grand, mais réel.

Le rapport de taille 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é.

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

Cinq tâches : $(0{,}3)$, $(1{,}4)$, $(2{,}5)$, $(4{,}7)$, $(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

Dis 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écide orienté ou non en testant si la relation est symétrique.
Choisis la représentation selon la densité : liste d'adjacence pour un graphe creux, matrice pour un graphe dense ou un calcul de chemins.
Vérifie le lemme des poignées de main : la somme des degrés doit valoir $2m$ .
Pour colorer, cherche d'abord une clique : elle donne la borne inférieure, et souvent la réponse.
Encadre $\chi$  : une clique de taille $k$ puis une coloration à $k$ couleurs. Les deux, sinon rien n'est prouvé.
Repère la famille du graphe. Intervalles, cordal, biparti, arbre : chacune a un algorithme exact rapide.
Contrôle la coloration en parcourant les arêtes : aucune ne doit relier deux sommets de même couleur.

En résumé

$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ᵏ 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. max(début) < min(fin).

Et ensuite ? Le bloc est bouclé. Six problèmes, six outils : la théorie des jeux pour décider face à quelqu'un, les probabilités pour chiffrer un risque, les statistiques pour lire des données, la complexité pour choisir un algorithme, l'arithmétique pour protéger un message, les graphes pour modéliser des relations. Ce qui se répète d'un chapitre à l'autre, et qui est en réalité le vrai objet du bloc, c'est le passage de l'énoncé en français au modèle mathématique, puis au programme qui le résout.

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

Un problème NP-complet

L'algorithme glouton

Un cas complet : planifier des tâches

Graphes cordaux, graphes parfaits, LexBFS

Exercices type

La méthode

En résumé

Un cas complet : planifier des tâches