Graphes: représentations et parcours

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• énoncer le vocabulaire des graphes — orienté ou non, pondéré, chemin, cycle, connexité, arbre, graphe orienté acyclique — et reconnaître, dans un problème formulé en français, le graphe qui s'y cache;
• choisir entre liste d'adjacence et matrice d'adjacence en justifiant votre choix par l'espace occupé et par le coût des opérations que votre programme fait le plus souvent;
• écrire le parcours en largeur et le parcours en profondeur, dire ce que chacun garantit, et démontrer que le premier calcule la distance en arêtes;
• lire un parcours en profondeur à travers ses dates de découverte et de fin, classer chaque arête en arête de liaison ou de retour, et en déduire la présence ou l'absence d'un circuit;
• calculer les composantes connexes d'un graphe, trier topologiquement un graphe orienté acyclique par les deux méthodes usuelles, et tester la bipartition par coloriage;
• annoncer le coût de chacun de ces algorithmes en fonction de $n$ et de $m$, et dire quelle opération vous avez comptée.

Trois problèmes, un seul objet

Le plan du métro, les dépendances, les relations

Voici trois questions qui n'ont rien à voir entre elles.

Première question. Un plan de transports publics relie une centaine d'arrêts. On voudrait savoir, depuis l'arrêt où l'on se trouve, quel est le plus petit nombre de correspondances pour atteindre chacun des autres arrêts. Pas la durée, pas la distance en kilomètres: le nombre de tronçons empruntés.

Deuxième question. Un projet logiciel se compose de modules, dont certains doivent être compilés avant d'autres. On voudrait produire un ordre de compilation qui respecte toutes ces contraintes — et, si aucun ordre ne convient, on voudrait savoir pourquoi, c'est-à-dire exhiber le cercle vicieux de dépendances qui rend le projet incompilable.

Troisième question. Dans un ensemble de personnes reliées deux à deux par une relation symétrique — elles se connaissent, elles ont cosigné un article, elles ont échangé un message —, on voudrait découper l'ensemble en groupes tels que deux personnes d'un même groupe soient reliées par une suite de relations, et deux personnes de groupes différents ne le soient jamais.

Ces trois questions portent sur des objets sans rapport: des arrêts de bus, des fichiers sources, des individus. Elles se ramènent pourtant au même objet mathématique — un ensemble de points et un ensemble de liens entre ces points — et à trois algorithmes qui tiennent chacun en une quinzaine de lignes de Python. C'est là toute la force de la théorie des graphes, et c'est ce qui justifie qu'on lui consacre trois chapitres de ce cours: vous n'apprenez pas trois algorithmes, vous apprenez un langage dans lequel des centaines de problèmes se formulent.

Le présent chapitre fixe ce langage, les deux façons de ranger un graphe en mémoire, et les deux parcours dont tout le reste découle. Le chapitre 7 y ajoutera des poids et cherchera les chemins les plus légers; le chapitre 8 cherchera à relier tous les sommets au moindre coût.

Le vocabulaire, une fois pour toutes

Deux conventions valent pour tout ce cours. D'abord, nos graphes sont simples: pas de boucle d'un sommet sur lui-même, pas de deux arêtes entre les mêmes sommets. Ensuite, le nombre d'arêtes d'un graphe non orienté simple est encadré par

Cet encadrement est l'origine de tout le reste du chapitre: entre $0$ et $\Theta (n^2)$ il y a un facteur $n$, et un algorithme dont le coût s'écrit $\Theta (n+m)$ n'a pas du tout le même comportement selon qu'on se trouve à gauche ou à droite de cette fourchette. On appelle creux un graphe dont le nombre d'arêtes reste de l'ordre de $n$, et dense un graphe dont le nombre d'arêtes est de l'ordre de $n^2$.

Démonstration. Comptons de deux façons le nombre de couples $(u,e)$ où $u$ est un sommet, $e$ une arête, et $u$ une extrémité de $e$. En regroupant par sommet, chaque sommet $u$ apparaît dans exactement $\mathrm{deg}(u)$ tels couples, par définition du degré: le total vaut ${\sum }_u\mathrm{deg}(u)$. En regroupant par arête, chaque arête a exactement deux extrémités distinctes — le graphe est simple, donc —, et fournit donc exactement deux couples: le total vaut . Les deux comptes portent sur le même ensemble fini, donc ils sont égaux.

Pour la seconde affirmation, séparons la somme selon la parité des degrés:

La première somme est paire comme somme d'entiers pairs, et $2m$ est pair; donc la seconde somme est paire. Or une somme d'entiers impairs est paire si et seulement si le nombre de termes est pair. Le nombre de sommets de degré impair est donc pair. $\square$

Ce lemme n'est pas une curiosité: c'est la raison pour laquelle une liste d'adjacence occupe $2m$ maillons et non $m$, et c'est lui qui fait apparaître le terme $m$ — et non $2m$ — dans le coût $\Theta (n+m)$ des parcours.

