Théorie des graphes : parcours, coloration et ordonnancement

Un graphe, c'est une relation

Le relevé fait sur le site dit quelles bornes sont à portée l'une de l'autre. Il compte onze paires : A et B, A et C, A et D, A et E, B et C, B et F, C et D, C et F, D et E, E et G, G et H. Rien d'autre n'est utile aux deux questions : ni la position exacte des bornes, ni la distance qui les sépare. Un point par borne, un trait par paire à portée, et le réseau tient dans un dessin.

Le graphe des bornes est simple et non orienté : $n = 8$, $m = 11$.

Le vocabulaire, sur le graphe des bornes

Degré

Le degré $d(v)$ d'un sommet est son nombre de voisins. Sur le graphe des bornes : A et C ont 4 voisins, B, D et E en ont 3, F et G 2, et H un seul.

Sur le graphe des bornes, $4 + 3 + 4 + 3 + 3 + 2 + 2 + 1 = 22 = 2 \times 11$. Conséquence immédiate : la somme des degrés étant paire, le nombre de sommets de degré impair est pair. Ils sont quatre ici, B, D, E et H. C'est le premier outil pour prouver qu'un graphe ne peut pas exister : cinq sommets de degré 3 donneraient une somme de 15, impaire.

Chemins, cycles, circuits

Certains ouvrages disent chaîne dans un graphe non orienté et réservent « chemin » aux graphes orientés. Ce site dit chemin dans les deux cas, et précise quand le sens compte.

Connexité

Un graphe est connexe si deux sommets quelconques sont reliés par un chemin. Sinon, il se décompose en composantes connexes, ses morceaux d'un seul tenant. Le graphe des bornes est connexe ; il cesse de l'être si la borne E tombe en panne.

Sous-graphes et cliques

Un sous-graphe s'obtient en gardant une partie des sommets et une partie des arêtes qui les relient. Le sous-graphe induit par un ensemble de sommets garde toutes les arêtes entre eux : on choisit les sommets, les arêtes viennent avec. Sur les bornes A, B, C et F, le sous-graphe induit a cinq arêtes, A-B, A-C, B-C, B-F et C-F ; ne garder que A-B et B-F donne un sous-graphe, qui n'est pas induit.

Le graphe des bornes contient quatre triangles, A, B, C ; A, C, D ; A, D, E ; B, C, F. Aucun groupe de quatre bornes n'est relié deux à deux : $\omega = 3$.

Quelques familles

Représenter un graphe en machine

Trois lectures du même objet, et trois usages. La matrice répond en une case à « ces deux bornes sont-elles voisines ? », et elle est symétrique, puisqu'une arête allume les cases $(i, j)$ et $(j, i)$. La liste donne d'un coup tous les voisins d'une borne, ce que la matrice ne fait qu'en lisant une ligne entière. La liste d'arêtes est la plus compacte, et c'est celle qu'on écrit dans un fichier.

Le bloc ci-dessous construit la matrice à partir de la liste d'arêtes, et en tire deux réponses.

La liste d'adjacence, elle, est à écrire.

Une bibliothèque fait tout cela d'un coup. networkx construit le graphe à partir de la liste d'arêtes, et sait ensuite en donner les voisins, les degrés, la matrice, les distances ou les composantes. Pour un très grand graphe, scipy.sparse range une matrice en ne gardant que ses cases non nulles.

Comment choisir. Un graphe est creux quand $m$ est de l'ordre de $n$, dense quand il approche $n(n - 1)/2$. Les grands graphes réels sont presque toujours creux : un réseau routier, un réseau social, les liaisons d'un réseau de capteurs. Pour eux, la liste d'adjacence gagne sur tous les tableaux, en mémoire et en temps : trouver les voisins d'un sommet y coûte son degré, quand la matrice oblige à lire ses $n$ cases. La matrice se justifie sur un graphe dense, ou pour répondre très souvent à « ces deux sommets sont-ils voisins ? ».

Parcourir un graphe

Première question du chapitre : un message parti du poste de garde passe-t-il par beaucoup de bornes avant d'atteindre la plus lointaine ? Y répondre demande de visiter les bornes dans un ordre réfléchi, en partant de A. C'est ce que fait un parcours.

Le parcours en largeur, déroulé depuis le poste de garde.

Les bornes s'allument par vagues, et chaque vague est à une arête de plus de A : B, C, D et E à un relais, F et G à deux, H à trois. Le rang de la vague où une borne s'allume est sa distance au poste de garde, en nombre de relais, et c'est pourquoi le parcours en largeur donne les plus courts chemins. La réponse à la première moitié de la question est là : trois relais suffisent pour atteindre H, et aucun chemin plus court n'existe.

