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;
décomposer un graphe orienté en composantes fortement connexes par l'algorithme de Kosaraju, et trouver les points d'articulation et les ponts d'un graphe non orienté par les valeurs basses d'un seul parcours en profondeur;
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

0 \leq m \leq (2 n) = \frac{n ( n - 1 )}{2} . (6.1)

Cet encadrement est l'origine de tout le reste du chapitre: entre $0$ et $Θ (n^{2})$ il y a un facteur $n$ , et un algorithme dont le coût s'écrit $Θ (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 $de g (u)$ tels couples, par définition du degré: le total vaut $\sum_{u} de g (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:

d e g (u) pair \sum de g (u) + d e g (u) impair \sum de g (u) = 2 m .

La première somme est paire comme somme d'entiers pairs, et $2 m$ 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. $□$

Ce lemme n'est pas une curiosité: c'est la raison pour laquelle une liste d'adjacence occupe $2 m$ maillons et non $m$ , et c'est lui qui fait apparaître le terme $m$ — et non $2 m$ — dans le coût $Θ (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; elle a sa propre section, après le tri topologique, dont elle se sert.

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

Question 6.1

Un graphe non orienté simple a 7 sommets. Quatre d'entre eux sont de degré 3 et les trois autres de degré 2. Est-ce possible?

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} de g (u) = 2 m$ 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.

Opération	Liste d'adjacence	Matrice d'adjacence
Espace occupé	$Θ (n + m)$	$Θ (n^{2})$
Tester si l'arête existe	$Θ (de g u)$	$Θ (1)$
Énumérer les voisins de $u$	$Θ (de g u)$

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} de g (u) = 2 m$ , donc $Θ (n + m)$ en comptant la visite des sommets sans voisin. Avec une matrice, chaque énumération coûte $Θ (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 $Θ (1)$ par question avec une matrice, et $Θ (de g 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 $Θ (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 $Θ (n + m) = Θ (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.

Question 6.2

Combien de maillons au total la liste d'adjacence du graphe témoin contient-elle, en comptant tous les voisins de tous les sommets?

Question 6.3

Écrivez la fonction qui construit une liste d'adjacence. Elle reçoit la liste des sommets et la liste des arêtes, et renvoie un dictionnaire associant à chaque sommet la liste triée de ses voisins. Le programme affiche ensuite les sept degrés du graphe témoin, séparés par une espace. Attention: une arête doit être rangée des DEUX côtés, et un sommet sans arête doit quand même figurer dans le dictionnaire, avec une liste vide.

liste_adjacence.py

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 $Θ (1)$ ; on prendra garde à ne pas écrire list.pop(0), qui décale tout le reste et coûte $Θ (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 $Θ (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} de g (u) = 2 m$ 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 $2 m$ dans un graphe connexe parcouru en entier.

Exemple 6.2 · Le parcours en largeur du graphe témoin depuis A, étape par étape

La trace ci-dessous est produite en exécutant le code, jamais recopiée à la main. Les voisins sont examinés par ordre alphabétique, ce qui rend la trace reproductible.

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

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, $δ (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 $δ (s, u) = + \infty$ et l'inégalité est vraie sans rien dire. Sinon, soit $P$ un plus court chemin de $s$ à $u$ , de longueur $δ (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}] \leq d [v_{1}] + 1 \leq 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] \leq 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. $□$

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 $δ (s, v)$ minimale parmi ceux-là. On a $v \neq = s$ , donc $δ (s, v) \geq 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] \geq δ (s, v)$ pour tout $v$ marqué, par récurrence sur l'ordre des marquages. Pour $s$ , $d [s] = 0 = δ (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 $δ (s, v)$ minimale: ainsi $d [v] > δ (s, v)$ , et tout sommet strictement plus proche de $s$ a reçu la bonne valeur. Le sommet $v$ est accessible — sinon $δ (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 = δ (s, u) + 1 = δ (s, v)$ , ce qui contredit $d [v] > δ (s, v)$ .

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

Point 3. Par construction, $d [v] = d [pere [v]] + 1$ pour tout $v \neq = 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 $δ (s, v) \leq δ (s, u) + 1$ , et appliqué dans l'autre sens — l'arête est non orientée — donne $δ (s, u) \leq δ (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é: $B C$ relie deux sommets de niveau 1, $D E$ deux sommets de niveau 2, $F G$ deux sommets de niveau 3, tandis que $C D$ joint les niveaux 1 et 2 et $E F$ 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.

Question 6.4

Remettez dans l'ordre les cinq étapes d'une itération du parcours en largeur, telles qu'elles apparaissent dans le code.

Glissez les éléments pour les mettre dans le bon ordre

Tester si le voisin v porte déjà une distance

Enfiler v à la queue de la file

Parcourir la liste des voisins de u

Donner à v la distance de u plus un et le père u

Défiler le sommet u en tête de file

Question 6.5

Écrivez le parcours en largeur. La fonction reçoit une liste d'adjacence et une source, et renvoie le dictionnaire des distances en arêtes. Un sommet inaccessible ne doit PAS figurer dans le dictionnaire. La file est ici une simple liste avec un indice de tête, pour que vous voyiez bien le mécanisme; le programme affiche ensuite les sept distances depuis A.

parcours_largeur.py

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 à $2 n$ 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.

Exemple 6.3 · Le parcours en profondeur du graphe témoin depuis A

Toujours les voisins par ordre alphabétique, et toujours une trace produite en exécutant le code.

debut, fin, pere = parcours_profondeur(GRAPHE, "A")
print([debut[s] for s in "ABCDEFG"])
print([fin[s] for s in "ABCDEFG"])
print([pere[s] for s in "ABCDEFG"])

[1, 2, 3, 4, 5, 6, 7]
[14, 13, 12, 11, 10, 9, 8]
[None, 'A', 'B', 'C', 'D', 'E', 'F']

Sommet	$d [u]$

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

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.

Explorateur 6.1 · Parcourir le graphe témoin, une étape à la fois

Le premier curseur choisit la structure d’attente: une file pour le parcours en largeur, une pile pour le parcours en profondeur. Le second avance d’une étape. Les deux parcours partent de A, examinent les voisins dans le même ordre alphabétique et traitent les sept sommets dans le même ordre — et pourtant les arêtes épaisses, celles de l’arbre de parcours, ne sont pas les mêmes: la file construit un arbre de hauteur 3, la pile un chemin de hauteur 6. Regardez aussi le contenu de la structure: la file ne dépasse jamais deux sommets ici, la pile en garde jusqu’à six, dont certains en double.

Structure d’attentefile (BFS)

Étape0 / 8

Sommet traité

—

File (gauche = sortie)

Sommets traités

0 / 7

Arêtes de l’arbre

0 / 6

Distance atteinte

Arêtes hors arbre

11 / 11

Question 6.6

Sur le graphe témoin, les deux parcours depuis A visitent les sept sommets dans le même ordre. Que peut-on en conclure?

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 $P Q$ , $QR$ , $R P$ , $S T$ , $T U$ . 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 $Θ (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.

Question 6.7

Un graphe non orienté a 30 sommets et 3 composantes connexes. Quel est son nombre minimal d'arêtes?

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:

arc	$3 \to 1$	$3 \to 4$	$1 \to 0$	$1 \to 5$	$4 \to 0$	$4 \to 5$	$0 \to 2$

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: $de g^{-} (0) = 2$ , $de g^{-} (1) = 1$ , $de g^{-} (2) = 2$ , $de g^{-} (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 \dots \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 $Θ (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$ .

Exemple 6.5 · Tri topologique du graphe D par les degrés entrants

Un seul sommet a un degré entrant nul au départ, le sommet 3. La file est alimentée par valeurs croissantes, de sorte que la trace soit reproductible.

Étape	Sommet sorti	File après
1	3	1, 4
2	1	4
3	4	0, 5
4	0	5
5	5	2
6	2	6
7	6	(vide)

L'ordre produit est donc $3, 1, 4, 0, 5, 2, 6$ , et il compte sept sommets: le graphe est acyclique. Vérifions un arc au hasard, $4 \to 5$ : le sommet 4 occupe la position 2 et le sommet 5 la position 4, donc l'arc va bien vers la droite. Les neuf arcs passent le test.

À l'étape 1, la sortie de 3 fait tomber à zéro les degrés entrants de 1 et de 4 — d'où deux sommets ajoutés d'un coup. À l'étape 3, la sortie de 4 libère à la fois 0, dont le second prédécesseur 1 était déjà sorti, et 5, pour la même raison.

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é à $de g^{-} (v)$ et n'atteint zéro — condition pour que $v$ soit enfilé — qu'après avoir été décrémenté $de g^{-} (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. $□$

Exemple 6.6 · Les deux méthodes ne donnent pas le même ordre

Sur le graphe $D$ , la boucle extérieure du parcours en profondeur essaie les sommets dans l'ordre 0, 1, 2, …, et le résultat est:

print(tri_topologique(DEPENDANCES))      # par degres entrants
print(tri_par_dates_de_fin(DEPENDANCES)) # par dates de fin

[3, 1, 4, 0, 5, 2, 6]
[3, 4, 1, 5, 0, 2, 6]

Deux ordres différents, tous deux valides: les positions de 1 et de 4 sont échangées, ainsi que celles de 5 et de 0. C'est normal et c'est important — un tri topologique n'est pas unique. Le graphe $D$ en admet exactement quatre, obtenus en énumérant les permutations compatibles:

(3, 1, 4, 0, 5, 2, 6), (3, 1, 4, 5, 0, 2, 6), (3, 4, 1, 0, 5, 2, 6), (3, 4, 1, 5, 0, 2, 6) .

Question 6.8

Quelle méthode choisiriez-vous si, en plus de l'ordre, vous vouliez exhiber le cercle vicieux de dépendances quand il y en a un?

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

C : x_{0} \to x_{1} \to \dots \to x_{k - 1} \to x_{k} = x_{0},

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 \leq i \leq 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] \leq d [x_{i - 1}]$ et $f [x_{i - 1}] \leq 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.

Exemple 6.7 · Ce que l'ajout d'un seul arc change

Ajoutons au graphe $D$ le seul arc $2 \to 4$ , et relançons les deux algorithmes.

CYCLIQUE = dict(DEPENDANCES)
CYCLIQUE[2] = [4, 6]
print(tri_topologique(CYCLIQUE))
print(possede_un_circuit(CYCLIQUE))

Question 6.9

Écrivez le tri topologique par degrés entrants. La fonction reçoit un graphe orienté sous forme de liste de successeurs et renvoie la liste des sommets dans un ordre topologique, ou None si le graphe contient un circuit. Alimentez la file de départ par valeurs croissantes, pour que le résultat soit reproductible. Le programme affiche l'ordre trouvé pour le graphe des dépendances.

tri_topologique.py

Les composantes fortement connexes

Se rejoindre dans les deux sens

Au début du chapitre, nous avons laissé de côté une question: que deviennent les composantes connexes dans un graphe orienté? Dans un réseau de rues à sens unique, il ne suffit pas qu'un chemin mène de $u$ à $v$ ; pour faire l'aller et retour, il en faut aussi un de $v$ à $u$ . La bonne notion demande les deux.

La relation est réflexive par le chemin vide, symétrique par construction — c'est ce que la simple accessibilité n'était pas —, et transitive en mettant les chemins bout à bout dans chaque sens. Dans un graphe non orienté, elle coïncide avec l'accessibilité, et l'on retrouve les composantes connexes.

Démonstration. Supposons que $G^{CFC}$ contienne un circuit $C_{1} \to C_{2} \to \dots \to C_{k} \to C_{1}$ de composantes distinctes, . Prenons et . L'arc provient d'un arc de avec , ; à l'intérieur de chaque composante, tout sommet atteint tout autre. On va donc de à dans , de à par l'arc, de à dans : est accessible depuis . En suivant le reste du circuit de la même manière, est accessible depuis . Donc et sont mutuellement accessibles et devraient appartenir à la même composante, alors que . Contradiction.

Tout graphe orienté se lit donc à deux échelles: des blocs fortement connexes, à l'intérieur desquels tout communique, reliés entre eux par une structure de dépendances sans circuit, qu'on peut trier topologiquement. Un graphe orienté acyclique est le cas extrême où chaque sommet forme à lui seul sa composante; un graphe fortement connexe est l'autre extrême.

Le chemin blanc

L'algorithme qui calcule les composantes repose sur une propriété du parcours en profondeur que la démonstration du théorème 6.9 utilisait déjà sans la nommer.

Démonstration. Soit $x = z_{0}, z_{1}, \dots, z_{k} = y$ le chemin blanc. Montrons par récurrence sur $i$ que est un descendant de , c'est-à-dire, par le théorème 6.6, que . Pour c'est vrai. Supposons-le pour . Pendant l'exploration de , donc entre et , l'algorithme examine l'arc . Le sommet était blanc à l'instant ; il est découvert au plus tard à cet examen, donc à un instant compris entre et , et le corollaire du théorème 6.6 en fait un descendant de .

L'algorithme de Kosaraju

L'algorithme le plus simple à justifier, publié par Sharir en 1981 et attribué à Kosaraju, tient en deux parcours en profondeur:

un premier parcours de $G$ en entier, qui fixe les dates de fin $f [u]$ ;
un second parcours, sur le graphe transposé $G^{T}$ — les mêmes sommets, tous les arcs retournés —, dont la boucle extérieure essaie les sommets par dates de fin décroissantes.

Chaque arbre du second parcours est une composante fortement connexe.

def composantes_fortes(graphe):
    """Composantes fortement connexes d un graphe oriente (Kosaraju)."""
    ordre, vus = [], set()

    def visiter(u):                      # premier parcours, sur G
        vus.add(u)
        for v in graphe[u]:
            if v not in vus:
                visiter(v)
        ordre.append(u)                  # u termine: dates de fin croissantes

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

Le coût est $Θ (n + m)$ : deux parcours complets, et la construction du transposé, qui examine chaque arc une fois. L'opération comptée reste l'examen d'un arc, et il y en a exactement $2 m$ , $m$ par parcours.

Pourquoi le transposé, et pourquoi cet ordre? Le transposé a les mêmes composantes que $G$ — retourner tous les arcs échange les deux chemins de chaque aller-retour —, mais il inverse les arcs entre composantes. Le lemme suivant dit que les dates de fin du premier parcours trient les composantes dans un ordre topologique de $G^{CFC}$ ; le second parcours, en commençant par la composante qui termine le plus tard, ne peut alors s'échapper que vers des composantes déjà marquées.

Pour une partie $C$ de $V$ , notons $f (C) = max_{u \in C} f [u]$ la date de fin la plus tardive de ses sommets, au premier parcours.

Démonstration. Soit $(x, y)$ l'arc, $x \in C$ , $y \in C^{'}$ . Considérons le premier sommet de $C \cup C^{'}$ découvert par le premier parcours, disons $z$ .

Si $z \in C$ : à l'instant $d [z]$ , tous les sommets de $C \cup C^{'}$ sont blancs. Depuis $z$ , un chemin blanc mène à tout sommet de $C$ — la composante est fortement connexe —, et à tout sommet de $C^{'}$ par , l'arc , puis l'intérieur de . Par le théorème 6.11, tous les sommets de deviennent des descendants de et terminent avant lui: .

Si $z \in C^{'}$ : de même, tous les sommets de $C^{'}$ deviennent des descendants de $z$ , et $f (C^{'}) = f [z]$ . Aucun sommet de n'est accessible depuis : sinon, avec l'arc , les sommets de et de seraient mutuellement accessibles. Donc aucun sommet de n'est découvert pendant l'exploration de ; ils sont tous encore blancs à l'instant , et terminent plus tard: .

Démonstration. Par récurrence sur le nombre d'arbres déjà construits, supposons que chacun soit une composante, et considérons le suivant, lancé depuis la racine $r$ — le sommet non marqué de plus grande date de fin. Soit $C$ la composante de $r$ ; aucun de ses sommets n'est marqué, puisque les arbres précédents sont des composantes entières, et $f [r] = f (C)$ est la plus grande date de fin parmi les composantes restantes.

L'arbre contient $C$ . Dans $G^{T}$ , $C$ est encore fortement connexe; tous ses sommets sont blancs quand $r$ est découvert, donc ils deviennent des descendants de $r$ par le théorème 6.11.

L'arbre ne contient rien d'autre. Un arc de $G^{T}$ qui quitte $C$ vers une composante $C^{'}$ est un arc de $G$ allant de $C^{'}$ vers $C$ . Le théorème 6.12 donne alors $f (C^{'}) > f (C)$ : la composante termine plus tard que toutes les composantes restantes, elle a donc déjà été traitée, et tous ses sommets sont marqués. Le parcours depuis ne peut sortir de que vers des sommets déjà marqués, et il n'y entre pas.

Exemple 6.8 · Les composantes du graphe R

Nous prenons un nouveau graphe orienté, distinct du graphe témoin comme du graphe des dépendances $D$ : le graphe $R$ , huit sommets numérotés de 0 à 7 et onze arcs,

arc	$0 \to 1$	$1 \to 2$	$1 \to 4$	$2 \to 0$

Une seconde méthode, due à Tarjan (1972), trouve les mêmes composantes en un seul parcours en profondeur, en maintenant pour chaque sommet la plus petite date de découverte qu'il peut atteindre par ses descendants et un arc de retour, et en empilant les sommets jusqu'à ce qu'une racine de composante soit reconnue. Elle a le même coût $Θ (n + m)$ et repose sur la même idée de «valeur basse» que la section suivante développe pour les graphes non orientés; nous ne la détaillons pas, la démonstration de Kosaraju suffisant à établir le résultat. Les composantes fortement connexes ont une application que le chapitre 12 rendra frappante: une formule 2-SAT, où chaque clause n'a que deux littéraux, se décide en temps linéaire en calculant les composantes d'un graphe d'implications, alors que 3-SAT est $N P$ -complet.

Question 6.10

Un graphe orienté à $n$ sommets est acyclique. Combien a-t-il de composantes fortement connexes?

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 $δ (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 $ℓ$ , 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

(ℓ - j) + (ℓ - j) + 1 = 2 (ℓ - j) + 1,

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

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, $Θ (n + m)$ , et l'opération comptée reste l'examen d'une arête.

Question 6.11

Écrivez le test de bipartition par coloriage en largeur. La fonction reçoit une liste d'adjacence et une source, colorie la composante de la source avec les valeurs 0 et 1, et renvoie le dictionnaire des couleurs — ou None si deux sommets voisins reçoivent la même couleur. Le programme affiche oui ou non pour le graphe témoin, puis pour le cycle de longueur 4.

bipartition.py

Question 6.12

Un parcours en largeur d'un graphe non orienté connexe trouve une arête reliant deux sommets du niveau 4. Qu'en déduisez-vous?

Points d'articulation et ponts

Les maillons faibles d'un réseau

Revenons aux graphes non orientés, et à une question de fiabilité. Un réseau de communication est connexe; existe-t-il un nœud dont la panne, à elle seule, le coupe en morceaux? Une liaison dont la rupture isole une partie du réseau?

L'algorithme naïf supprime chaque sommet tour à tour et relance un parcours: $n$ parcours, soit $Θ (n (n + m))$ . Un seul parcours en profondeur suffit, à condition de noter pour chaque sommet jusqu'où ses descendants savent «remonter».

Elle se calcule pendant le parcours lui-même, sans rien lui ajouter d'autre qu'une comparaison par arête: au retour de chaque appel récursif,

bas [u] = min (d [u], {u, w} de retour min d [w], v fils de u min bas [v]),

puisque le sous-arbre de $u$ est $u$ plus les sous-arbres de ses fils.

Démonstration. Tout repose sur le théorème 6.7: dans un graphe non orienté, il n'y a que des arêtes de liaison et des arêtes de retour, et une arête de retour relie un sommet à l'un de ses ancêtres. En particulier, aucune arête ne relie deux sous-arbres disjoints. Pour un sommet $v$ , notons $T_{v}$ son sous-arbre.

Point 1. Si $r$ a deux fils $v_{1}$ et $v_{2}$ , aucune arête ne relie $T_{v_{1}}$ à , et le seul ancêtre commun de leurs sommets est : tout chemin de à passe par , et supprimer les sépare. Si n'a qu'un fils, supprimer laisse l'arbre de ce fils, qui contient tous les autres sommets et reste connexe.

Point 2. Soit $v$ un fils de $u$ avec $bas [v] \geq d [u]$ . Les arêtes qui quittent $T_{v}$ sont l'arête de liaison ${u, v}$ et des arêtes de retour issues de $T_{v}$ vers des ancêtres stricts de , de date de découverte au moins : ces ancêtres ne peuvent être que lui-même, puisque les ancêtres stricts de ont été découverts avant lui. Toutes les arêtes qui quittent aboutissent donc en ; supprimer isole de la racine, qui n'est pas dans puisque . Réciproquement, supposons que chaque fils de vérifie : chaque possède une arête de retour vers un ancêtre strict de , qui reste relié à par l'arbre privé de . Après suppression de , chaque sous-arbre de fils reste donc relié à la racine, et le graphe reste connexe.

Point 3. Une arête de retour ${x, w}$ ferme un cycle avec le chemin de l'arbre de $w$ à $x$ , et une arête d'un cycle n'est jamais un pont. Soit maintenant une arête de liaison ${u, v}$ . Comme au point 2, les arêtes qui quittent $T_{v}$ sont ${u, v}$ et des arêtes de retour vers des ancêtres stricts de $v$ — parmi lesquels . L'arête est un pont si et seulement si aucune de ces arêtes de retour n'existe, c'est-à-dire si aucune ne remonte à ou plus haut: . L'inégalité est stricte ici, et large au point 2: une arête de retour de vers lui-même contourne l'arête , mais ne contourne pas le sommet .

def articulations(graphe, racine):
    """Points d'articulation et ponts de la composante de racine (graphe NON oriente)."""
    debut, bas = {}, {}
    points, ponts = set(), []
    horloge = 0

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

Le coût est celui d'un parcours en profondeur, $Θ (n + m)$ : chaque arête est examinée deux fois, une fois depuis chaque extrémité, et chaque examen coûte une comparaison de plus que dans le parcours ordinaire. Le test v != pere est celui de l'exercice 6.5: sans lui, l'arête vers le père passerait pour une arête de retour, et aucune arête ne serait jamais un pont.

Exemple 6.10 · Le graphe témoin est 2-connexe; privé de C, il ne l'est plus

Sur le graphe témoin complet, lancé depuis $A$ avec les voisins par ordre alphabétique, le parcours est la chaîne $A, B, C, D, E, F, G$ de l'exemple 6.3, et

sommet	A	B	C	D	E	F	G
$d [u]$	1	2	3	4	5	6	7
$bas [u]$

Question 6.13

Combien de ponts le graphe $H$ de la section sur les composantes connexes compte-t-il? Rappel: sommets $P, Q, R, S, T, U, V$ et arêtes $P Q$ , $QR$ , $R P$ , $S T$ , $T U$ . On compte les ponts de chaque composante.

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} de g (u) = 2 m$ , 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.

Série d'exercices du chapitre 6Exercice 1 sur 5

Question 6.14

Pour quelle opération la matrice d'adjacence est-elle asymptotiquement meilleure que la liste?

Exercices

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

Exercice 6.1 · Deux représentations, deux comptes

On considère le graphe non orienté $K$ à cinq sommets $1, 2, 3, 4, 5$ et six arêtes ${1, 2}$ , ${1, 3}$ , ${2, 3}$ , ${3, 4}$ , , .

Exercice 6.2 · Deux parcours à la main

Sur le graphe $K$ de l'exercice 6.1, avec les listes de voisins triées par ordre croissant:

Effectuez le parcours en largeur depuis le sommet 1. Donnez l'ordre de visite, les cinq distances et les arêtes de l'arbre.
Effectuez le parcours en profondeur récursif depuis le sommet 1. Donnez les dates de découverte et de fin, ainsi que les arêtes de l'arbre.
Classez les six arêtes en arêtes de liaison et arêtes de retour pour le parcours en profondeur, et vérifiez le théorème 6.7.

Solution

1. La file démarre avec 1. On défile 1, dont les voisins 2 et 3 sont découverts à la distance 1. On défile 2: son seul voisin non vu est 3, déjà marqué; rien de nouveau. On défile 3: ses voisins 4 et 5 sont découverts à la distance 2. On défile 4, puis 5: rien de nouveau.

Sommet	1	2	3	4	5
Distance	0	1	1	2	2
Père	—	1	1	3	3

L'ordre de visite est $1, 2, 3, 4, 5$ et l'arbre est fait des quatre arêtes , , , — soit arêtes, comme il se doit. Les deux arêtes restantes, et , relient chacune deux sommets d'un même niveau: le graphe contient donc des cycles impairs et n'est pas biparti. On les voit: et .

Exercice 6.3 · Le tri topologique et ses variantes

On reprend le graphe orienté $D$ du chapitre: sommets 0 à 6, arcs $3 \to 1$ , $3 \to 4$ , $1 \to 0$ , $1 \to 5$ , $4 \to 0$ , , , , .

Exercice 6.4 · Bipartition et cycle impair

Soit le graphe non orienté $B$ à six sommets $a, b, c, d, e, f$ et sept arêtes $ab$ , $b c$ , $c d$ , $d e$ , $e f$ , , .

Exercice 6.5 · Détecter un cycle dans un graphe non orienté

Le théorème 6.9 concerne les graphes orientés. Dans un graphe non orienté, le critère naïf «on retrouve un sommet déjà vu» est faux, puisque l'arête vers le père se présente toujours deux fois.

Écrivez la fonction récursive qui décide si un graphe non orienté connexe contient un cycle, en passant le père en paramètre.
Démontrez que cette fonction est correcte: elle rend True si et seulement si le graphe contient un cycle.
En déduire, sans exécuter d'algorithme, une condition nécessaire et suffisante portant sur $n$ et $m$ pour qu'un graphe connexe soit un arbre.

Solution

1. On parcourt en profondeur et l'on ignore l'unique arête qui remonte au père:

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

    def

Exercice 6.6 · Kosaraju à la main

Soit le graphe orienté $Q$ à sept sommets $0, \dots, 6$ et huit arcs $0 \to 1$ , $1 \to 2$ , $1 \to 3$ , $2 \to 0$ , , , , .

Exercice 6.7 · Tester la forte connexité en deux parcours

Soit $G$ un graphe orienté et $s$ un sommet quelconque.

Démontrez que $G$ est fortement connexe si et seulement si un parcours depuis $s$ dans $G$ et un parcours depuis $s$ dans le transposé $G^{T}$ atteignent chacun tous les sommets.
Donnez le coût de ce test en fonction de $n$ et , et comparez-le à l'algorithme de Kosaraju.

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.
Tarjan, «Depth-first search and linear graph algorithms», SIAM Journal on Computing 1(2), 1972 — l'article fondateur des valeurs basses, pour les composantes fortement connexes comme pour les points d'articulation.

Objectifs du chapitre

Trois problèmes, un seul objet

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

Le vocabulaire, une fois pour toutes

Le graphe témoin du cours

Ranger un graphe en mémoire

Deux représentations, deux profils de coût

Quand la matrice gagne-t-elle vraiment?

Le parcours en largeur

L'algorithme et sa file

Le parcours en largeur calcule bien la distance

Le parcours en profondeur

Deux formes, un même ordre

Le théorème des parenthèses

Classer les arêtes

Les composantes connexes

Le tri topologique

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

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

Seconde méthode: par les dates de fin

Détecter un cycle

Les composantes fortement connexes

Se rejoindre dans les deux sens

Le chemin blanc

L'algorithme de Kosaraju

Tester la bipartition

Deux couleurs, une contrainte

Points d'articulation et ponts

Les maillons faibles d'un réseau

Synthèse

Exercices

Références

Ce qu'il reste

Les distances depuis A

La somme des distances

L'arbre du parcours et ce qui en reste

Étape	Défilé	Découverts (distance)	File après
1	A	B (1), C (1)	B, C
2	B	D (2)	C, D
3	C	E (2)	D, E
4	D	F (3)	E, F
5	E	G (3)	F, G
6	F	—	G
7	G	—	(vide)

A	1	14	—	—
B	2	13	A	—
C	3	12	B	C–A
D	4	11	C	D–B
E	5	10	D	E–C
F	6	9	E	F–D
G	7	8	F	G–E

Sommet	Voisins	Degré
1	2, 3	2
2	1, 3	2
3	1, 2, 4, 5	4
4	3, 5	2
5	3, 4	2