Que la relation d'accessibilité soit une relation d'équivalence mérite la vérification, parce qu'elle justifie le mot «composante»: elle est réflexive (le chemin de longueur 0), symétrique dans le cas non orienté (on parcourt le chemin à l'envers), et transitive (on met bout à bout). Dans un graphe orienté, la symétrie tombe, et c'est pourquoi la notion correspondante — la forte connexité — est plus délicate; nous ne l'abordons pas ici.

Un mot sur la pondération, qui ne servira vraiment qu'aux deux chapitres suivants. Un graphe est pondéré lorsqu'une fonction $w$ associe à chaque arête un nombre, son poids: une durée, une distance, une capacité, un coût. Le présent chapitre n'utilise pas les poids — la distance $\delta (s,v)$ y compte des arêtes, pas des kilomètres —, mais le graphe sur lequel nous travaillons les porte, parce que les chapitres 7 et 8 en auront besoin et que c'est le même graphe.

Le graphe témoin du cours

Tout ce chapitre, tout le chapitre 7 et tout le chapitre 8 travaillent sur le même petit graphe. Ses sept sommets sont nommés de $A$ à $G$, ses onze arêtes portent les poids de la figure 6.1, et son dessin est fixé une fois pour toutes: $A$ est au même endroit dans les trois chapitres. Ces sept sommets ne représentent rien de réel; ce sont des données fictives, choisies pour rester identiques d'un chapitre à l'autre, de sorte que vous puissiez comparer les traces des algorithmes sans avoir à réapprendre la figure.

Relevons ce que la figure donne, puisque nous nous en servirons constamment. Il y a $n=7$ sommets et $m=11$ arêtes. Les degrés valent 2 pour $A$, 3 pour $B$, 4 pour $C$, 4 pour $D$, 4 pour $E$, 3 pour $F$ et 2 pour $G$: leur somme fait $2+3+4+4+4+3+2=22=2\times 11$, ce qui vérifie le théorème 6.1 sur ce cas particulier. Le graphe est connexe. Il n'est pas un arbre, puisqu'un arbre à sept sommets aurait six arêtes et qu'il en a onze. Enfin il est au sens relatif: contre un maximum de , soit 52 % des arêtes possibles. À sept sommets la distinction creux/dense n'a évidemment pas de sens; elle en prendra un dès que nous parlerons de cent mille sommets.

Ranger un graphe en mémoire

Deux représentations, deux profils de coût

Un graphe abstrait est un ensemble de paires. Un programme, lui, doit répondre vite à des questions précises: «quels sont les voisins de $u$?», «$u$ et $v$ sont-ils reliés?», «combien d'arêtes en tout?». Les deux représentations classiques répondent bien à des questions différentes, et c'est exactement pour cela qu'il y en a deux.

La liste d'adjacence associe à chaque sommet la liste de ses voisins. En Python, un dictionnaire dont les valeurs sont des listes:

GRAPHE = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D", "F", "G"

Chaque arête $\{u,v\}$ y figure deux fois, une fois dans la liste de $u$ et une fois dans celle de $v$. La structure occupe donc $n$ entrées de dictionnaire et ${\sum }_u\mathrm{deg}(u)=2m$ maillons, soit $7+22=29$ cases pour notre graphe témoin: c'est le lemme des poignées de main qui donne ce chiffre, et c'est ce qui rend l'espace .

La matrice d'adjacence est un tableau $n\times n$ dont la case $(i,j)$ dit si l'arête existe — et, pour un graphe pondéré, quel est son poids:

SOMMETS = ["A", "B", "C", "D", "E", "F", "G"]
INDICE = {s: i for i, s in enumerate(SOMMETS)}
M = [[0] * 7 for _ in range(7)]
for u, v, poids in ARETES:

Pour un graphe non orienté, cette matrice est symétrique et sa diagonale est nulle, puisque nos graphes sont simples. Pour un graphe orienté elle ne l'est pas, et c'est justement ainsi qu'on lit l'orientation dans la matrice. L'espace occupé est $n^2$ cases quel que soit le nombre d'arêtes: 49 cases ici, dont 22 seulement portent une arête.

Le tableau suivant donne le coût de chaque opération élémentaire dans les deux représentations. Toutes ces bornes se lisent directement sur le code: l'opération comptée est l'accès à une case de la structure.

Une seule ligne suffit à faire pencher la balance dans un sens ou dans l'autre, et c'est l'avant-dernière. Un algorithme de graphe typique — un parcours, un plus court chemin, un arbre couvrant — ne teste presque jamais l'existence d'une arête donnée; il énumère les voisins de chaque sommet, l'un après l'autre. Avec une liste d'adjacence, le total de ces énumérations vaut ${\sum }_u\mathrm{deg}(u)=2m$, donc $\Theta (n+m)$ en comptant la visite des sommets sans voisin. Avec une matrice, chaque énumération coûte $\Theta (n)$, qu'il y ait zéro ou $n-1$ voisins, et le total est quoi qu'il arrive.

Quand la matrice gagne-t-elle vraiment?

