Exercice Sur Les Graphs

Table des matières

1 Exercice Sur les graphs 2

1
1 Exercice Sur les graphs
Étant donnée une représentation d’un graphe orienté par listes d’adjacence,
on demande le temps nécessaire pour calculer le degré sortant de chaque sommet,
puis le degré entrant de chaque sommet.
— Degré sortant. Dans la représentation par listes d’adjacence, le degré
sortant d’un sommet u est exactement la longueur de sa liste d’adjacence
Adj[u]. Pour calculer le degré sortant de tous les sommets, il suffit donc de
parcourir l’ensemble des listes et d’enregistrer leur taille. Le temps total
est proportionnel au nombre de sommets plus la somme des longueurs des
listes, soit Θ(|V | + |E|) (où |V | est le nombre de sommets et |E| le nombre
d’arcs). En effet, il faut au moins allouer un tableau de taille |V | pour
stocker les résultats, et la somme des longueurs des listes est précisément
|E| (chaque arc contribue pour une entrée dans la liste de son origine).
— Degré entrant. Pour obtenir le degré entrant de chaque sommet, on
peut initialiser un tableau deg_entrant[1..|V |] à zéro, puis parcourir toutes
les listes d’adjacence : pour chaque arc (u, v) rencontré (c’est-à-dire pour
chaque v présent dans Adj[u]), on incrémente deg_entrant[v]. Ce traite-
ment examine chaque arc une fois et effectue un travail constant par arc,
d’où un temps total en Θ(|V | + |E|).
Dans les deux cas, le temps de calcul est donc Θ(|V | + |E|), ce qui est optimal
puisque tout arc doit être consulté au moins une fois.

Exercice 22.1-2
On considère un arbre binaire complet à 7 sommets numérotés de 1 à 7
comme dans un tas binaire : la racine est 1, et pour un nœud i, son fils gauche
est 2i et son fils droit 2i + 1 (dans la limite des 7 sommets). L’arbre est ici vu
comme un graphe non orienté (les arêtes sont entre parent et enfant).
Représentation par listes d’adjacence. On associe à chaque sommet la liste
de ses voisins :
Sommet 1 : 2, 3
Sommet 2 : 1, 4, 5
Sommet 3 : 1, 6, 7
Sommet 4 : 2
Sommet 5 : 2
Sommet 6 : 3
Sommet 7 : 3
Si l’on souhaitait une version orientée (de la racine vers les feuilles), on aurait
simplement 1 → 2, 3 ; 2 → 4, 5 ; 3 → 6, 7 et les listes des feuilles seraient vides.
L’énoncé ne précisant pas l’orientation, la représentation non orientée est la plus
usuelle pour un arbre.
Représentation par matrice d’adjacence. La matrice d’adjacence A est une
matrice 7×7 symétrique où A[i][j] = 1 s’il existe une arête entre i et j, et 0 sinon.

2
Avec la numérotation du tas, les arêtes sont : (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7).
On obtient la matrice suivante :
 
0 1 1 0 0 0 0
1 0 0 1 1 0 0
 
1 0 0 0 0 1 1
 
A= 0 1 0 0 0 0 0

0 1 0 0 0 0 0
 
0 0 1 0 0 0 0
0 0 1 0 0 0 0

Exercice 22.1-3
Le graphe transposé d’un graphe orienté G = (V, E) est le graphe GT =
(V, E T ) où E T = {(v, u) ∈ V × V | (u, v) ∈ E}. On demande de décrire des
algorithmes efficaces pour construire GT à partir de G, dans les deux représen-
tations classiques, et d’analyser leur temps d’exécution.
1. Représentation par matrice d’adjacence. Soit M la matrice d’adjacence
de G (M [i][j] = 1 si (i, j) ∈ E, 0 sinon). La matrice d’adjacence de GT s’obtient
en transposant M : M T [i][j] = M [j][i]. Un algorithme simple consiste à allouer
une nouvelle matrice T de taille |V | × |V |, puis à copier chaque entrée avec
inversion des indices :
pour i de 1 à |V|
pour j de 1 à |V|
T[j][i] <- M[i][j]
Le temps d’exécution est Θ(|V |2 ), car on doit parcourir toutes les entrées de
la matrice. Ce temps est asymptotiquement optimal pour cette représentation,
puisqu’il faut examiner les |V |2 entrées pour construire la matrice transposée (à
moins d’utiliser une structure creuse, mais la matrice pleine suppose un stockage
explicite de chaque entrée).
2. Représentation par listes d’adjacence. Soit Adj le tableau de |V | listes
représentant G. On construit AdjT de la manière suivante :
(i) Créer un tableau AdjT de |V | listes vides.
(ii) Pour chaque sommet u = 1 à |V | :
— Pour chaque v dans Adj[u] (représentant un arc (u, v)) : ajouter u à
la liste AdjT [v].
Cet algorithme examine chaque arc exactement une fois, et pour chaque arc il
effectue une insertion en tête de liste (opération en temps constant). Le temps
total est donc Θ(|V | + |E|). C’est également optimal car tout arc doit être
retourné pour construire le graphe transposé.

3
Exercice 22.1-4
Énoncé
Soit G = (V, E) un multigraphe orienté donné sous forme de listes d’adja-
cence. Décrire un algorithme en temps O(V + E) qui construit la représentation
par listes d’adjacence du graphe non orienté équivalent G′ = (V, E ′ ), où E ′
contient les arêtes de E dans lesquelles les arêtes multiples entre deux sommets
sont remplacées par une arête simple et toutes les boucles sont supprimées.

Solution
Soit n = |V |. On suppose que les sommets sont numérotés de 1 à n. L’al-
gorithme procède en deux phases : d’abord on génère une version non orientée
(avec doublons), puis on élimine les doublons dans chaque liste.

Algorithm 1 Transformation d’un multigraphe orienté en graphe simple non

orienté
1: Entrée : tableaux d’adjacence Adj[1..n] de G, chaque Adj[u] est une liste.
′
2: Sortie : tableaux d’adjacence Adj [1..n] de G′ .
3: Créer un tableau A[1..n] de listes vides.
4: for u = 1 à n do
5: for chaque v ∈ Adj[u] do
6: if u ̸= v then
7: ajouter v à A[u]
8: ajouter u à A[v]
9: Créer un tableau global vue[1..n] initialisé à 0.
10: jeton ← 0
11: for u = 1 à n do
12: jeton ← jeton + 1
13: initialiser une liste vide Adj′ [u]
14: for chaque v ∈ A[u] do
15: if vue[v] ̸= jeton then
16: vue[v] ← jeton
17: ajouter v à Adj′ [u]
′
18: return Adj

Analyse
— Phase 1 (lignes 3–9) : chaque arête orientée de G est parcourue exactement
une fois. Comme |E| est le nombre total d’entrées dans les listes d’adjacence,
on effectue O(E) opérations. On ignore les boucles.
— Phase 2 (lignes 11–19) : la longueur totale des listes A[u] est au plus 2E
(chaque arête orientée non boucle produit deux entrées). La boucle interne

4
 examine chaque élément une fois. Grâce au tableau vue et au jeton, le test
et l’ajout se font en temps constant par élément. L’incrémentation du jeton
pour chaque sommet prend O(V ). Le temps total de cette phase est O(V +E).
— L’espace supplémentaire est O(V + E) pour A et le tableau vue.
L’algorithme construit bien Adj′ où chaque arête non orientée apparaît exacte-
ment une fois dans chaque liste des deux extrémités, et sans boucle. La com-
plexité totale est O(V + E).

Exercice 22.1-5
Énoncé
Le carré d’un graphe orienté G = (V, E) est le graphe G2 = (V, E 2 ) tel que
(u, v) ∈ E 2 si et seulement si G contient un chemin d’au plus deux arcs entre u
et v. Décrire des algorithmes efficaces pour calculer G2 à partir de G, pour les
représentations par listes d’adjacence et par matrice d’adjacence. Analyser les
temps d’exécution.

Solution
Représentation par listes d’adjacence. On suppose V = {1, . . . , n}.

Algorithm 2 Carré d’un graphe orienté – listes d’adjacence

1: Entrée : Adj[1..n] listes d’adjacence de G.
2
2: Sortie : Adj [1..n] listes d’adjacence de G2 .
3: Tableau global vue[1..n] initialisé à 0, jeton ← 0.
4: for u = 1 à n do
5: jeton ← jeton + 1
6: initialiser Adj2 [u] vide
7: vue[u] ← jeton ▷ chemin de longueur 0
8: ajouter u à Adj2 [u]
9: for chaque v ∈ Adj[u] do
10: if vue[v] ̸= jeton then
11: vue[v] ← jeton
12: ajouter v à Adj2 [u] ▷ chemin de longueur 1
13: for chaque w ∈ Adj[v] do
14: if vue[w] ̸= jeton then
15: vue[w] ← jeton
16: ajouter w à Adj2 [u] ▷ chemin de longueur 2
2
17: return Adj

Complexité. Pour un sommet u, la boucle interne visite tous les successeurs

v de u et pour chacun tous les successeurs w de v. Le nombre total d’opérations

5
est
X X  X
out-degre(u)+ out-degre(v) = O(E)+ in-degre(v)·out-degre(v).
u∈V v∈Adj[u] v∈V

Dans le pire cas (graphe dense), in-degre(v) = out-degre(v) = Θ(V ) pour tout
v, ce qui donne Θ(V 3 ). Pour un graphe éparse, le temps est bien meilleur (par
exemple O(V 2 ) pour une étoile, O(V ) si degrés bornés).P On peut donc dire que
l’algorithme s’exécute en O(V 3 ) dans le pire cas, et en O( v in-degre(v) out-degre(v))
en général, ce qui est toujours O(V E).

Représentation par matrice d’adjacence. Soit A la matrice d’adjacence

booléenne n × n de G, où A[i][j] = 1 si (i, j) ∈ E, 0 sinon. Le carré G2 a pour
matrice C telle que C[i][j] = 1 s’il existe un chemin d’au plus deux arcs de i à
j. On a
_n