Le même graphe, parcouru par une figure qui calcule elle-même le parcours ; la réserve s'y affiche en jetons à chaque pas.

Avec la pile, le parcours file de B vers C, puis D, E, G et H, et ne revient chercher F qu'à la fin : il suit chaque branche jusqu'au bout. C'est ce qui le rend commode pour délimiter un morceau du graphe. Pour la seconde moitié de la question, il suffit de retirer la borne en panne et de lancer un parcours depuis A : les bornes qu'il atteint restent joignables, les autres sont coupées. Sur ce réseau, seules deux pannes coupent quelque chose : celle de E, qui isole G et H, et celle de G, qui isole H. E et G sont des points de passage obligés.

Les deux parcours visitent chaque sommet une fois et examinent chaque arête deux fois, depuis chacune de ses extrémités : avec des listes d'adjacence, leur temps est en $O(n + m)$. Avec une matrice, il passe à $O(n^2)$, puisqu'il faut lire toute une ligne pour trouver les voisins d'un sommet.

Le parcours en largeur, écrit en Python sur la liste d'adjacence. Le second appel répond à la question de la panne.

Remplacer deque et popleft par une liste et pop() change la file en pile : le même code devient un parcours en profondeur, à un détail près, que le chapitre sur les parcours explique avec les composantes connexes et la détection de cycle.

Quand les arêtes portent un poids : Dijkstra et Prim. Deux algorithmes célèbres sont des parcours dont la réserve est une file de priorité, qui rend à chaque pas le sommet le plus avantageux plutôt que le plus ancien.

L'algorithme de Dijkstra calcule les plus courts chemins dans un graphe pondéré, aux poids positifs : il sort à chaque pas le sommet le plus proche du départ parmi ceux qu'il a déjà atteints. C'est le parcours en largeur, quand les arêtes n'ont plus toutes la même longueur. Voir le chapitre sur les plus courts chemins.

L'algorithme de Prim construit un arbre couvrant de poids minimal : relier toutes les bornes par des câbles, de longueur totale la plus petite possible. Il part d'un sommet, et ajoute à chaque pas la liaison la moins chère qui atteint un sommet neuf. Voir le chapitre sur les arbres.

Colorier un graphe

Seconde question du chapitre. Deux bornes à portée l'une de l'autre se brouillent si elles émettent sur le même canal, et chaque canal supplémentaire est une fréquence de plus à réserver. Attribuer un canal à chaque borne, c'est donner une couleur à chaque sommet, avec une seule règle : deux sommets reliés n'ont jamais la même couleur.

Colorier d'abord, on expliquera après

Deux choses se remarquent en jouant. L'ordre change le résultat : trois teintes dans l'ordre alphabétique, quatre dans le second, sur le même graphe et avec la même règle. Et une fois trois teintes trouvées, rien ne dit encore qu'on ne peut pas descendre à deux. Avoir réussi avec trois prouve qu'il en suffit trois, pas qu'il en faut trois.

La clique donne le minimum

Comment on prouve qu'une coloration est optimale. 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$. Une coloration seule ne prouve jamais l'optimalité : elle ne fournit qu'une majoration.

Un problème réputé difficile

Vérifier, justement, s'écrit en quelques lignes.

Une seule boucle sur les arêtes : la vérification est en $O(m)$, ce qui place la coloration dans NP.

L'algorithme glouton

La première ligne de la boucle relève les couleurs interdites ; la seconde prend la première qui reste. Les voisins pas encore coloriés n'y figurent pas : l'algorithme décide sans rien savoir de ce qui vient après. Il est en $O(n + m)$ et produit toujours une coloration valide, mais pas forcément optimale.

Le glouton sur le graphe des bornes, dans l'ordre alphabétique : chaque couleur apparaît à l'étape qui la donne.

L'ordre décide de tout

Le plus petit exemple tient en quatre sommets alignés, A-B-C-D. Deux couleurs suffisent : il n'y a aucun triangle, et l'alternance 0, 1, 0, 1 convient. La figure propose deux ordres ; on peut aussi composer le sien en cliquant les sommets.

Dans le second ordre, A et D, qui ne sont pas voisins, prennent tous deux la couleur 0. B, voisin de A, prend la 1. C arrive enfin entre B, en 1, et D, en 0 : il lui faut une troisième couleur. Aucune décision n'était fausse sur le moment ; c'est leur enchaînement qui coûte.