La matrice gagne dans deux situations, et il faut les nommer précisément plutôt que de dire «quand le graphe est dense».

Premier cas: l'opération dominante est le test d'existence. Un algorithme qui demande cent mille fois «l'arête $\{u,v\}$ existe-t-elle?» sans jamais énumérer de voisinage paiera $\Theta (1)$ par question avec une matrice, et $\Theta (\mathrm{deg}u)$ avec une liste. C'est le profil de certains algorithmes de comptage de triangles ou de tests d'isomorphisme locaux. À noter qu'un dictionnaire d'ensembles — {"A": {"B", "C"}, ...} en Python — offre le test en $O(1)$ en moyenne tout en gardant l'espace $\Theta (n+m)$: c'est souvent le vrai meilleur compromis, et le chapitre 4 explique à quel prix.

Second cas: le graphe est dense. Si $m$ est de l'ordre de $n^2$, alors $\Theta (n+m)=\Theta (n^2)$ et la matrice n'occupe pas plus de place que la liste, tout en étant plus compacte en pratique — un bit par case contre un pointeur et une valeur par maillon.

Le parcours en largeur

L'algorithme et sa file

Le parcours en largeur — breadth-first search, ou BFS — explore le graphe par cercles concentriques autour d'une source $s$: d'abord $s$, puis tous ses voisins, puis tous les voisins de ses voisins non encore vus, et ainsi de suite. La structure qui produit cet ordre est une file: premier entré, premier sorti.

from collections import deque


def parcours_largeur(graphe, source):
    """Distance en aretes depuis source, et pere de chaque sommet atteint."""
    distance = {source: 0}
    pere = {source: None}
    file = deque([source])
    while file:
        u = file.popleft()
        for v in graphe[u]:
            if v not in distance:
                distance[v] =

Trois détails de ce code portent toute la correction de l'algorithme, et il vaut la peine de les nommer.

D'abord, un sommet est marqué au moment où il est enfilé, pas au moment où il est défilé: c'est le test v not in distance qui fait office de marque. Si l'on marquait à la sortie de la file, un sommet ayant plusieurs voisins déjà défilés serait enfilé plusieurs fois, et le parcours cesserait d'être linéaire.

Ensuite, la file est une file et non une pile. deque.popleft() retire en tête en temps $\Theta (1)$; on prendra garde à ne pas écrire list.pop(0), qui décale tout le reste et coûte $\Theta (n)$, transformant silencieusement un algorithme linéaire en algorithme quadratique.

Enfin, pere mémorise par quelle arête chaque sommet a été atteint. L'ensemble de ces arêtes forme l'arbre du parcours en largeur, et nous verrons que le chemin qu'il donne de $s$ à $v$ est un plus court chemin.

Le coût est $\Theta (n+m)$: chaque sommet est enfilé et défilé une fois exactement — d'où le terme $n$ — et la boucle intérieure examine la liste de voisins de chaque sommet défilé une fois exactement, soit ${\sum }_u\mathrm{deg}(u)=2m$ examens d'arêtes en tout. L'opération comptée ici est l'examen d'une arête depuis l'une de ses extrémités, et il y en a exactement $2m$ dans un graphe connexe parcouru en entier.

Le parcours en largeur calcule bien la distance

Il est facile de croire ce résultat sur un dessin et difficile de le démontrer proprement; c'est pourtant le seul énoncé qui justifie qu'on utilise le BFS pour calculer des distances. Nous procédons en deux lemmes puis le théorème. Dans toute cette sous-section, $G=(V,E)$ est un graphe, orienté ou non, $s$ une source, $\delta (s,v)$ la distance en arêtes, et $d[v]$ la valeur que l'algorithme range dans distance[v] — avec la convention $d[v]=+\infty$ tant que $v$ n'est pas marqué.

Démonstration. Si $u$ n'est pas accessible depuis $s$, alors $\delta (s,u)=+\infty$ et l'inégalité est vraie sans rien dire. Sinon, soit $P$ un plus court chemin de $s$ à $u$, de longueur $\delta (s,u)$. En lui ajoutant l'arête $\{u,v\}$ on obtient une marche de à comptant arêtes. Or un plus court chemin est au plus aussi long que n'importe quelle marche joignant les deux mêmes extrémités — toute marche contient un chemin, obtenu en supprimant les portions comprises entre deux passages par un même sommet, ce qui ne peut qu'en raccourcir la longueur. Donc .

Démonstration. Par récurrence sur le nombre d'opérations de file effectuées. Initialement la file ne contient que $s$, et les deux inégalités sont vides ou triviales.

Supposons-les vraies avant une opération. Si l'opération est un défilement, l'ancienne tête $v_1$ disparaît et la nouvelle tête est $v_2$ (ou la file devient vide, cas trivial). La seconde famille d'inégalités subsiste telle quelle. Pour la première, l'hypothèse donne $d[v_r]\le d[v_1]+1\le d[v_2]+1$, la dernière inégalité venant de . La propriété est donc conservée.