C[i][j] = A[i][j] ∨ (A[i][k] ∧ A[k][j]) .
k=1

Le terme entre parenthèses est le produit booléen de A par elle-même.

Algorithm 3 Carré d’un graphe orienté – matrice d’adjacence

1: Entrée : matrice booléenne A[1..n][1..n].
2: Sortie : matrice booléenne C de G2 .
3: C ← A
4: for i = 1 à n do
5: for j = 1 à n do
6: if C[i][j] = 1 then continue
7: for k = 1 à n do
8: if A[i][k] = 1 et A[k][j] = 1 then
9: C[i][j] ← 1
10: break
11: return C

Complexité. Les trois boucles imbriquées prennent Θ(V 3 ) dans le pire cas.
On peut également utiliser la multiplication rapide de matrices (Strassen, Cop-
persmith–Winograd) pour obtenir O(V ω ) avec ω ≈ 2.37, mais l’approche naïve
en O(V 3 ) est satisfaisante pour cet exercice. On note que chaque sommet u
possède un chemin de longueur 0 vers lui-même, donc C[i][i] = 1 pour tout i.
Ceci est bien pris en compte car A[i][i] peut être 1, mais même s’il ne l’est pas,
le chemin de longueur 0 n’est pas capturé par le produit matriciel ni par A.
En effet, l’énoncé dit « au plus deux arcs », ce qui inclut les chemins de lon-
gueur 0. Il convient donc de forcer C[i][i] ← 1 pour tout i avant de commencer
ou après. L’algorithme ci-dessus doit être adapté : on peut initialiser C à la
matrice identité ∨A, puis calculer les chemins de longueur 2.
— y devient gris (temps 3). Voisin : x (blanc).

6
 — Arête (y, x) : x blanc → arête d’arbre.
Appel DFS-Visit(x) au temps 4.
x devient gris (temps 4). Voisin : v (gris).
Arête (x, v) : v gris → arête de retour.
Plus de voisins. x finit au temps 5.
— Retour à y : plus de voisins.
y finit au temps 6.
Après cette boucle, il reste au plus un sommet pouvant être un puits universel.
Il faut encore le vérifier complètement.

Algorithm 4 Détection d’un puits universel en O(V )

1: Entrée : matrice d’adjacence A[1..n][1..n].
2: Sortie : un sommet puits universel s’il existe, sinon NIL.
3: candidat ← 1
4: for j = 2 à n do
5: if A[candidat][j] = 1 then
6: candidat ← j
▷ sinon A[candidat][j] = 0, on conserve le candidat
7: Vérification du candidat :
8: for i = 1 à n do
9: if i ̸= candidat then
10: if A[candidat][i] = 1 ou A[i][candidat] = 0 then
11: return NIL ▷ le candidat n’est pas un puits universel
12: return le candidat ▷ le candidat est un puits universel

Correction.
— Invariant de la boucle de sélection : à chaque itération j, le sommet
candidat courant est le seul parmi {1, . . . , j} qui peut encore être un puits
universel.
— Initialement (j = 1), candidat = 1, le seul candidat possible parmi
{1}. L’invariant est vrai.
— Supposons l’invariant vrai avant d’examiner j. Si A[candidat][j] = 1,
candidat a un arc sortant, il ne peut pas être puits ; de plus tous les
sommets i < j, i ̸= candidat ont déjà été exclus, donc le seul nouveau
candidat possible parmi {1, . . . , j} est j. On pose candidat ← j. Si
A[candidat][j] = 0, alors j ne reçoit pas d’arc de candidat, donc j
ne peut pas être puits universel. Les autres sommets i < j sont déjà
exclus, donc le candidat reste le seul candidat possible.
Ainsi après la boucle, seul le candidat peut être puits universel.
— La phase de vérification teste la condition de puits universel sur le can-
didat : tous les arcs entrants doivent exister (A[i][candidat] = 1 pour
i ̸= candidat) et aucun arc sortant (A[candidat][i] = 0 pour tout i). Si un
test échoue, le graphe ne contient aucun puits universel.

7
Complexité. La première boucle effectue n − 1 itérations, chacune en temps
O(1). La phase de vérification effectue n itérations contenant un nombre constant
de lectures dans A. Le temps total est donc Θ(n) = O(V ), ce qui est optimal
pour ce problème.

Exercice 22.1-7
Soit G = (V, E) un graphe orienté sans boucle, avec |V | = n et |E| = m. Sa
matrice d’incidence B est une matrice n × m définie par :

−1 si l’arête j quitte le sommet i,

bij = 1 si l’arête j entre dans le sommet i,

0 sinon.


On s’intéresse à la matrice produit BB T , où B T est la transposée de B.

BB T est une matrice carrée de taille n × n. Décrivons ses coefficients.
Pour deux sommets i et k (avec 1 ≤ i, k ≤ n), le coefficient (BB T )ik est
donné par :
Xm
(BB T )ik = bij bkj .
j=1

Chaque arête j contribue au terme bij bkj . Examinons les différents cas.
— Si i = k : alors bij bij = (bij )2 . Comme bij ∈ {−1, 0, 1}, son carré vaut 1
si l’arête j est incidente au sommet i (qu’elle le quitte ou qu’elle y entre),
et 0 sinon. Ainsi,
X
(BB T )ii = 1 = deg(i),
j: j incidente à i

où deg(i) désigne le degré total du sommet i (somme du degré entrant et

du degré sortant).
— Si i ̸= k : la contribution d’une arête j n’est non nulle que si les deux
sommets i et k sont les extrémités de j. Comme le graphe n’a pas de
boucle, une arête j relie deux sommets distincts. Notons u la queue et v
la tête de l’arête j. On a alors buj = −1, bvj = +1, et tous les autres
coefficients sont nuls. Ainsi, pour une paire (i, k) avec i ̸= k :
— Si l’arête j va de i vers k (i.e. u = i, v = k), alors bij bkj = (−1)(+1) =
−1.
— Si l’arête j va de k vers i (i.e. u = k, v = i), alors bij bkj = (+1)(−1) =
−1.
— Sinon, le produit est nul.
Par conséquent, chaque arête reliant i et k (dans un sens ou dans l’autre)
contribue −1 à la somme. Soit mik le nombre d’arêtes entre i et k (indé-
pendamment de l’orientation). Alors :
(BB T )ik = − mik .

8
 En résumé, la matrice BB T a pour coefficients :