Le même effet, sur le graphe des bornes. Choisir un ordre, le dérouler pas à pas, puis comparer le nombre de couleurs à celui de la plus grande clique ; ou cliquer les bornes dans l'ordre de son choix.

L'écart n'est pas toujours d'une seule couleur. Il existe des graphes bipartis, colorables en deux couleurs, sur lesquels un ordre défavorable fait employer au glouton autant de couleurs que la moitié du nombre de sommets.

Graphes cordaux, graphes parfaits et LexBFS

Graphe cordal

Le carré est le plus petit graphe qui ne soit pas cordal : un cycle de quatre sommets, sans corde. Ajouter une diagonale le coupe en deux triangles, et le rend cordal.

Le graphe des bornes est cordal. Le cycle A, B, F, C, A a la corde B-C ; le cycle A, B, C, D, E, A a les cordes A-C et A-D ; et ainsi de suite pour chacun. Vérifier cycle par cycle serait long, et LexBFS, plus bas, fera ce contrôle d'un seul passage. Deux familles sont cordales d'office : les arbres, qui n'ont aucun cycle, et les graphes d'intervalles, obtenus en posant des segments sur une droite et en reliant deux segments qui se recouvrent.

Graphe parfait

Les sous-graphes induits ne sont pas un détail. Le cycle de cinq sommets n'a aucun triangle, $\omega = 2$, mais demande trois couleurs, $\chi = 3$ : il n'est pas parfait. Le coller à côté d'un triangle donne un graphe où $\chi = 3$ et $\omega = 3$, égalité trompeuse : le sous-graphe induit par le cycle garde son écart, et le graphe entier n'est pas parfait non plus.

Pourquoi un graphe cordal est parfait

Le raisonnement tient en trois temps, et il n'admet qu'un résultat.

1. Le glouton atteint $\omega$. Colorier dans l'ordre inverse d'un ordre parfait d'élimination : quand vient le tour d'un sommet, ses voisins déjà coloriés sont ceux qui le suivaient dans l'ordre d'élimination, donc deux à deux reliés. Avec lui, ils forment une clique, de taille au plus $\omega$ : ils sont au plus $\omega - 1$, ne lui interdisent qu'au plus $\omega - 1$ couleurs, et le glouton n'emploie jamais plus de $\omega$ couleurs. Comme il en faut au moins $\omega$, $\chi = \omega$.
2. Un sous-graphe induit d'un graphe cordal est cordal. Un cycle sans corde dans le sous-graphe serait aussi sans corde dans le graphe entier, puisque le sous-graphe induit garde toutes les arêtes entre ses sommets.
3. Donc l'égalité $\chi = \omega$ vaut pour le graphe et pour chacun de ses sous-graphes induits : le graphe est parfait.

La chaîne à retenir : cordal ⟹ parfait ⟹ $\chi = \omega$, et un ordre d'élimination rend le glouton optimal. Reste à trouver cet ordre.

LexBFS

Les étiquettes se comparent comme les mots d'un dictionnaire, numéro par numéro, et non comme des nombres. On compare les premiers numéros ; en cas d'égalité, les suivants. Ainsi $(4)$ l'emporte sur $(3, 2, 1)$, puisque 4 dépasse 3 dès le premier numéro, et $(3, 2)$ l'emporte sur $(3)$, qu'elle prolonge. Additionner les numéros, ou lire $(3, 2)$ comme « 32 », donnerait d'autres choix.

La mise à jour des étiquettes se suit sur quatre sommets : un triangle A, B, C, et un sommet D accroché à C.

Sur le graphe des bornes, le même déroulé donne ceci.

L'ordre de choix est H, G, E, D, A, C, B, F. Le contrôle se lit sur cet ordre : pour chaque sommet, ses voisins choisis avant lui sont-ils deux à deux reliés ? Pour A, ce sont E et D, reliés ; pour C, A et D, reliés ; pour B, A et C ; pour F, C et B ; les autres n'en ont qu'un. Le contrôle passe : le graphe des bornes est cordal. Le glouton dans cet ordre donne H 0, G 1, E 0, D 1, A 2, C 0, B 1, F 2, soit trois couleurs, et le triangle A, B, C prouve que c'est le minimum. Le bouton « LexBFS » de la figure du glouton, plus haut, déroule exactement cet ordre.

Bien programmé, LexBFS est en $O(n + m)$, comme le glouton : sur un graphe cordal, une coloration optimale s'obtient donc en temps linéaire, alors que le problème est NP-complet sur un graphe quelconque. C'est la structure du graphe, et non la puissance de calcul, qui fait la différence.