Si l'opération est un enfilement, c'est que l'algorithme traite un sommet $u$ qu'il vient de défiler et qu'il découvre un voisin $v$, auquel il donne $d[v]=d[u]+1$. Appliquons l'hypothèse de récurrence à la file telle qu'elle était juste avant le défilement de $u$: $u$ en était alors la tête, donc pour son dernier élément $w$ on avait $d[w]\le d[u]+1$. Or, entre ce défilement et l'enfilement de , les seuls sommets ajoutés sont d'autres voisins de , tous munis eux aussi de la valeur . Le dernier élément de la file actuelle vérifie donc encore , et la suite reste croissante après l'ajout de . Quant à la première inégalité, la nouvelle tête satisfait — elle était derrière dans la file d'avant —, donc . Les deux propriétés sont préservées.

La conséquence annoncée s'ensuit: un sommet enfilé après un autre a une valeur de $d$ au moins aussi grande, et comme une file préserve l'ordre, les défilements se font eux aussi par $d$ croissant. $\square$

Démonstration. Point 1. Un sommet n'est marqué que lorsqu'il est découvert depuis un voisin déjà marqué, et $s$ est marqué d'emblée; une récurrence immédiate sur l'ordre des marquages montre donc que tout sommet marqué est accessible depuis $s$. Réciproquement, supposons qu'un sommet accessible reste non marqué et prenons-en un, disons $v$, de distance $\delta (s,v)$ minimale parmi ceux-là. On a $v\ne s$, donc $\delta (s,v)\ge 1$; soit le sommet qui précède sur un plus court chemin, de sorte que . Par minimalité de , le sommet est marqué, donc enfilé, donc défilé — la boucle ne s'arrête que la file vide. Au moment où est défilé, l'algorithme examine tous ses voisins, dont : si n'était pas encore marqué, il l'est alors. Contradiction.

Point 2. Montrons d'abord $d[v]\ge \delta (s,v)$ pour tout $v$ marqué, par récurrence sur l'ordre des marquages. Pour $s$, $d[s]=0=\delta (s,s)$. Si $v$ est marqué lors du traitement de $u$, alors , la première inégalité par hypothèse de récurrence — a été marqué avant — et la seconde par le théorème 6.2.

Supposons maintenant qu'un sommet reçoive une valeur trop grande, et choisissons parmi ces sommets un $v$ de distance $\delta (s,v)$ minimale: ainsi $d[v]>\delta (s,v)$, et tout sommet strictement plus proche de $s$ a reçu la bonne valeur. Le sommet $v$ est accessible — sinon $\delta (s,v)=+\infty$ et rien ne peut être plus grand — et . Soit le prédécesseur de sur un plus court chemin: , donc par minimalité. Considérons l'instant où est défilé et où l'algorithme examine le voisin . Trois cas, et trois seulement.

• $v$ n'est pas encore marqué. L'algorithme pose alors $d[v]=d[u]+1=\delta (s,u)+1=\delta (s,v)$, ce qui contredit $d[v]>\delta (s,v)$.

Aucun cas n'est possible: il n'existe pas de sommet mal évalué, et $d[v]=\delta (s,v)$ partout.

Point 3. Par construction, $d[v]=d[\mathrm{pere}[v]]+1$ pour tout $v\ne s$ marqué. En remontant les pères depuis $v$ on obtient donc une suite de sommets dont les valeurs de $d$ décroissent de un à chaque pas, et qui se termine en $s$ où $d=0$: ce chemin compte exactement arêtes. C'est donc un plus court chemin.

Démonstration. Le théorème 6.2 appliqué à l'arête dans un sens donne $\delta (s,v)\le \delta (s,u)+1$, et appliqué dans l'autre sens — l'arête est non orientée — donne $\delta (s,u)\le \delta (s,v)+1$. Les deux inégalités réunies disent exactement que la différence des deux distances est comprise entre $-1$ et .

Sur le graphe témoin, les cinq arêtes hors de l'arbre confirment l'énoncé: $BC$ relie deux sommets de niveau 1, $DE$ deux sommets de niveau 2, $FG$ deux sommets de niveau 3, tandis que $CD$ joint les niveaux 1 et 2 et $EF$ les niveaux 2 et 3. Nous utiliserons ce théorème deux fois: pour le test de bipartition en fin de chapitre, et, au chapitre 7, pour comprendre ce que Dijkstra ajoute au BFS.

Le parcours en profondeur

Deux formes, un même ordre

Le parcours en profondeur — depth-first search, ou DFS — fait le contraire du précédent: il suit un chemin aussi loin qu'il peut, et ne revient en arrière que lorsqu'il est bloqué. La structure sous-jacente est une pile: dernier entré, premier sorti. Elle peut être explicite, ou bien être la pile d'appels de la récursion — et c'est cette seconde forme qui s'écrit le plus naturellement.

def parcours_profondeur(graphe, source):
    """Dates de decouverte et de fin, et pere de chaque sommet atteint."""
    debut, fin, pere = {}, {}, {source: None}
    horloge = 0

    def visiter(u):
        nonlocal horloge
        horloge += 1
        debut[u] = horloge
        for v in graphe[u]:
            if v not in debut:
                pere[v] = u
                visiter(v)
        horloge +=