(
deg(i) si i = k,
(BB T )ik =
−(nombre d’arêtes entre i et k) si i ̸= k.
On reconnaît la matrice laplacienne du graphe non orienté sous-jacent (celui
obtenu en oubliant l’orientation des arêtes). Cette matrice est souvent notée
L = D −A, où D est la matrice diagonale des degrés et A la matrice d’adjacence
du graphe non orienté (comptant les arêtes multiples).

Réponse : Le coefficient (BB T )ii est le degré total du sommet i ; pour

i ̸= k, (BB T )ik est l’opposé du nombre d’arêtes reliant i et k (toutes orientations
confondues).

Exercice 22.1-8
On considère une représentation d’un graphe orienté G = (V, E) par listes
d’adjacence, mais chaque liste Adj[u] est implémentée par une table de hachage
contenant les sommets v tels que (u, v) ∈ E.

Temps moyen pour tester l’existence d’une arête

Si l’on suppose que toutes les requêtes d’appartenance d’une arête (u, v)
sont équiprobables et que la fonction de hachage est uniforme, le temps moyen
pour déterminer si (u, v) ∈ E est O(1) en pratique. En effet, une table de
hachage bien dimensionnée (facteur de charge constant) permet une insertion,
une suppression et une recherche en temps constant en moyenne.

Inconvénients de ce schéma
Malgré cette performance moyenne intéressante, l’utilisation de tables de
hachage présente plusieurs inconvénients :
— Temps dans le pire cas : une mauvaise fonction de hachage ou un trop
grand nombre de collisions peuvent dégrader la recherche en O(|Adj[u]|)
dans le pire cas, ce qui peut être problématique pour certaines applications.
— Coût mémoire : les tables de hachage ont généralement un facteur de
charge maximal et nécessitent un espace supplémentaire pour gérer les
collisions (listes chaînées ou adressage ouvert). De plus, le redimensionne-
ment périodique (rehachage) est coûteux en temps et en mémoire.
— Non adaptées au parcours séquentiel : itérer sur tous les voisins d’un
sommet est moins efficace qu’avec une liste chaînée, car il faut parcourir
l’ensemble des cases de la table (dont beaucoup sont vides) ou maintenir
une structure supplémentaire.
— Complexité d’implémentation : la gestion des collisions, du redimen-
sionnement et du choix de la fonction de hachage ajoute de la complexité
par rapport à une simple liste.

9
Structure alternative proposée
Pour remédier à ces problèmes, on peut remplacer chaque table de hachage
par un arbre binaire de recherche équilibré (par exemple un arbre rouge-
noir ou un arbre AVL). Chaque Adj[u] devient alors un arbre contenant l’en-
semble des sommets v pour lesquels (u, v) ∈ E.

Avantages :
— Temps garanti : les opérations (recherche, insertion, suppression) s’ef-
fectuent en O(log deg(u)) dans le pire cas, ce qui élimine les risques de
dégradation catastrophique.
— Pas de fonction de hachage : on évite les problèmes de collisions et de
redimensionnement.
— Parcours ordonné : on peut aisément parcourir les voisins dans l’ordre
croissant, ce qui peut être utile pour certains algorithmes.

Inconvénients :
— Temps d’accès : O(log deg(u)) en moyenne et dans le pire cas, alors que
la table de hachage offre O(1) en moyenne. Pour des degrés très faibles, la
constante cachée peut rendre l’arbre moins performant.
— Coût mémoire : chaque nœud d’arbre stocke des pointeurs supplémen-
taires (gauche, droite, parent, couleur), ce qui augmente la consommation
mémoire par rapport à une liste chaînée ou à une table de hachage com-
pacte.
— Complexité d’implémentation : la mise en œuvre d’arbres équilibrés
est plus délicate que celle de tables de hachage basiques.

Alternative supplémentaire : tableau trié + recherche bi-

naire
Si le graphe est statique (pas de modifications après la construction), on peut
stocker chaque liste Adj[u] dans un tableau trié. La recherche d’une arête se
fait alors par dichotomie en O(log deg(u)) et l’empreinte mémoire est minimale.
L’inconvénient majeur est l’inefficacité des mises à jour (insertion et suppression
coûtent O(deg(u))).

Conclusion
Aucune structure n’est universellement meilleure. Le choix dépend des contraintes
de l’application :
— Pour des graphes dynamiques avec de nombreuses requêtes d’appartenance
et peu de parcours séquentiels, la table de hachage reste pertinente malgré
ses inconvénients.

10
— Pour des applications nécessitant des garanties de temps dans le pire cas
(par exemple systèmes temps réel), un arbre équilibré est préférable.
— Pour des graphes statiques, un tableau trié offre un excellent compromis
entre temps de recherche et compacité.

11
Notation
Pour un sommet v, on note d[v] la distance (en nombre d’arêtes) depuis la
source, et π[v] le prédécesseur de v dans l’arbre de parcours en largeur. On suit
l’algorithme BFS(G, s) tel que décrit dans Cormen et al.

Exercice 22.2-1
On considère le graphe orienté de la figure 22.2(a) (édition classique, 6 som-
mets) dont les arcs sont :

1 → 2, 1 → 4, 2 → 5, 3 → 5, 3 → 6, 4 → 2, 5 → 4, 6 → 6.

La source est le sommet 3.

Le déroulement du parcours en largeur donne les valeurs suivantes :
— d[3] = 0, π[3] = NIL (source).
— Les voisins de 3 sont 5 et 6 : d[5] = 1, π[5] = 3 ; d[6] = 1, π[6] = 3.
— Du sommet 5, on découvre 4 : d[4] = 2, π[4] = 5.
— Du sommet 6, l’arc (6, 6) boucle sur lui-même, aucun nouveau sommet.
— Du sommet 4, on découvre 2 : d[2] = 3, π[2] = 4.
— Du sommet 2, son seul voisin 5 est déjà visité.
— Le sommet 1 n’est jamais atteint : d[1] = ∞, π[1] = NIL.

Sommet d π
1 ∞ NIL
2 3 4
3 0 NIL
4 2 5
5 1 3
6 1 3

Table 1 – Résultats du BFS orienté depuis le sommet 3.

Exercice 22.2-2
On considère le graphe non orienté de la figure 22.3 (8 sommets) dont les
arêtes sont :

{r, s}, {r, w}, {s, w}, {t, u}, {t, x}, {u, v}, {u, y}, {w, x}, {x, y}.

La source est le sommet u.

Le parcours en largeur s’effectue comme suit (l’ordre exact des découvertes
dépend de l’ordre des listes d’adjacence ; on donne celui usuellement illustré
dans l’ouvrage) :

12
 — d[u] = 0, π[u] = NIL.
— Voisins de u : t, v, y ⇒ d[t] = d[v] = d[y] = 1 ; π[t] = π[v] = π[y] = u.
— Depuis t : on découvre x ⇒ d[x] = 2, π[x] = t.
— Depuis v : aucun nouveau voisin.
— Depuis y : voisin x déjà découvert, rien de nouveau.
— Depuis x : on découvre w ⇒ d[w] = 3, π[w] = x.
— Depuis w : on découvre r et s ⇒ d[r] = d[s] = 4, π[r] = π[s] = w.
— Depuis r : s déjà découvert, rien de nouveau.
— Depuis s : r déjà découvert.

Sommet d π
r 4 w
s 4 w
t 1 u
u 0 NIL
v 1 u
w 3 x
x 2 t
y 1 u

Table 2 – Résultats du BFS non orienté depuis le sommet u.

Exercice 22.2-3
Énoncé
Montrer qu’un seul bit par sommet suffit pour coder la couleur, en expliquant
que la procédure BFS produirait le même résultat si les lignes 5 et 14 étaient
supprimées.

Solution
Considérons l’algorithme BFS classique (Cormen et al., 3e édition) :

13
Algorithm 5 BFS(G, s) original
1: for chaque sommet u ∈ V \ {s} do
2: [Link] ← BLANC
3: u.d ← ∞
4: u.π ← NIL
5: [Link] ← GRIS ▷ ligne 5
6: s.d ← 0
7: s.π ← NIL
8: Q ← ∅
9: ENFILER(Q, s)
10: while Q ̸= ∅ do
11: u ← DÉFILER(Q)
12: for chaque v ∈ Adj[u] do
13: if [Link] = BLANC then
14: [Link] ← GRIS ▷ ligne 14
15: v.d ← u.d + 1
16: v.π ← u
17: ENFILER(Q, v)
18: [Link] ← NOIR

L’algorithme utilise trois couleurs : BLANC (non découvert), GRIS (décou-

vert mais non terminé), NOIR (terminé). Le seul test effectué sur la couleur
est la comparaison avec BLANC (ligne 13). Dès qu’un sommet est découvert,
on le marque GRIS puis, après avoir exploré sa liste d’adjacence, on le marque
NOIR. Or, le fait de distinguer GRIS et NOIR n’apporte aucune information
supplémentaire : on souhaite simplement éviter de remettre en file un sommet
déjà découvert. Par conséquent, un seul bit suffit pour mémoriser l’état « pas
encore découvert » (BLANC) ou « déjà découvert » (NOIR). Si l’on supprime
les lignes 5 et 14 (les affectations à GRIS) et que l’on remplace l’affectation
de la ligne 18 par la mise à NOIR au moment de la découverte (c’est-à-dire
aux endroits correspondant aux anciennes lignes 5 et 14), le comportement de
l’algorithme reste identique : chaque sommet est enfilé exactement une fois, les
distances et les prédécesseurs sont inchangés. En pratique, on pourrait conserver
un unique booléen découvert initialisé à faux pour chaque sommet. Les lignes
5 et 14 originales deviendraient alors découvert← vrai, et la ligne 18 serait
supprimée. Le test de la ligne 13 porterait sur non découvert. Ainsi, un seul
bit par sommet suffit pour implanter la couleur, et l’algorithme produit le même
résultat.

Exercice 22.2-4
Énoncé
Quel est le temps d’exécution de BFS si l’on représente le graphe par une
matrice d’adjacence et que l’on adapte l’algorithme à cette représentation ?

14
Solution
Si le graphe G = (V, E) est donné par une matrice d’adjacence A de taille
|V | × |V |, la recherche du voisinage d’un sommet u exige de parcourir la ligne u
de la matrice, ce qui prend Θ(|V |) opérations. L’algorithme BFS modifié est le
suivant :
— Initialisation des attributs de tous les sommets : O(|V |).
— Boucle while : chaque sommet est défilé exactement une fois, donc |V | ité-
rations.
— À l’intérieur, pour le sommet u défilé, on examine les |V | entrées A[u, v]
(v = 1, . . . , |V |) afin de détecter les voisins non découverts. Ce parcours
coûte Θ(|V |) par sommet.
Le temps total est donc Θ(|V |2 ) dans le pire des cas, quelle que soit la densité
du graphe.

Exercice 22.2-5
Énoncé
Montrer que, dans un parcours en largeur, la valeur u.d attribuée à un som-
met u est indépendante de l’ordre dans lequel les sommets apparaissent dans
chaque liste d’adjacence. En utilisant la figure 22.3 comme exemple, montrer
que l’arbre de largeur calculé par BFS peut dépendre de l’ordre dans les listes
d’adjacence.

Solution
Indépendance des distances u.d. Soit G = (V, E) un graphe orienté ou non
orienté, et s le sommet source. Notons δ(s, u) la distance (longueur du plus court
chemin) de s à u dans G. L’algorithme BFS possède les propriétés suivantes,
qui découlent uniquement de l’ordre de découverte par couches et non de l’ordre
dans les listes d’adjacence :
1. La file Q contient à tout instant des sommets dont les distances d sont rangées
en ordre croissant (la différence entre deux distances consécutives est au plus
1).
2. Lorsqu’un sommet v est découvert pour la première fois, il est atteint par
un chemin de longueur u.d + 1, où u est le sommet en cours d’exploration.
Comme les sommets sont traités dans l’ordre croissant de leur distance, ce
chemin est nécessairement un plus court chemin de s à v : aucun autre chemin
plus court n’aurait pu laisser v non découvert auparavant.
3. Par conséquent, pour chaque sommet u, la valeur u.d attribuée par BFS est
exactement δ(s, u), qui est une propriété intrinsèque du graphe, indépendante
de l’ordre des listes d’adjacence.

15
Dépendance de l’arbre de largeur. L’arbre (ou la forêt) de largeur est
formé par les pointeurs π. Lorsqu’un sommet v blanc est découvert depuis u, on
fixe v.π = u. S’il existe plusieurs sommets qui auraient pu découvrir v au même
moment (c’est-à-dire situés à la même distance de s), le premier qui examine v
dans sa liste d’adjacence devient son parent. L’ordre dans les listes d’adjacence
peut donc modifier le choix du parent, sans affecter les distances.
Exemple. Considérons le graphe non orienté G à 4 sommets {s, a, b, c} et
les arêtes (s, a), (s, b), (a, c), (b, c). Listes d’adjacence :
— Adj[s] = [a, b] ou [b, a],
— Adj[a] = [s, c],
— Adj[b] = [s, c],
— Adj[c] = [a, b].
Deux ordres différents pour Adj[s] produisent deux arbres de largeur distincts :
— Ordre [a, b] : BFS enfile d’abord a puis b depuis s. Ensuite a découvre c
et le marque comme fils (c.π = a). Quand b est traité, c est déjà découvert.
Arbre : s → a, s → b, a → c.
— Ordre [b, a] : BFS enfile b puis a. b découvre c (c.π = b). Arbre : s →
a, s → b, b → c.
Dans les deux cas, les distances sont identiques : s.d = 0, a.d = b.d = 1, c.d = 2.
Cet exemple illustre le même phénomène que la figure 22.3 de l’ouvrage, où
l’ordre des voisins du sommet source influe sur les liens de parenté mais non sur
les distances calculées.

Exercice 22.2-6
On doit exhiber un graphe orienté G = (V, E), une source s ∈ V et un
ensemble d’arcs Eπ ⊆ E tels que le chemin simple unique de s à tout sommet v
dans (V, Eπ ) est un plus court chemin dans G, mais que Eπ ne peut être obtenu
par un parcours en largeur (BFS) de G, quel que soit l’ordre des sommets dans
les listes d’adjacence.

a c

b d

Figure 1 – Graphe pour l’exercice 22.2-6.

16
 Considérons le graphe G de sommets {s, a, b, c, d} et d’arcs

E = {(s, a), (s, b), (a, c), (a, d), (b, c), (b, d)}.

La source est s. Les distances de plus court chemin depuis s sont : d[s] = 0,
d[a] = d[b] = 1, d[c] = d[d] = 2.
On propose l’ensemble d’arcs

Eπ = {(s, a), (s, b), (a, c), (b, d)}.

Le graphe (V, Eπ ) est un arbre orienté de racine s. Les chemins qu’il définit
sont : s → a, s → b, s → a → c, s → b → d, tous de longueur égale à la distance
minimale dans G. Eπ est donc bien un arbre de plus courts chemins.
Montrons qu’aucun BFS sur G, quel que soit l’ordre des listes d’adjacence,
ne peut produire Eπ . Dans BFS, la source s est d’abord visitée. Ses voisins a
et b sont alors découverts et enfilés, avec π[a] = π[b] = s ; leurs distances sont
1. L’ordre d’enfilement (et donc de traitement) de a et b dépend de l’ordre de
la liste Adj[s] : soit a puis b, soit b puis a. Supposons que a soit traité avant
b. Lors du traitement de a, ses voisins c et d sont blancs ; BFS les découvre
tous les deux et pose π[c] = π[d] = a. Lorsque b est ensuite traité, c et d
sont déjà découverts, donc leurs parents ne changent pas. L’arbre construit est
{(s, a), (s, b), (a, c), (a, d)}. Si au contraire b est traité en premier, on obtient
{(s, a), (s, b), (b, c), (b, d)}. Dans les deux cas, un même sommet de niveau 1
devient parent de deux sommets de niveau 2. L’arbre souhaité Eπ répartit les
enfants : c enfant de a, d enfant de b, ce qui exigerait que a et b soient chacun
le premier à traiter l’un des deux sommets de niveau 2, ce qui est impossible
avec un traitement séquentiel. Aucun ordonnancement des listes d’adjacence ne
peut produire Eπ .

Exercice 22.2-7
On dispose de n catcheurs professionnels et d’une liste de r rivalités (paires de
catcheurs rivaux). On souhaite attribuer à chacun un type « babyface » (gentil)
ou « heel » (méchant) de sorte que toute rivalité oppose un babyface à un heel.
Ce problème se modélise par un graphe non orienté G où les sommets sont
les catcheurs et les arêtes sont les rivalités. Une désignation valable correspond
exactement à une 2-coloration de G, qui existe si et seulement si G est biparti.
Algorithme en O(n + r). On peut utiliser un parcours en largeur (BFS) ou
en profondeur (DFS). L’idée est de colorier chaque sommet en 0 ou 1 de façon
que deux sommets adjacents portent des couleurs différentes. On initialise un
tableau couleur[1..n] à une valeur indéfinie. Pour chaque sommet non encore
colorié, on le colorie arbitrairement en 0, puis on effectue un BFS/DFS à partir
de ce sommet : pour chaque voisin v d’un sommet u, si v n’est pas colorié, on
lui donne la couleur opposée à celle de u et on l’enfile ; si v est déjà colorié de la
même couleur que u, le graphe n’est pas biparti et la désignation est impossible.

17
Désignation-Catcheurs(liste des n catcheurs, liste des r rivalités)
construire un graphe G avec n sommets et r arêtes
couleur[1..n] ← NIL
pour chaque sommet v de 1 à n faire
si couleur[v] = NIL alors
couleur[v] ← 0
ENFILER(v)
tant que la file n’est pas vide faire
u ← DÉFILER()
pour chaque voisin w de u faire
si couleur[w] = NIL alors
couleur[w] ← 1 - couleur[u]
ENFILER(w)
sinon si couleur[w] = couleur[u] alors
retourner "Impossible"
retourner couleur

Le parcours de tous les sommets et de toutes les arêtes prend un temps

O(n + r). La construction du graphe et la vérification se font donc en O(n + r).

Exercice 22.2-8
Le diamètre d’un arbre T = (V, E) est la plus grande distance (en nombre
d’arêtes) entre deux sommets quelconques. Un algorithme efficace pour le cal-
culer repose sur deux parcours BFS.
(i) Choisir un sommet arbitraire u ∈ V . Effectuer un BFS (ou DFS) depuis
u pour trouver un sommet v le plus éloigné de u.
(ii) Effectuer un second BFS depuis v pour trouver un sommet w le plus
éloigné de v. La distance δ(v, w) est le diamètre de l’arbre.
Justification. Dans un arbre, le sommet le plus éloigné d’un sommet quel-
conque est toujours une extrémité d’un plus long chemin. En effet, soit P un
plus long chemin (diamètre) d’extrémités x et y. Soit u un sommet quelconque.
Le sommet v le plus éloigné de u coïncide avec x ou y (ou se trouve à une
distance qui permet d’atteindre l’extrémité du diamètre). Une fois trouvée une
extrémité v, le second BFS depuis v donne l’autre extrémité w du diamètre. La
distance calculée est donc bien le diamètre.
Complexité. Chaque BFS visite tous les sommets et toutes les arêtes de
l’arbre, donc O(|V | + |E|) = O(n) (car |E| = n − 1). Le temps d’exécution est
donc O(n).

Exercice 22.2-9
Soit G = (V, E) un graphe connexe non orienté. On demande un algorithme
en O(|V | + |E|) pour calculer un chemin qui traverse chaque arête de G exacte-

18
ment une fois dans chaque direction.
Modélisation. On transforme G en un graphe orienté G′ en remplaçant
chaque arête {u, v} par deux arcs opposés (u, v) et (v, u). G′ est fortement
connexe et, pour chaque sommet, le degré entrant est égal au degré sortant (car
chaque arête non orientée contribue d’un au degré entrant et d’un au degré
sortant de chaque extrémité). G′ est donc un graphe eulérien orienté.
Algorithme. On peut construire un circuit eulérien dans G′ en temps
O(|V | + |E|) avec l’algorithme de Hierholzer :
— Partir d’un sommet quelconque. Suivre des arcs non encore empruntés
jusqu’à revenir au sommet de départ (on obtient un circuit).
— Tant qu’il reste un sommet du circuit qui possède encore des arcs non
visités, démarrer un nouveau circuit depuis ce sommet et l’insérer dans le
circuit principal.
Le résultat est une séquence d’arcs qui constitue un chemin (une marche) dans
G′ empruntant chaque arc exactement une fois. Revenu en termes du graphe
non orienté G, cela donne une marche qui traverse chaque arête exactement une
fois dans chaque sens. La longueur totale est 2|E|, et le temps de construction
est O(|V | + |E|) avec une gestion appropriée des listes d’adjacence (pointeurs
vers le prochain arc à utiliser).
Application au labyrinthe. On dispose d’un labyrinthe et d’une grande
quantité de pièces (pennies). La méthode pour trouver la sortie sans se perdre
consiste à suivre une règle simple : toujours placer une pièce sur le sol lorsqu’on
emprunte un passage, et ne jamais reprendre un passage qui comporte déjà
deux pièces (une dans chaque direction). Ceci revient à effectuer un parcours en
profondeur (DFS) du graphe des couloirs : on explore aussi loin que possible, en
marquant les passages à l’aller avec une pièce. Lorsqu’on atteint une impasse,
on fait demi-tour en ramassant la pièce (ou en la laissant comme marqueur de
retour). Ce procédé permet d’explorer systématiquement tout le labyrinthe sans
emprunter plus de deux fois un même couloir, et garantit de trouver la sortie. Il
correspond à l’algorithme de Hierholzer sur le graphe orienté obtenu en doublant
les arêtes, où les pièces servent à se souvenir des directions déjà parcourues.

19
Exercice 22.3-1
On considère un parcours en profondeur (DFS) dans un graphe orienté puis
dans un graphe non orienté. Pour chaque arête (u, v), on s’intéresse aux couleurs
des sommets au moment où l’arête est examinée (c’est-à-dire lorsque u est gris).
La couleur de u est donc toujours GRAY. Les cas où u est WHITE ou
BLACK ne correspondent à aucun moment réel de l’exploration.
Le tableau ci-dessous indique, pour chaque couleur de v rencontrée, si la
situation est possible et quel type d’arête en résulte.

Graphe orienté
u\v WHITE GRAY BLACK
WHITE Non Non Non
GRAY Oui (arbre) Oui (retour) Oui (avant ou traversante)
BLACK Non Non Non

Graphe non orienté

Dans un graphe non orienté, chaque arête est traitée deux fois. Lorsque l’on
explore u, on ignore les arêtes menant à un sommet noir (car elles ont déjà été
classifiées).
Seuls les cas suivants se présentent :

u\v WHITE GRAY BLACK

WHITE Non Non Non
GRAY Oui (arbre) Oui (retour) Non
BLACK Non Non Non

Exercice 22.3-2
Le graphe orienté de la figure 22.6 (CLRS, 3e édition) est constitué des
sommets
u, v, w, x, y, z
et des arêtes :

u → v, u → x, v → y, w → y, w → z, x → v, y → x, z → z.

Les listes d’adjacence sont ordonnées alphabétiquement. L’ordre d’examen

des sommets dans la boucle principale de DFS est également alphabétique.
Nous exécutons l’algorithme pas à pas.

Déroulement
1. Sommet u : blanc → appel DFS-Visit(u) au temps 1.
— u devient gris (temps 1).

20
 — Voisins dans l’ordre : v puis x.
— Arête (u, v) : v blanc → arête d’arbre.
Appel DFS-Visit(v) au temps 2.
— v devient gris (temps 2). Voisin : y (blanc).
— Arête (v, y) : y blanc → arête d’arbre.
Appel DFS-Visit(y) au temps 3.
— y devient gris (temps 3). Voisin : x (blanc).
— Arête (y, x) : x blanc → arête d’arbre.
Appel DFS-Visit(x) au temps 4.
x devient gris (temps 4). Voisin : v (gris).
Arête (x, v) : v gris → arête de retour.
Plus de voisins. x finit au temps 5.
— Retour à y : plus de voisins.
y finit au temps 6.
— Retour à v : plus de voisins.
v finit au temps 7.
— Retour à u : voisin suivant x (maintenant noir, fini en 5).
Arête (u, x) : x noir et descendant de u → arête avant.
— u finit au temps 8.
2. Sommets suivants dans l’ordre alphabétique :
v est déjà noir, puis w est blanc.
— Appel DFS-Visit(w) au temps 9.
— w devient gris (temps 9).
Voisins : y (noir, fini en 6), puis z (blanc).
— Arête (w, y) : y noir.
Comme y n’est pas un descendant de w (il appartient à un
autre arbre DFS), c’est une arête traversante.
— Arête (w, z) : z blanc → arête d’arbre.
Appel DFS-Visit(z) au temps 10.
— z devient gris (temps 10). Voisin : z lui-même (gris).
— Arête (z, z) : boucle sur lui-même, z gris → arête de retour.
— Plus de voisins.
z finit au temps 11.
— w finit au temps 12.
3. Les sommets x, y et z sont déjà noirs.
Fin de l’algorithme.

21
Temps de découverte et de fin
Sommet Temps de découverte d[u] Temps de fin f [u]
u 1 8
v 2 7
y 3 6
x 4 5
w 9 12
z 10 11

Classification des arêtes

Arête Type
(u, v) arbre
(u, x) avant
(v, y) arbre
(y, x) arbre
(x, v) retour
(w, y) traversante
(w, z) arbre
(z, z) retour

Cette classification respecte les règles de l’algorithme DFS.

22
Exercice 22.4-1
On considère le DAG (graphe orienté acyclique) de la figure 22.8. Ce graphe
représente les dépendances entre vêtements pour s’habiller.
Les sommets sont :

belt, jacket, pants, shirt, shoes, socks, tie, watch.

Les arêtes (dépendances) sont les suivantes (ordre alphabétique des listes
d’adjacence) :
— pants → belt
— pants → shoes
— socks → shoes
— shirt → jacket
— shirt → tie
— tie → jacket
— belt → jacket
— jacket, shoes et watch n’ont pas de successeurs.
L’algorithme Topological-Sort effectue un parcours en profondeur (DFS)
sur le graphe, en considérant les sommets dans l’ordre alphabétique pour la
boucle principale, et en parcourant chaque liste d’adjacence dans l’ordre alpha-
bétique (comme dans l’exercice 22.3-2).
Les temps de découverte et de fin sont calculés ci-dessous.

Déroulement du DFS
1. belt (blanc) : découverte au temps 1, devient gris.
Voisin : jacket (blanc).
— jacket : découverte au temps 2, pas de voisin, fin au temps 3.
belt finit au temps 4.
2. jacket est déjà noir.
3. pants (blanc) : découverte au temps 5, devient gris.
Voisins : belt (noir), puis shoes (blanc).
— shoes : découverte au temps 6, pas de voisin, fin au temps 7.
pants finit au temps 8.
4. shirt (blanc) : découverte au temps 9, devient gris.
Voisins : jacket (noir), puis tie (blanc).
— tie : découverte au temps 10, voisin jacket (noir), fin au temps 11.
shirt finit au temps 12.
5. shoes est déjà noir.

23
 6. socks (blanc) : découverte au temps 13, devient gris.
Voisin : shoes (noir).
socks finit au temps 14.
7. tie est déjà noir.
8. watch (blanc) : découverte au temps 15, pas de voisin, fin au temps 16.
Les temps de fin sont récapitulés ci-dessous :
Sommet Temps de fin
belt 4
jacket 3
pants 8
shirt 12
shoes 7
socks 14
tie 11
watch 16
L’ordre topologique est l’ordre décroissant des temps de fin :

watch, socks, shirt, tie, pants, shoes, belt, jacket.

Exercice 22.3-4
Énoncé : Montrer qu’un seul bit par sommet suffit pour stocker la couleur,
en arguant que la procédure DFS produirait le même résultat si la ligne 3 de
DFS-VISIT était supprimée.
Démonstration. Dans la version usuelle de DFS, chaque sommet peut prendre
trois couleurs : BLANC (non découvert), GRIS (découvert mais non terminé)
et NOIR (terminé). La ligne 3 de DFS-Visit positionne le sommet en GRIS au
début de sa visite.
Si l’on supprime cette ligne et que l’on remplace la couleur GRIS par NOIR
dès la découverte, on obtient un algorithme qui n’utilise que deux couleurs
(BLANC/NOIR). Plus précisément, modifions DFS-Visit comme suit :
1. temps = temps + 1
2. u.d = temps
3. [Link] = NOIR // unique bit : visité
4. pour chaque v ∈ Adj[u] : si [Link] = BLANC, alors v.π = u ; DFS-
Visit(v)
5. temps = temps + 1
6. u.f = temps
La couleur GRIS n’apparaît plus. Le test [Link] == BLANC suffit à distin-
guer les sommets non découverts des autres. Les dates d et f , l’arborescence
de père π et la classification des arcs (à l’aide des intervalles [d, f ]) restent
identiques à la version tricolore. Un seul bit par sommet suffit donc.

24
Exercice 22.3-5
Énoncé : Montrer qu’un arc (u, v) est
(a) un arc d’arbre ou un arc avant si et seulement si u.d < v.d < v.f < u.f ,
(b) un arc arrière si et seulement si v.d ≤ u.d < u.f ≤ v.f ,
(c) un arc transverse si et seulement si v.d < v.f < u.d < u.f .
Démonstration. Rappelons le théorème des parenthèses : pour tout couple de
sommets u, v, soit les intervalles [u.d, u.f ] et [v.d, v.f ] sont disjoints, soit l’un
est strictement inclus dans l’autre, la relation d’inclusion correspondant à la
relation ancêtre/descendant dans la forêt DFS.
(a) Arc d’arbre ou arc avant. Un arc d’arbre relie un parent à son enfant
dans la forêt ; un arc avant relie un ancêtre à un descendant non direct.
Dans les deux cas, u est un ancêtre de v, donc d’après le théorème des
parenthèses, [v.d, v.f ] ⊂ [u.d, u.f ], ce qui se traduit par u.d < v.d < v.f <
u.f . Réciproquement, si ces inégalités sont vérifiées, v est descendant de
u et l’arc (u, v) ne peut être ni arrière ni transverse, donc c’est un arc
d’arbre ou avant.
(b) Arc arrière. Un arc arrière relie un descendant à un ancêtre. Ainsi v est
un ancêtre de u, d’où [u.d, u.f ] ⊂ [v.d, v.f ], soit v.d ≤ u.d < u.f ≤ v.f
(l’inégalité large v.d ≤ u.d tient compte du cas où v = u, arc auto-référent).
Réciproquement, ces inégalités impliquent que v est ancêtre de u ; l’arc ne
pouvant être ni d’arbre ni avant (sinon u.d < v.d), il est nécessairement
arrière.
(c) Arc transverse. Un arc transverse relie des sommets sans relation an-
cêtre/descendant. Leurs intervalles sont donc disjoints. Comme l’arc est
dirigé de u vers v et qu’il est exploré après la découverte de u, on doit
avoir v découvert et terminé avant u, soit v.d < v.f < u.d < u.f . Récipro-
quement, cette disjonction exclut toute relation d’ancestralité, donc l’arc
est transverse.

Exercice 22.3-6
Énoncé : Montrer que dans un graphe non orienté, classer une arête {u, v}
comme arête d’arbre ou arête arrière selon que (u, v) ou (v, u) est rencontrée en
premier durant le parcours en profondeur est équivalent à la classification basée
sur l’ordre des quatre types.
Démonstration. Dans un graphe non orienté, DFS ne produit jamais d’arcs
transverses ni d’arcs avant (car chaque arête est explorée dans les deux sens, la
première rencontre détermine un arc d’arbre, la seconde un arc arrière). Lors-
qu’on examine une arête {u, v} depuis le sommet u, deux cas se présentent :

25
 — Si v est BLANC, l’arête devient un arc d’arbre (u, v) (et plus tard l’ex-
ploration depuis v verra u déjà GRIS ou NOIR, ce qui donnera un arc
arrière). Les intervalles vérifient u.d < v.d < v.f < u.f .
— Si v n’est pas BLANC et v ̸= π[u], alors v a déjà été découvert. Dans un
graphe non orienté, v ne peut être qu’un ancêtre de u (pas de transverses).
L’arc (u, v) est donc un arc arrière, ce qui correspond aux inégalités v.d <
u.d < u.f < v.f .
Ainsi, la classification fondée sur l’ordre de rencontre (premier sens = arbre,
second sens = arrière) coïncide exactement avec celle issue des intervalles de
dates : si u.d < v.d l’arête est d’arbre, si v.d < u.d elle est arrière.

Exercice 22.3-7
Énoncé : Réécrire la procédure DFS en utilisant une pile pour éliminer la
récursion.
On propose l’algorithme itératif suivant. La pile stocke des couples (u, état)
où l’état 0 signifie que l’on entre dans le sommet (pré-visite) et l’état 1 que l’on
sort du sommet (post-visite).

Algorithm 6 DFS-itératif(G)
1: for all u ∈ G.V do
2: [Link] ← BLANC
3: u.π ← NIL
4: temps ← 0
5: for all u ∈ G.V do
6: if [Link] == BLANC then
7: [Link]((u, 0))
8: while Pile n’est pas vide do
9: (v, état) ← Pile.Dépiler()
10: if état == 0 then
11: temps ← temps + 1
12: v.d ← temps
13: [Link] ← NOIR
14: [Link]((v, 1)) ▷ pour post-visite
15: for all w ∈ Adj[v] en ordre inverse do
16: if [Link] == BLANC then
17: w.π ← v
18: [Link]((w, 0))
19: else
20: temps ← temps + 1
21: v.f ← temps
return les dates d, f et les pères π

En empilant d’abord le marqueur de sortie (v, 1) puis les voisins dans l’ordre

26
inverse, on garantit que les sommets sont traités dans le même ordre que l’appel
récursif (profondeur d’abord). Le temps d’exécution reste O(|V | + |E|).

Exercice 22.3-8
Énoncé : Donner un contre-exemple à la conjecture : si un graphe orienté G
contient un chemin de u à v, et si u.d < v.d dans un parcours en profondeur de
G, alors v est un descendant de u dans la forêt DFS produite.
Contre-exemple. Considérons le graphe orienté G = (V, E) avec V = {1, 2, 3}
et les arcs
E = {(1, 2), (2, 1), (1, 3)}.
On exécute DFS en commençant par le sommet 1 et en traitant la liste d’adja-
cence dans l’ordre [2, 3].
— DFS-Visit(1) : 1.d = 1. Le premier voisin est 2 (blanc) ⇒ 2.π = 1, appel
récursif.
— DFS-Visit(2) : 2.d = 2. Son seul voisin est 1, qui est gris ⇒ arc arrière.
Fin de 2 : 2.f = 3.
— Retour à 1 : le voisin suivant 3 est blanc ⇒ 3.π = 1, appel.
— DFS-Visit(3) : 3.d = 4, 3.f = 5.
— Retour à 1 : 1.f = 6.
Les dates obtenues sont :

1.d = 1, 2.d = 2, 3.d = 4, 1.f = 6, 2.f = 3, 3.f = 5.

On a u = 2, v = 3. Il existe un chemin de u à v : 2 → 1 → 3. On vérifie

u.d = 2 < v.d = 4. Pourtant, v = 3 n’est pas un descendant de u = 2 dans
la forêt DFS : l’arbre de racine 1 a pour enfants 2 et 3, mais 2 n’a pas de
descendant. Ainsi la conjecture est fausse.

27
Exercice 22.4-2
Soit
G = (V, E)
un DAG et deux sommets
s, t ∈ V.
On souhaite compter le nombre de chemins simples de s à t (un chemin
simple est une séquence de sommets distincts).
Comme G est acyclique, tout chemin est simple.
L’algorithme suivant est linéaire en

|V | + |E|.

Principe On effectue un tri topologique de G (par exemple avec DFS).

On initialise un tableau
count[v]
à 0 pour tout sommet v, puis on pose

count[s] = 1.

On parcourt ensuite les sommets dans l’ordre topologique ; pour chaque som-
met u, on ajoute
count[u]
à
count[v]
pour chaque arête
(u, v) ∈ E.
À la fin,
count[t]
contient le nombre recherché.

Preuve de correction La preuve se fait par récurrence sur l’ordre topolo-

gique.
Lorsqu’on traite un sommet u, tous les chemins de s à u ont déjà été comptés,
car tous les prédécesseurs de u apparaissent avant lui dans l’ordre topologique.
Chaque chemin de s à u peut alors être prolongé par une arête (u, v) pour
former un chemin de s à v.
Comme le graphe est acyclique, aucun chemin n’est compté plusieurs fois.

28
def nb_chemins (G, s , t ) :
# G : d i c t i o n n a i r e {sommet : l i s t e de v o i s i n s }

o r d r e = t r i _ t o p o l o g i q u e (G)

# l i s t e d e s sommets dans l ’ o r d r e t o p o l o g i q u e
count = {v : 0 f o r v in G}

count [ s ] = 1

f o r u in o r d r e :
f o r v in G[ u ] :
count [ v ] += count [ u ]

return count [ t ]
La complexité est :
O(|V | + |E|),
car :

— le tri topologique coûte O(|V | + |E|) ;

— le parcours des arêtes est également linéaire.

Exemple Pour le DAG de la figure 22.8 (les mêmes sommets que ci-dessus),
avec
s = pants et t = jacket,
les chemins possibles sont :

pants → belt → jacket.

Le chemin
pants → shoes
ne mène pas à jacket.
Il existe donc un seul chemin, et l’algorithme retourne :

1.

Avec
s = shirt et t = jacket,
les chemins sont :

shirt → jacket
et

29
 shirt → tie → jacket.
Il y a donc :
2
chemins distincts.
L’exemple donné dans l’énoncé (chemins de p à v) correspond à un autre
DAG, mais la méthode reste identique.

Exercice 22.3-9
Énoncé
Donner un contre-exemple à la conjecture suivante : si un graphe orienté G
contient un chemin de u à v, alors toute recherche en profondeur doit donner
v.d ≤ u.f .

Solution
La conjecture est fausse. Voici un contre-exemple.
Considérons le graphe orienté G = (V, E) avec V = {x, u, v} et les arcs

E = { x → u, u → x, x → v }.

Il existe bien un chemin de u à v, à savoir u → x → v. Choisissons l’ordre

d’examen des sommets dans la boucle extérieure de DFS comme x, puis u, puis
v, et ordonnons les listes d’adjacence de sorte que Adj[x] = [u, v], Adj[u] = [x],
Adj[v] = []. L’exécution de DFS sur ce graphe donne les estampilles suivantes :
— Découvrir x : x.d = 1
— Depuis x, examiner x → u ; u est blanc, donc découvrir u : u.d = 2
— Depuis u, examiner u → x ; x est gris ⇒ arc arrière. Aucun autre voisin,
donc u termine : u.f = 3
— Revenir en x, examiner x → v ; v est blanc, donc découvrir v : v.d = 4
— v termine : v.f = 5, puis x termine : x.f = 6.
On obtient u.f = 3 et v.d = 4, d’où v.d > u.f . Ceci contredit v.d ≤ u.f ,
bien que le chemin u ⇝ v existe.
Ainsi, même en présence d’un chemin de u à v, une DFS peut attribuer des
temps tels que v.d > u.f lorsque le chemin passe par un sommet ancêtre de u
et que l’arête correspondante est un arc arrière.

30
Exercice 22.3-10
Énoncé
Modifier le pseudocode de la recherche en profondeur pour qu’il affiche
chaque arête du graphe orienté G avec son type. Montrer les modifications éven-
tuelles à apporter si G est non orienté.

Solution
Graphe orienté. Lors du parcours de l’arête (u, v), le type se détermine à
partir de la couleur de v :
— BLANC : arc d’arbre (tree edge).
— GRIS : arc arrière (back edge).
— NOIR : si u.d < v.d, c’est un arc avant (forward edge) ; sinon c’est un arc
transverse (cross edge).
On modifie la procédure DFS-Visit pour afficher chaque arête et son type.

Algorithm 7 DFS-Visit orienté avec affichage des types d’arêtes

1: Entrée : sommet u, temps global time, listes d’adjacence Adj
2: time ← time + 1
3: u.d ← time
4: [Link] ← GRIS
5: for chaque v ∈ Adj[u] do
6: if [Link] = BLANC then
7: afficher “(u, v) : arc d’arbre”
8: v.π ← u
9: DFS-Visit(v)
10: else if [Link] = GRIS then
11: afficher “(u, v) : arc arrière”
12: else ▷ v est NOIR
13: if u.d < v.d then
14: afficher “(u, v) : arc avant”
15: else
16: afficher “(u, v) : arc transverse”
17: [Link] ← NOIR
18: time ← time + 1
19: u.f ← time

Graphe non orienté. Dans un graphe non orienté, chaque arête est repré-
sentée deux fois dans les listes d’adjacence. Il faut éviter de la classifier deux
fois. De plus, les arcs avant et transverses n’existent pas (une arête ne peut être
qu’un arc d’arbre ou un arc arrière). On peut marquer les arêtes déjà traitées
(par exemple en maintenant un tableau de booléens pour chaque arête) ou, plus

31
simplement, n’afficher l’arête que lorsqu’elle est examinée dans le sens où v n’est
pas le parent de u. En pratique, quand on explore (u, v) :
— si v est BLANC : c’est une arête d’arbre, on l’affiche et on poursuit la visite.
— si v est GRIS et v ̸= u.π : c’est une arête arrière, on l’affiche (elle sera
rencontrée une seule fois dans ce sens car au moment où l’on examine l’autre
sens, u sera déjà noir et v.π ̸= u).
Il n’est pas nécessaire de mémoriser l’état des arêtes si l’on suit cette règle.
On peut donc modifier DFS-Visit pour un graphe non orienté en remplaçant la
boucle pour par :
1: for chaque v ∈ Adj[u] do
2: if [Link] = BLANC then
3: afficher “{u, v} : arête d’arbre”
4: v.π ← u
5: DFS-Visit(v)
6: else if [Link] = GRIS et v ̸= u.π then
7: afficher “{u, v} : arête arrière”

Exercice 22.3-11
Énoncé
Expliquer comment un sommet u d’un graphe orienté peut se retrouver dans
une arborescence de profondeur ne contenant que u, bien que u possède à la fois
des arcs entrants et sortants dans G.

Solution
Un tel comportement se produit lorsque u est choisi comme racine d’une
nouvelle arborescence par la boucle extérieure de DFS et qu’au moment de sa
découverte, tous ses voisins accessibles par ses arcs sortants sont déjà noirs
(c’est-à-dire déjà entièrement explorés dans des arborescences précédentes). Par
ailleurs, ses arcs entrants proviennent de sommets qui seront explorés plus tard
(ou qui n’ont pas encore été découverts), de sorte qu’ils n’ont pas contribué à
faire entrer u dans une arborescence antérieure.
Plus formellement, notons que l’algorithme DFS explore les sommets dans
l’ordre de la boucle extérieure. Si u apparaît après tous les sommets qui sont
atteignables depuis u, alors au moment où u est découvert, tous ces sommets
ont déjà été visités et terminés. Les arcs sortants de u ne mènent donc qu’à
des sommets noirs, et DFS ne découvre aucun nouveau sommet depuis u. Ainsi
l’arborescence de profondeur issue de u ne contient que u. Les arcs entrants de
u proviennent quant à eux de sommets encore blancs ou déjà noirs appartenant
à d’autres arborescences, ce qui n’empêche pas u de rester racine.
Exemple concret. Soit G avec V = {a, u, b} et les arcs

E = { u → a, b → u }.

32
Supposons que la boucle extérieure de DFS parcourt les sommets dans l’ordre
a, u, b.
— a est visité le premier. Adj[a] = ∅, donc a est découvert puis immédiatement
terminé. a est noir.
— On passe à u. u est blanc, on le découvre (nouvelle racine). On explore
Adj[u] = [a]. Comme a est noir, l’arc u → a est un arc transverse. Aucun
autre voisin, donc u termine. L’arbre contient uniquement u.
— Enfin b est découvert. Son voisin u est noir, l’arc b → u est un arc transverse.
b termine.
Le sommet u possède bien un arc sortant (u → a) et un arc entrant (b → u),
mais son arborescence de profondeur est réduite à lui-même.

Exercice 22.3-12
Énoncé
Montrer que l’on peut utiliser une recherche en profondeur d’un graphe non
orienté G pour identifier les composantes connexes de G, et que la forêt de
profondeur contient autant d’arbres que G a de composantes connexes. Plus
précisément, montrer comment modifier DFS pour qu’il attribue à chaque som-
met v un entier [Link] entre 1 et k (où k est le nombre de composantes connexes
de G) tel que [Link] = [Link] si et seulement si u et v sont dans la même composante
connexe.

Solution
Dans un graphe non orienté, la relation d’accessibilité est une relation d’équi-
valence dont les classes sont les composantes connexes. L’algorithme DFS, lancé
à partir d’un sommet, explore exactement tous les sommets de sa composante
connexe. En effet, chaque appel à DFS-Visit depuis la boucle extérieure découvre
un sommet encore blanc et, par le parcours récursif, visite tous les sommets qui
lui sont reliés par un chemin. Comme le graphe est non orienté, si deux sommets
sont dans la même composante, ils sont mutuellement accessibles ; dès que l’un
est découvert, l’autre le sera dans la même arborescence de profondeur. Ainsi
chaque arbre de la forêt de profondeur correspond exactement à une composante
connexe.
Pour attribuer un numéro de composante, on maintient un compteur global
cc_num initialisé à 0. À chaque fois que la boucle principale de DFS rencontre
un sommet blanc, on incrémente cc_num et l’on affecte cette valeur au champ
[Link] de tout sommet découvert lors de l’appel récursif correspondant.

33
Algorithm 8 DFS modifié pour les composantes connexes
1: Entrée : graphe non orienté G = (V, E) représenté par listes d’adjacence
2: Sortie : pour chaque v ∈ V , un entier [Link]
3: Global : time ← 0, cc_num ← 0
4: for chaque u ∈ V do
5: [Link] ← BLANC
6: u.π ← NIL
7: for chaque u ∈ V do
8: if [Link] = BLANC then
9: cc_num ← cc_num + 1
10: DFS-Visit-CC(u)

Algorithm 9 DFS-Visit-CC(u)
1: time ← time + 1
2: u.d ← time
3: [Link] ← GRIS
4: [Link] ← cc_num ▷ numéro de composante
5: for chaque v ∈ Adj[u] do
6: if [Link] = BLANC then
7: v.π ← u
8: DFS-Visit-CC(v)
9: [Link] ← NOIR
10: time ← time + 1
11: u.f ← time

Correction. Tous les sommets d’une même composante connexe sont mutuel-
lement accessibles. Lorsque le premier d’entre eux est découvert dans la boucle
principale (il est blanc), le parcours récursif visitera tous les sommets de sa com-
posante et leur affectera le même numéro cc_num. Tout sommet déjà numéroté
appartenant à une autre composante ne sera plus jamais blanc, et recevra un
numéro différent lors de son propre appel racine. La forêt de profondeur compte
donc exactement k = cc_num arbres, chacun correspondant à une composante
connexe.

Complexité. La modification n’introduit qu’un coût constant par sommet.

La complexité totale reste O(V + E).

34
Exercice 22.5-1
Énoncé. Comment le nombre de composantes fortement connexes d’un graphe
orienté peut-il changer lorsqu’on ajoute une nouvelle arête ?

Rappel. Deux sommets u et v appartiennent à la même composante fortement

connexe (CFC) s’il existe un chemin de u vers v et un chemin de v vers u.
Le graphe des composantes fortement connexes d’un graphe orienté est tou-
jours un DAG.

Analyse. L’ajout d’une arête dans un graphe orienté peut :

— ne rien changer ;
— diminuer le nombre de composantes fortement connexes ;
— mais ne peut jamais l’augmenter.

Pourquoi le nombre ne peut-il pas augmenter ? Ajouter une arête ajoute

de nouvelles possibilités de chemins dans le graphe. Cela peut rendre certains
sommets mutuellement accessibles, mais cela ne peut jamais détruire une acces-
sibilité déjà existante.
Ainsi, deux sommets qui étaient dans la même CFC avant l’ajout de l’arête
restent dans la même CFC après l’ajout.
Par conséquent, une composante existante ne peut pas être divisée en plu-
sieurs composantes. Le nombre de CFC ne peut donc jamais augmenter.

Pourquoi le nombre peut-il diminuer ? L’ajout d’une arête peut créer un

cycle entre plusieurs composantes du graphe condensé.
Supposons par exemple deux composantes fortement connexes distinctes :

C1 et C2 ,

avec un chemin de C1 vers C2 , mais aucun chemin retour.

Si l’on ajoute une arête permettant d’aller de C2 vers C1 , alors les deux
composantes deviennent mutuellement accessibles et fusionnent en une seule
CFC.

Exemple. Considérons le graphe :

a → b.

Les composantes fortement connexes sont :

{a}, {b}.

Le nombre de CFC vaut donc 2.

Ajoutons l’arête :
b → a.

35
 Le graphe devient :
a ↔ b.
Maintenant :
a ⇝ b et b ⇝ a.
Les deux sommets appartiennent donc à la même composante fortement
connexe :
{a, b}.
Le nombre de CFC passe alors de 2 à 1.

Conclusion. L’ajout d’une arête dans un graphe orienté :

— ne peut jamais augmenter le nombre de composantes fortement connexes ;
— peut le laisser inchangé ;
— peut le diminuer en fusionnant plusieurs composantes.

36
Exercice 22.5-2
Énoncé. Montrer le fonctionnement de la procédure Strongly-Connected-
Components sur le graphe de la figure 22.6.
On suppose :
— que DFS examine les sommets dans l’ordre alphabétique ;
— que les listes d’adjacence sont également triées alphabétiquement.

1. Graphe considéré
Les sommets sont :
u, v, w, x, y, z.
Les arêtes sont :

u → v, u → x, v → y, w → y, w → z, x → v, y → x, z → z.

2. Premier DFS sur G

On exécute DFS dans l’ordre alphabétique :

u, v, w, x, y, z.

Exploration depuis u

u → v → y → x.
— x termine au temps 5 ;
— y termine au temps 6 ;
— v termine au temps 7 ;
— u termine au temps 8.

Exploration depuis w

w → z.
— z termine au temps 11 ;
— w termine au temps 12.

37
3. Temps de fin
Sommet Temps de fin
u 8
v 7
w 12
x 5
y 6
z 11

L’ordre décroissant des temps de fin est donc :

w, z, u, v, y, x.

4. Graphe transposé GT
On inverse toutes les arêtes :

v → u, x → u, y → v, y → w, z → w, v → x, x → y, z → z.

5. Second DFS sur GT

On parcourt les sommets dans l’ordre :

w, z, u, v, y, x.

Depuis w
Aucune arête sortante vers un sommet blanc.
On obtient la composante :
{w}.

Depuis z
z possède une boucle sur lui-même.
On obtient :
{z}.

Depuis u
Aucun successeur non visité.
On obtient :
{u}.

38
Depuis v
On visite :
v → x → y.
Et :
y → v.
Ainsi :
v, x, y
sont mutuellement accessibles.
On obtient :
{v, x, y}.

6. Forêt DFS obtenue

La forêt du second DFS est donc :

{w}, {z}, {u}, {v, x, y}.

Ce sont exactement les composantes fortement connexes du graphe.

39
Exercice 22.5-3
Énoncé. Le professeur Bacon affirme que l’algorithme des composantes forte-
ment connexes serait plus simple si, lors du second DFS, on utilisait le graphe
original au lieu du transposé, et si l’on examinait les sommets dans l’ordre crois-
sant des temps de fin.
Cette variante est-elle toujours correcte ?

Réponse. Non, cette variante est fausse en général.

Contre-exemple
Considérons le graphe :
a → b.
Les composantes fortement connexes sont :

{a}, {b}.

Premier DFS
Supposons que l’on commence par a.

a → b.
Les temps de fin sont :

f (b) = 2, f (a) = 3.

L’ordre croissant des temps de fin est donc :

b, a.

Second DFS sur le graphe original

On commence par b.

b
n’a aucun successeur.
Première composante :
{b}.
Ensuite on visite a.
Mais :
a → b.
Or b est déjà noir.
Le DFS depuis a donne :
{a}.

40
 Dans cet exemple, le résultat reste correct.
Cependant, considérons maintenant :

a ↔ b, b → c.
Les CFC réelles sont :
{a, b}, {c}.
Un premier DFS peut produire :

f (c) < f (b) < f (a).

L’ordre croissant devient :

c, b, a.
Le second DFS sur le graphe original peut alors partir de c, puis atteindre
incorrectement d’autres sommets selon la structure du graphe, mélangeant plu-
sieurs composantes.
Le problème fondamental est le suivant :
Le second DFS doit être effectué sur le graphe transposé afin de «
remonter » les arêtes entre composantes.
Dans l’algorithme correct de Kosaraju :
— le premier DFS ordonne les composantes ;
— le second DFS sur GT isole exactement chaque composante.
Utiliser G au lieu de GT détruit cette propriété essentielle.

Conclusion. L’algorithme proposé par le professeur Bacon n’est pas correct

en général.

41
Exercice 22.5-4
Énoncé. Montrer que pour tout graphe orienté G,

T
GTSCC = GSCC .

Autrement dit, le transposé du graphe des composantes de GT est égal au

graphe des composantes de G.

Rappel
Le graphe des composantes fortement connexes

GSCC

est défini comme suit :

— chaque sommet représente une composante fortement connexe de G ;
— il existe une arête
Ci → Cj
si une arête du graphe original relie un sommet de Ci à un sommet de Cj .

Observation fondamentale
Les composantes fortement connexes de G et de GT sont les mêmes.
En effet :

u⇝v et v ⇝ u
dans G
si et seulement si

v ⇝ u et u ⇝ v
dans GT .
Ainsi, la relation de forte connexité est inchangée par transposition.

Correspondance des arêtes

Supposons qu’il existe une arête :

Ci → Cj

dans
GSCC .
Alors il existe :
u ∈ Ci , v ∈ Cj

42
tels que :
u→v
dans G.
Dans le graphe transposé GT , cette arête devient :

v → u.

Par conséquent, dans

(GT )SCC ,
on obtient l’arête :
Cj → Ci .
Toutes les arêtes sont donc inversées.
Ainsi :
T
(GT )SCC = (GSCC ) .
En transposant les deux côtés :

T
(GT )SCC = GSCC .

Conclusion. Le graphe des composantes fortement connexes est compatible

avec l’opération de transposition :

(GT )SCC = (GSCC )T .

Autrement dit, transposer un graphe inverse simplement les arêtes entre
composantes fortement connexes.

Exercice 22.5-5
Énoncé. Donner un algorithme en temps

O(|V | + |E|)

pour calculer le graphe des composantes fortement connexes d’un graphe orienté

G = (V, E).

L’algorithme doit garantir qu’il existe au plus une arête entre deux sommets
du graphe des composantes.

43
1. Définitions
Soit
G = (V, E)
un graphe orienté.
On note :
SCC(G)
l’ensemble des composantes fortement connexes de G.
Le graphe des composantes (ou graphe condensé) est le graphe :

GSCC = (VSCC , ESCC )

défini par :
— chaque sommet de VSCC représente une composante fortement connexe ;
— il existe une arête
Ci → Cj
si et seulement si :

∃(u, v) ∈ E avec u ∈ Ci , v ∈ Cj , Ci ̸= Cj .

Le graphe des composantes est toujours un DAG.

2. Idée de l’algorithme
L’algorithme se déroule en trois étapes :
1. calculer les composantes fortement connexes ;
2. associer à chaque sommet son identifiant de composante ;
3. parcourir les arêtes originales afin de construire les arêtes du graphe condensé.
Le point délicat consiste à éviter les doublons d’arêtes.

3. Algorithme
Étape 1 : calcul des composantes
On applique l’algorithme de Kosaraju ou de Tarjan.
En temps :
O(|V | + |E|).
Supposons que l’on obtienne :

comp[u]

44
= identifiant de la composante contenant le sommet u.
Supposons également qu’il y ait :

composantes fortement connexes.

Étape 2 : construction du graphe condensé

On initialise :

VSCC = {1, 2, . . . , k}.

Puis on parcourt chaque arête :

(u, v) ∈ E.

Soient :
cu = comp[u], cv = comp[v].
— Si
cu = cv ,
l’arête reste à l’intérieur d’une composante et n’apparaît pas dans le graphe
condensé.
— Sinon, on ajoute l’arête :
cu → cv
au graphe condensé.

Élimination des doublons

Afin d’éviter plusieurs copies d’une même arête entre deux composantes, on
utilise une structure de type ensemble (set) :

ESCC = set().
Chaque insertion :

(cu , cv )
est effectuée une seule fois.

45
4. Pseudo-code
def component_graph (G) :

# Etape 1 : SCC
comp , k = strongly_connected_components (G)

# comp [ u ] = i d e n t i f i a n t de composante

E_scc = set ( )

# Etape 2 : c o n s t r u c t i o n d e s a r e t e s
f o r u in G:
f o r v in G[ u ] :

cu = comp [ u ]
cv = comp [ v ]

i f cu != cv :
E_scc . add ( ( cu , cv ) )

V_scc = { 1 , 2 , . . . , k}

return ( V_scc , E_scc )

5. Preuve de correction
Correction des sommets
Chaque sommet du graphe condensé correspond exactement à une compo-
sante fortement connexe de G.
Ainsi :
VSCC
est correct.

Correction des arêtes

Considérons deux composantes distinctes :

Ci , Cj .

Par définition du graphe des composantes, il existe une arête :

Ci → Cj

46
si et seulement si il existe :
(u, v) ∈ E
avec :
u ∈ Ci , v ∈ Cj .
Or l’algorithme parcourt toutes les arêtes de E.
Ainsi :
— toute arête nécessaire est ajoutée ;
— aucune arête incorrecte n’est ajoutée.
Donc :
ESCC
est correct.

Absence de doublons
Les arêtes sont stockées dans un ensemble.
Par conséquent, même si plusieurs arêtes du graphe original relient les mêmes
composantes, une seule arête apparaît dans le graphe condensé.

6. Complexité
— calcul des SCC :
O(|V | + |E|);
— parcours des arêtes :
O(|E|);
— insertions dans un ensemble :
O(1)
amorti par opération.
Donc la complexité totale est :

O(|V | + |E|).

47
Exercice 22.5-6
Énoncé. Étant donné un graphe orienté

G = (V, E),

construire un graphe
G′ = (V, E ′ )
tel que :
1. G′ possède les mêmes composantes fortement connexes que G ;
2. G′ possède le même graphe des composantes que G ;
3. |E ′ | soit aussi petit que possible.
Décrire un algorithme rapide permettant de calculer G′ .

1. Intuition
Nous voulons conserver uniquement les arêtes essentielles :
— assez d’arêtes pour maintenir la forte connexité à l’intérieur de chaque
composante ;
— assez d’arêtes pour préserver les connexions entre composantes ;
— aucune arête inutile.

2. Structure optimale
Supposons qu’une composante fortement connexe :

contienne :
k
sommets.
Pour que C reste fortement connexe, il faut au moins :

arêtes lorsque :
k > 1.
En effet, un cycle dirigé simple suffit :

v1 → v2 → · · · → vk → v1 .
Ainsi :

48
 — chaque composante de taille k > 1 peut être réduite à un cycle ;
— une composante de taille 1 ne nécessite aucune arête interne.

Entre deux composantes distinctes :

— une seule arête suffit pour représenter chaque arête du graphe condensé.

3. Construction de G′
Étape 1 : calcul des composantes fortement connexes
On calcule les SCC en temps :

O(|V | + |E|).

Étape 2 : réduction interne de chaque composante

Pour chaque composante :

C = {v1 , v2 , . . . , vk },

avec :
k > 1,
on ajoute uniquement les arêtes :

v1 → v2 , v 2 → v3 , ... v k → v1 .
Cela forme un cycle simple fortement connexe.

Étape 3 : arêtes entre composantes

Pour chaque arête du graphe condensé :

Ci → Cj ,

on conserve une unique arête originale :

u→v

avec :
u ∈ Ci , v ∈ Cj .

49
4. Pourquoi cette solution est minimale ?
Minimalité interne
Une composante fortement connexe contenant :

sommets nécessite au moins :

k
arêtes lorsque :
k > 1.
Le cycle simple utilise exactement :

arêtes.
Il est donc optimal.

Minimalité externe
Entre deux composantes distinctes, une seule arête suffit pour préserver le
graphe condensé.
Toute arête supplémentaire serait redondante.

5. Algorithme
def reduce_graph (G) :

SCC = strongly_connected_components (G)

E_prime = set ( )

# Reduction i n t e r n e
f o r C in SCC :

v e r t i c e s = l i s t (C)
k = len ( v e r t i c e s )

if k > 1:
f o r i in range ( k ) :
u = vertices [ i ]
v = v e r t i c e s [ ( i + 1) % k ]

50
 E_prime . add ( ( u , v ) )

# Une a r e t e e n t r e composantes
added = set ( )

f o r ( u , v ) in E :

cu = comp [ u ]
cv = comp [ v ]

i f cu != cv and ( cu , cv ) not in added :

E_prime . add ( ( u , v ) )
added . add ( ( cu , cv ) )

return (V, E_prime )

6. Preuve de correction
Même composantes fortement connexes
Chaque composante est remplacée par un cycle orienté couvrant tous ses
sommets.
Dans un cycle orienté :

u⇝v
pour tous les sommets u, v du cycle.
Ainsi, chaque composante reste fortement connexe.

Aucune nouvelle forte connexité n’est créée entre composantes distinctes, car
les arêtes inter-composantes respectent exactement le graphe condensé original.
Donc les SCC restent inchangées.

Même graphe condensé

Pour chaque arête :
Ci → Cj
du graphe condensé original, une arête correspondante est conservée.
Ainsi le graphe condensé reste identique.

51
7. Complexité
— calcul des SCC :
O(|V | + |E|);
— construction des cycles internes :

O(|V |);

— parcours des arêtes originales :

O(|E|).

La complexité totale est donc :

O(|V | + |E|).

Conclusion
Le graphe réduit
G′ = (V, E ′ )
obtenu :
— conserve exactement les mêmes composantes fortement connexes ;
— conserve exactement le même graphe condensé ;
— possède un nombre minimal d’arêtes ;
— est calculable en temps linéaire.

52