Ordonnancer : quand les couleurs sont des créneaux

Deux sortes de contraintes reviennent sans cesse, et elles ne donnent pas le même graphe.

• L'incompatibilité : deux tâches ne peuvent pas avoir lieu en même temps. La relation est symétrique : ce sont des arêtes, et choisir les créneaux revient à colorier, une couleur par créneau.
• La précédence : une tâche doit être finie avant qu'une autre commence. La relation a un sens : ce sont des arcs, et le graphe est orienté.

Sur le réseau du chapitre, la première sorte se rencontre à la maintenance. Chaque borne doit être arrêtée une demi-journée pour sa révision, et deux bornes à portée l'une de l'autre ne peuvent pas l'être ensemble : la zone qu'elles se partagent ne serait plus couverte. Combien de demi-journées faut-il au minimum ? C'est le même graphe, et la même réponse : $\chi = 3$. La coloration de la figure donne le planning, A, F et G la première demi-journée, B, D et H la deuxième, C et E la troisième, et le triangle A, B, C prouve qu'on ne peut pas faire en deux.

La seconde sorte se rencontre à l'installation d'une nouvelle borne.

Un tel graphe se lit autrement qu'un graphe de conflits. La durée minimale du chantier est la longueur du plus long chemin, en additionnant les durées : c'est le chemin critique de la méthode PERT, que le chapitre sur les graphes orientés calcule avec les dates au plus tôt et au plus tard. Et un circuit y signale une erreur de planification : si « tester » devait aussi précéder « tirer », aucune tâche du circuit ne pourrait commencer la première.

Les grandes familles de problèmes d'ordonnancement.

• La gestion de projet : des tâches liées par des précédences, et une date de fin à rendre la plus proche possible (méthode PERT, chemin critique).
• Les problèmes d'atelier, où des pièces passent sur plusieurs machines. Dans un flow-shop, toutes les pièces suivent la même séquence de machines ; dans un job-shop, chaque pièce a sa propre séquence, imposée ; dans un open-shop, l'ordre de passage sur les machines est libre.
• L'ordonnancement des processus d'un système d'exploitation : un processeur, ressource unique, partagé entre les programmes qui veulent s'exécuter. Voir le chapitre sur le multitâche.

Avant de colorier, se demander si les contraintes sont des incompatibilités ou des précédences : un planning de chantier où « les fondations avant les murs » se traduit par des arcs, pas par des couleurs.

Ce que le réseau décide

Les deux questions du début ont maintenant leur réponse.

Un message du poste de garde atteint toute borne en trois relais au plus, et H, la plus lointaine, exige bien ces trois relais : le parcours en largeur l'a montré par vagues. Deux pannes seulement coupent le réseau, celle de E, qui isole G et H, et celle de G, qui isole H. Ce sont les deux bornes à doubler, si la couverture doit résister à une panne.

Trois canaux suffisent, et il en faut trois. A, F et G sur le premier, B, D et H sur le deuxième, C et E sur le troisième : aucune paire à portée ne partage un canal. Et le triangle A, B, C prouve qu'on ne pourrait pas faire avec deux. Le réseau étant cordal, LexBFS et le glouton auraient trouvé ce minimum seuls, sans essai ; et le même raisonnement donne, sans rien changer, le planning de maintenance en trois demi-journées.

La méthode

1. Dire ce que sont les sommets et ce que sont les liens, en français, avant tout dessin : « un sommet = une borne ; une arête = deux bornes à portée ».
2. Décider orienté ou non en testant si la relation est symétrique.
3. Choisir l'écriture selon la densité : liste d'adjacence pour un graphe creux, matrice pour un graphe dense.
4. Vérifier le lemme des poignées de main : la somme des degrés doit valoir $2m$.
5. Pour des distances en nombre de liens, un parcours en largeur ; pour les morceaux du graphe, n'importe quel parcours, souvent en profondeur ; pour des liens pondérés, Dijkstra.
6. Pour colorier, chercher d'abord une clique : elle donne la borne inférieure, et souvent la réponse.
7. Encadrer $\chi$ : une clique de taille $k$ puis une coloration à $k$ couleurs. Les deux, sinon rien n'est prouvé.
8. Regarder la structure : un graphe cordal se colore de façon optimale dans l'ordre de LexBFS, un graphe biparti en deux couleurs ; sinon, le glouton ne donne qu'une majoration.

Mettre en pratique