L'horloge s'incrémente à deux moments: quand on découvre un sommet et quand on termine de l'explorer, c'est-à-dire quand on a fini d'examiner tous ses voisins. Chaque sommet reçoit donc deux dates, $d[u]$ et $f[u]$, avec $d[u]<f[u]$, et l'horloge va de 1 à $2n$ sur une composante de $n$ sommets. Ces deux dates ne servent pas qu'à décorer la trace: elles sont l'outil de démonstration de toute la fin du chapitre.

La forme itérative remplace la récursion par une pile explicite. Elle n'est pas qu'un exercice de style: sur un graphe de plusieurs centaines de milliers de sommets, la version récursive dépasse la profondeur de pile autorisée par Python et lève une RecursionError.

def profondeur_iteratif(graphe, source):
    """Meme ordre de visite que la version recursive, avec une pile explicite."""
    vus = set()
    ordre = []
    pile = [source]
    while pile:
        u = pile.pop()
        if u in vus:
            continue
        vus.add(u)
        ordre.append(u)
        for v in reversed(graphe[u]):
            if v not in vus:
                pile.append(v)

Deux différences avec le BFS méritent d'être vues. Le reversed sert à retrouver exactement l'ordre de la version récursive: une pile ressort les éléments à l'envers, donc pour visiter les voisins dans l'ordre alphabétique il faut les empiler dans l'ordre inverse. Et le test if u in vus: continue en tête de boucle n'a pas d'équivalent dans le BFS: un sommet peut se trouver plusieurs fois dans la pile, parce qu'on empile un voisin sans le marquer, et qu'il peut être empilé de nouveau depuis un autre sommet avant d'être dépilé. On le marque au dépilement, et on ignore les doublons. C'est le prix à payer pour que la version itérative donne le même arbre que la version récursive.

Le théorème des parenthèses

Les dates de découverte et de fin racontent la structure de l'arbre de parcours, et elles la racontent complètement.

Démonstration. L'intervalle $[d[u],f[u]]$ est exactement la durée pendant laquelle $u$ est présent sur la pile des appels: il y est poussé quand $d[u]$ est fixé et retiré quand $f[u]$ l'est. Or une pile n'entrelace jamais deux séjours: si $u$ est empilé après $v$ et que $v$ est encore là, alors $u$ sera dépilé avant $v$. Les deux intervalles sont donc soit disjoints, soit emboîtés — un entrelacement est impossible.

Supposons maintenant $[d[v],f[v]]\subset [d[u],f[u]]$, c'est-à-dire $d[u]<d[v]<f[v]<f[u]$. Le sommet $v$ est découvert alors que l'appel est en cours; or tout sommet découvert pendant cet appel l'est depuis un sommet lui-même découvert pendant cet appel, ou depuis : une récurrence immédiate sur l'ordre de découverte montre que est un descendant de dans l'arbre. Réciproquement, si est un descendant de , l'appel qui le découvre est imbriqué dans , donc son intervalle l'est aussi. Les trois cas sont exclusifs et couvrent toutes les possibilités.

Le corollaire dont nous aurons besoin s'énonce en une phrase: si $v$ est découvert alors que $u$ est en cours d'exploration, c'est-à-dire si $d[u]<d[v]<f[u]$, alors $v$ est un descendant de $u$. C'est le point 3 du théorème, et c'est le seul outil dont la suite du chapitre a besoin.

Classer les arêtes

Un parcours en profondeur partage les arêtes en quatre familles, selon ce que l'algorithme trouve en examinant l'arête $(u,v)$ depuis $u$.

Démonstration. Soit $\{u,v\}$ une arête, et supposons sans perte de généralité que $d[u]<d[v]$: l'un des deux est découvert en premier. Au moment où $u$ est découvert, $v$ est encore blanc. Or $v$ est un voisin de $u$, donc il figure dans la liste que l'appel visiter(u) s'apprête à parcourir; il sera donc découvert — par cet appel lui-même, ou plus tôt par un appel imbriqué — avant que visiter(u) ne se termine. Ainsi $d[u]<d[v]<f[u]$, et le corollaire du théorème 6.6 fait de un de . En particulier est gris pendant tout l'intervalle , puisqu'un ancêtre ne termine qu'après ses descendants.

Regardons maintenant laquelle des deux rencontres a lieu la première.

• Depuis $u$ d'abord, c'est-à-dire si l'appel visiter(u) atteint $v$ dans sa liste avant que $v$ n'ait été découvert ailleurs: $v$ est blanc, l'algorithme descend, et l'arête est une arête de liaison.
• Depuis $v$ d'abord, c'est-à-dire si $v$ a été découvert par un autre chemin, plus bas dans la descendance de $u$: l'appel visiter(v) examine alors $u$, qui est gris d'après ce qui précède, et l'arête est une arête de retour.

Ces deux cas sont exhaustifs, donc aucune arête n'est classée en avant ni transverse. Une arête transverse exigerait qu'aucune des deux extrémités ne soit ancêtre de l'autre, ce que nous venons d'exclure. Quant à l'apparence d'une arête en avant — $u$ retrouvant plus tard dans sa liste un $v$ devenu noir entre-temps —, c'est la seconde lecture d'une arête déjà classée de retour depuis $v$, et non une nouvelle famille. $\square$

Dans un graphe orienté, les quatre familles existent bel et bien: le graphe orienté de la section sur le tri topologique produira, avec un parcours lancé dans l'ordre croissant des sommets, quatre arcs de liaison et cinq arcs transverses, et aucun arc de retour — c'est précisément parce qu'il est acyclique.

Les composantes connexes

Les deux parcours ci-dessus explorent la composante de leur source, et elle seule. Pour traiter un graphe qui n'est pas connexe, il suffit de les relancer depuis chaque sommet non encore vu.

Nous travaillons ici sur un second graphe, distinct du graphe témoin, précisément parce que le graphe témoin est connexe et ne montrerait rien. Appelons-le $H$: sept sommets $P,Q,R,S,T,U,V$, et cinq arêtes $PQ$, $QR$, $RP$, $ST$, $TU$. Le sommet n'a aucune arête.

def composantes(graphe):
    """Liste des composantes connexes, chacune donnee par la liste de ses sommets."""
    vus = set()
    resultat = []
    for depart in graphe:
        if depart in vus:
            continue
        composante = []
        file = deque([depart])
        vus.add(depart)
        while file:
            u = file.popleft()
            composante.append(u)
            for v in

Le coût reste $\Theta (n+m)$, et c'est le point à comprendre: la boucle extérieure passe sur les $n$ sommets, mais elle ne déclenche un parcours que pour les sommets encore non vus, et la somme des coûts de tous ces parcours partiels est celle d'un parcours unique — chaque sommet est enfilé une fois, chaque arête examinée deux fois, sur l'ensemble des composantes. On ne paie donc pas le nombre de composantes.

Cette relation mérite d'être retenue: un graphe à $n$ sommets et $c$ composantes connexes a au moins $n-c$ arêtes, avec égalité si et seulement si c'est une forêt. Elle donne un test immédiat: un graphe connexe à $n$ sommets et $n-1$ arêtes est un arbre, et un graphe connexe à $n$ sommets et strictement plus de $n-1$ arêtes contient un cycle.

Le tri topologique

Un graphe orienté, et il est différent du graphe témoin

Le tri topologique répond à la deuxième des trois questions de l'introduction: ordonner des tâches soumises à des contraintes de précédence. Il lui faut un graphe orienté, et le graphe témoin du cours ne l'est pas. Nous en construisons donc un autre, explicitement distinct, et il ne faut surtout pas le confondre avec le graphe témoin: ses sommets sont numérotés de 0 à 6 et ses arêtes sont des arcs orientés. Appelons-le $D$. Il représente sept tâches, l'arc $u\to v$ signifiant «la tâche $u$ doit être terminée avant que la tâche $v$ ne commence», et il compte neuf arcs:

DEPENDANCES = {
    0: [2],
    1: [0, 5],
    2: [6],
    3: [1, 4],
    4: [0, 5],
    5: [2],
    6: [],
}

Les degrés entrants se lisent en comptant les apparitions de chaque numéro dans les listes: ${\mathrm{deg}}^{-}(0)=2$, ${\mathrm{deg}}^{-}(1)=1$, ${\mathrm{deg}}^{-}(2)=2$, ${\mathrm{deg}}^{-}(3)=0$, , , . Leur somme vaut 9, le nombre d'arcs — l'analogue orienté du lemme des poignées de main, avec cette fois et non , chaque arc n'ayant qu'une origine et qu'une destination.

Que l'acyclicité soit nécessaire est immédiat: si $v_{i_1}\to v_{i_2}\to \cdots \to v_{i_k}\to v_{i_1}$ est un circuit, alors la condition donnerait , ce qui est absurde. Qu'elle soit suffisante est la correction des deux algorithmes ci-dessous, et nous la démontrons pour le premier.

Première méthode: par les degrés entrants

L'idée, due à Kahn, est celle que vous auriez eue: on commence par une tâche qui n'attend rien, on la retire, ce qui libère peut-être d'autres tâches, et on recommence.

def tri_topologique(graphe):
    """Ordre topologique par degres entrants, ou None si le graphe a un circuit."""
    entrant = {u: 0 for u in graphe}
    for u in graphe:
        for v in graphe[u]:
            entrant[v] += 1
    file = deque(sorted(u for u in graphe if entrant[u] == 0))
    ordre = []
    while file

Le coût est $\Theta (n+m)$: le calcul des degrés entrants balaie tous les arcs une fois, et la boucle principale sort chaque sommet une fois et décrémente chaque arc une fois. L'opération comptée est la décrémentation d'un degré entrant, et il y en a exactement $m$.

Démonstration de la correction. Montrons que la fonction rend une énumération valide si et seulement si le graphe est acyclique.

Supposons d'abord que la boucle sorte les $n$ sommets. Soit $(u,v)$ un arc. Le compteur entrant[v] a été initialisé à ${\mathrm{deg}}^{-}(v)$ et n'atteint zéro — condition pour que $v$ soit enfilé — qu'après avoir été décrémenté ${\mathrm{deg}}^{-}(v)$ fois, c'est-à-dire après la sortie de tous les prédécesseurs de $v$, dont . Donc sort avant , et l'arc va de la gauche vers la droite. L'énumération est bien un tri topologique.

Supposons ensuite que la boucle s'arrête avant d'avoir sorti les $n$ sommets, et soit $W$ l'ensemble non vide des sommets jamais sortis. Chaque $w\in W$ a, à l'arrêt, un compteur entrant[w] strictement positif, sinon il aurait été enfilé. Or ce compteur vaut le nombre de prédécesseurs de $w$ non encore sortis, donc tout sommet de $W$ possède au moins un prédécesseur dans $W$. Partons alors d'un sommet quelconque de $W$ et remontons de prédécesseur en prédécesseur: la suite ne quitte jamais $W$, qui est fini, donc elle repasse par un sommet déjà rencontré, et le morceau compris entre les deux passages est un circuit. Réciproquement, nous avons vu qu'un graphe avec circuit n'admet aucun tri topologique; la boucle ne peut donc pas en sortir sommets. Les deux implications sont établies.

Seconde méthode: par les dates de fin

La seconde méthode est plus courte à écrire et plus subtile à justifier. On lance un parcours en profondeur, et on énumère les sommets par dates de fin décroissantes.

def tri_par_dates_de_fin(graphe):
    """Tri topologique d un DAG: dates de fin decroissantes d un parcours en profondeur."""
    vus = set()
    ordre = []

    def visiter(u):
        vus.add(u)
        for v in graphe[u]:
            if v not in vus:
                visiter(v)
        ordre.append(u)          # u vient de terminer

    for u in sorted(graphe):
        if u not in vus:
            visiter(u)

Démonstration. Il suffit de montrer que pour tout arc $(u,v)$ de $G$, on a $f[v]<f[u]$: l'ordre décroissant des dates de fin place alors $u$ avant $v$. Considérons l'instant où le parcours, explorant $u$, examine l'arc $(u,v)$. À cet instant, $v$ est blanc, gris ou noir.

• $v$ blanc: l'algorithme descend dans $v$, qui devient un fils de $u$, et termine avant lui: $f[v]<f[u]$.
• $v$ gris: $v$ est alors un ancêtre de $u$ encore sur la pile, et l'arc $(u,v)$ est un arc de retour; le chemin d'arcs de liaison de à , suivi de , forme un circuit — exclu par hypothèse. Ce cas ne se produit donc jamais dans un DAG.

Dans les deux cas possibles, $f[v]<f[u]$, ce qui achève la démonstration. $\square$

Détecter un cycle

Le lien entre circuits et arcs de retour n'est pas une heuristique: c'est une équivalence, et c'est elle que nous démontrons.

Démonstration. Condition suffisante. Supposons qu'un parcours produise un arc de retour $(u,v)$. Par définition, $v$ est gris au moment où l'arc est examiné depuis $u$, donc $v$ est un ancêtre de $u$ dans la forêt de parcours: il existe un chemin d'arcs de liaison de $v$ à $u$. En lui adjoignant l'arc $(u,v)$, on ferme un circuit. $G$ a donc un circuit.

Condition nécessaire. Supposons que $G$ contienne un circuit et notons-le

ses sommets $x_0,\dots ,x_{k-1}$ étant deux à deux distincts. Lançons un parcours en profondeur quelconque, et appelons $v$ le premier sommet de $C$ que le parcours découvre; quitte à renuméroter le circuit, supposons $v=x_0$. Notons le prédécesseur de sur le circuit.

Montrons par récurrence sur $i$ que chaque $x_i$, pour $0\le i\le k-1$, est un descendant de $v$ dans la forêt de parcours — ou est $v$ lui-même.

Pour $i=0$ c'est vrai par convention. Supposons-le vrai pour $x_{i-1}$, donc $d[v]\le d[x_{i-1}]$ et $f[x_{i-1}]\le f[v]$ par le théorème 6.6. Considérons l'instant où l'exploration de examine l'arc ; cet instant est compris entre et , donc entre et . Deux cas.

• Si $x_i$ est encore blanc, il est découvert à cet instant et devient un fils de $x_{i-1}$, donc un descendant de $v$.
• Si $x_i$ est déjà découvert, alors $d[x_i]$ est antérieur à cet instant, donc . Par ailleurs , puisque est le sommet du circuit découvert et que . On a donc , et le corollaire du théorème 6.6 fait de un descendant de .

Dans les deux cas $x_i$ est un descendant de $v$, ce qui achève la récurrence. En particulier $u=x_{k-1}$ est un descendant de $v$, de sorte que $d[v]<d[u]<f[u]<f[v]$. Au moment où l'exploration de examine l'arc , l'instant est compris entre et , donc strictement antérieur à et postérieur à : le sommet est gris. L'arc est donc un arc de retour, et le parcours en produit au moins un.

La traduction algorithmique est directe, avec les trois couleurs de la définition:

def possede_un_circuit(graphe):
    """Vrai si un parcours en profondeur rencontre un arc de retour."""
    BLANC, GRIS, NOIR = 0, 1, 2
    etat = {u: BLANC for u in graphe}

    def visiter(u):
        etat[u] = GRIS
        for v in graphe[u]:
            if etat[v] == GRIS:
                return True                      # arc de retour: circuit

Le test décisif est etat[v] == GRIS et non etat[v] != BLANC: un sommet noir est terminé, il ne peut plus être sur la pile, et un arc qui y mène ne ferme aucun circuit. Confondre les deux est l'erreur classique, et elle déclare cycliques tous les graphes en losange, comme $D$, où le sommet 0 est atteint depuis 1 puis depuis 4.

Tester la bipartition

Deux couleurs, une contrainte

La bipartition est la structure des problèmes d'affectation — des candidats et des postes, des tâches et des machines, des étudiants et des projets —, et la reconnaître est le préalable à tout algorithme de couplage. Elle admet une caractérisation remarquablement simple.

Démonstration. Condition nécessaire. Supposons $G$ biparti, de partition $V_0\cup V_1$, et soit $x_0,x_1,\dots ,x_k=x_0$ un cycle. Chaque arête change de part, donc la part de est celle de si est pair et l'autre si est impair. Comme , la part de est celle de , ce qui force à être pair. Tout cycle d'un graphe biparti est donc de longueur paire.

Condition suffisante. Supposons que $G$ n'ait aucun cycle impair. Il suffit de traiter chaque composante connexe séparément, puisqu'une union de bipartitions est une bipartition. Soit donc $G$ connexe, $s$ un sommet, et colorions chaque sommet $v$ selon la parité de $\delta (s,v)$: $V_0$ les distances paires, $V_1$ les impaires. Soit une arête, et supposons par l'absurde et de même couleur, c'est-à-dire . Le théorème 6.5 impose ; combiné à l'égalité des parités, cela force , disons .

Prenons un plus court chemin $P_u$ de $s$ à $u$ et un plus court chemin $P_v$ de $s$ à $v$, tous deux de longueur $\ell$, et soit $w$ le dernier sommet commun aux deux — il en existe au moins un, à savoir —, disons à la distance . Alors la portion de de à compte arêtes, celle de de à en compte également, et ces deux portions n'ont que en commun. En les mettant bout à bout et en refermant par l'arête , on obtient un cycle de longueur

qui est impair. Contradiction. Donc toute arête relie deux couleurs distinctes, et la partition est une bipartition. $\square$

La démonstration est constructive, et l'algorithme s'en déduit: on fait un parcours en largeur en coloriant chaque sommet de la couleur opposée à celle de son père, et l'on échoue dès qu'une arête relie deux sommets de même couleur.

def bipartition(graphe, source):
    """Une 2-coloration de la composante de source, ou None s il n y en a pas."""
    couleur = {source: 0}
    file = deque([source])
    while file:
        u = file.popleft()
        for v in graphe[u]:
            if v not in couleur:
                couleur[v] = 1 - couleur[u]
                file.append(v)
            elif couleur[v] == couleur[u]:

Le coût est celui d'un parcours en largeur, $\Theta (n+m)$, et l'opération comptée reste l'examen d'une arête.

Synthèse

• Un graphe $G=(V,E)$ est un ensemble de $n$ sommets et de $m$ liens, orientés ou non, éventuellement pondérés. Le lemme des poignées de main, ${\sum }_u\mathrm{deg}(u)=2m$, gouverne tout ce qui suit: il donne les 22 maillons de la liste d'adjacence du graphe témoin, et il fait apparaître le terme $m$ dans le coût des parcours. Un graphe non orienté simple a entre 0 et arêtes, et c'est cet écart d'un facteur qui rend le choix de la représentation décisif.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

def contient_un_cycle(graphe, source):
    """Vrai si la composante de source contient un cycle. Graphe NON oriente."""
    vus = set()

    def visiter

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 20 pour les représentations, le parcours en largeur, le parcours en profondeur, le théorème des parenthèses et le tri topologique; les démonstrations des théorèmes 6.2 à 6.4 suivent la sienne de près.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, pour fixer le vocabulaire: arête de liaison, arête de retour, arête transverse.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — chapitre 4, avec de nombreuses implémentations commentées et une discussion très concrète du choix de la représentation.
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 3, particulièrement clair sur la bipartition, les composantes connexes et les graphes orientés acycliques.
• Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitres 3 et 4, pour une présentation courte et très lisible des deux parcours et de leurs applications.
• Beauquier, Berstel & Chrétienne, Éléments d'algorithmique, Masson — pour les preuves de correction rédigées en français, dans le style de ce chapitre.