Chap02 Graphes Parcours - Student

Chapitre 2 : Parcours de graphes
1 Graphes et accessibilité
1.1 Définitions de base et vocabulaire
Un graphe est un objet mathématique permettant de modéliser une relation binaire sur un ensemble
fini. Selon que cette relation est asymétrique ou symétrique, le graphe sera orienté ou non.
Définition 1.1
Un graphe orienté G = (S, A) est composé d’un ensemble fini S d’éléments appelés sommets et
d’une partie A de S × S dont les éléments sont appelés arcs.
Définition 1.2
Si (x, y) est un arc d’un graphe orienté, on dit alors :
• que x et y sont les extrémités de cet arc (x l’origine et y la destination) ;
• que x est un prédécesseur de y et que x est un successeur de y.
De plus, si x = y, l’arc (x, x) est appelé une boucle.
Exercice de cours 1.3

Représenter graphiquement le graphe G = (S, A) où S = {1, 2, 3, 4, 5, 6}, A = {(1, 2), (2, 4), (2, 5), (4, 1),
(4, 4), (4, 5), (5, 4), (6, 3)}. Quels sont les successeurs de 2 ? Les prédécesseurs de 5 ?
Définition 1.4
Un graphe non orienté G = (S, A) est composé d’un ensemble fini S d’éléments appelés sommets
et d’un ensemble de paires de S dont les éléments sont appelés arêtes.

Représenter graphiquement le graphe G = (S, A) où S = {1, 2, 3, 4, 5, 6} et A = {{1, 2}, {1, 5}, {5, 2},
{3, 6}}.

Rappeler quelles sont les deux implémentations concrètes de la structure de graphe.
Remarque 1.7
Étant donné un graphe orienté, sa version non orientée est obtenue en supprimant les boucles et en sub-
stituant à chaque arc restant (x, y) la paire {x, y} ♣ . Réciproquement la version orientée d’un graphe non
orienté est obtenue en substituant à chaque arête {x, y} les deux arcs (x, y) et (y, x).
♣. Comme il n’y a pas de doublons dans un ensemble, l’arête {x, y} est présente au plus une fois, même si les arcs
(x, y) et (y, x) étaient tous deux présents dans le graphe initial.
Informatique - MPI Lycée Fermat - 2024/2025 1/28

Combien d’arcs a la version orientée du graphe G de l’exercice de cours 1.5 ? Combien d’arêtes a la version
non orientée du graphe G de l’exercice de cours 1.3 ?
Définition 1.9
Soit G = (S, A) un graphe non orienté (resp. orienté). Soit G0 = (S 0 , A0 ) un graphe non orienté
(resp. orienté). On dit que G0 est un sous-graphe de G si et seulement si S 0 ⊆ S, et A0 ⊆ A.

Donner deux sous-graphes distincts à trois sommets du graphe G de l’exercice de cours 1.5.
Définition 1.11
Soit G = (S, A) un graphe non orienté (resp. orienté). Soit W ⊆ S un sous-ensemble de sommets.
Le sous-graphe de G induit par W est le graphe G0 = (W, A0 ) où A0 = {{x, y} ∈ A | (x, y) ∈ W 2 })
(resp. A0 = {(x, y) ∈ A | (x, y) ∈ W 2 })).

Donner le sous-graphe induit par le graphe G de l’exercice de cours 1.5 sur l’ensemble de sommets {2, 4, 6}.

Donner un sous-graphe de G de l’exercice de cours 1.5 qui ne soit pas un sous-graphe induit.
Définition 1.14
Deux sommets distincts d’un graphe orienté G = (S, A) (resp. non orienté) G sont adjacents
ou voisins s’ils sont les extrémités d’un même arc (respectivement d’une même arête), i.e. si
(x, y) ∈ A (resp. {x, y} ∈ A).
On appelle voisinage d’un sommet x l’ensemble des sommets qui lui sont adjacents, et degré de
x (noté deg(x)) le nombre de tels sommets.
Si x est un sommet d’un graphe orienté, on appelle degré sortant de x (noté d+ (x)) le nombre
de successeurs de x, et degré entrant de x (noté d− (x)) son nombre de prédecesseurs.

Donner les sommets adjacents du sommet 2 dans le graphe G de l’exercice de cours 1.5. En déduire le degré
du sommet 2. Donner le degré sortant du sommet 4 dans le graphe G de l’exercice de cours 1.3

Que vaut la somme des degrés des sommets d’un graphe non orienté ? Que vaut la somme des degrés entrants
(resp. sortants) des sommets d’un graphe orienté ?
Définition 1.17
Soit G = (S, A) un graphe orienté (resp. non orienté). Un chemin (resp. une chaîne) est une suite
finie non vide de sommets c = (s0 , . . . , sp ) telle que : s0 = x, sp = y et ∀k ∈ J0, p−1K, (sk , sk+1 ) ∈ A
(resp. {sk , sk+1 } ∈ A).
La longueur c est p, c’est le nombre d’arcs (resp. d’arêtes) empruntées par ce chemin (resp. cette
chaîne) comptés avec multiplicité.
On dit qu’un chemin (resp. une chaîne) c = (s0 , . . . , sp ) est élémentaire si et seulement si ses
sommets sont deux à deux distincts, i.e. ∀(i, j) ∈ J0, pK2, si = sj ⇒ i = j.

Définition 1.18
Soit G = (S, A) un graphe non orienté(resp. non orienté). Un chemin (resp. une chaîne) s0 = x,
sp = y est un circuit (resp. un cycle) s0 = sp et p > 1 (resp. p > 3).
On dit d’un tel circuit (resp. d’un tel cycle) qu’il est élémentaire si et seulement si le seul sommet
répété est son extrémité, i.e. ∀(i, j) ∈ J0, p − 1K2 , si = sj ⇒ i = j.
Remarque 1.19
La définition ci-dessus de cycle fixe une origine : s0 . Néanmoins on assimilera souvent comme étant un
même cycle les suites s0 , s1 . . . sp et s00 , s01 . . . s0p s’il existe k ∈ J1, p − 1K tel que ∀i ∈ J0, pK, s0i = si+k mod p .

Dans le graphe G de l’exercice de cours 1.3, donner un chemin de longueur 5, un circuit de longueur 6 et un
circuit élémentaire de longueur 3.

Soit un graphe non orienté G = (S, A) à n sommets. Montrer qu’il n’admet pas de chaîne élémentaire de
longueur supérieure à n.
Définition 1.22
Soit G = (S, A) un graphe non orienté (resp. orienté). On dit que :
• G est acyclique dès lors qu’il n’existe aucun cycle élémentaire ;
• G est complet dès lors que A = {{x, y} | (x, y) ∈ A2 } (resp. A = S × S)
Soit G = (S, A) un graphe non orienté, on dit que :
• G est biparti dès lors qu’il existe une partition {W1 , W2 } de ses sommets tel que ∀{u, v} ∈
A, (u, v) ∈ W1 × W2 ∪ W2 × W1 ;
• G est un arbre si et seulement si G est connexe ♣ et acyclique.

Soit un graphe orienté G = (S, A). Montrer que si G est acyclique alors il admet un sommet sans prédécesseur
(resp. sans successeur).

Dessiner le graphe complet à 5 sommets.
1.2 Accessibilité dans le cas non orienté et connexité

Dans toute cette section, on travaille sur un graphe non orienté G = (S, A). On notera n = card(S)
et m = card(A). On supposera que n > 0.
On définit sur S la relation binaire ∼ par ∀(u, v) ∈ S 2 , u ∼ v si et seulement s’il existe une chaîne
reliant u à v.
Remarque 1.25
Dès que plusieurs graphes seront en jeu, on indicera les relations par le graphe concerné afin de lever toute
ambiguïté, par exemple on notera u ∼G v ou u ∼G0 v.
Proposition 1.26
La relation ∼ est une relation d’équivalence.

Démontrer que ∼ est bien une relation d’équivalence.
Remarque 1.28
Pour les graphes non orientés, la relation binaire ∼ peut être définie comme la clôture reflexive transitive
de la relation ∼ sur S définie par A, i.e. telle que ∀(u, v) ∈ S 2 , u ∼ v ↔ u, v ∈ A.
Définition 1.29
Soit ∼ la relation définie ci-avant. On appelle composantes connexes de G les classes d’équiva-
lences de ∼. Elles forment une partition de S ♣ .

Donner les composantes connexes du graphe ci-dessous.
0 1 2
3 4 5
Définition 1.31
Soit W ⊆ S,
• le graphe G est dit connexe si et seulement s’il admet une seule composante connexe ;
• l’ensemble W est dit connexe si et seulement le sous-graphe induit par G sur W est connexe.

Donner l’ensemble des ensembles connexes du graphe de l’exercice de cours 1.30.
Remarque 1.33
De manière équivalente on peut dire qu’un ensemble de sommets W ⊆ S est connexe si et seulement si les
sommets de W sont deux à deux reliés par une chaîne de G n’empruntant que des sommets de W .

Donner un exemple d’ensemble dont les sommets sont 2 à 2 reliés par une chaîne du graphe mais qui ne forme
pas un ensemble connexe.
Proposition 1.35
Soit W ⊆ S, W est une composante connexe de G si et seulement si W est connexe maximale
(au sens de ⊆).

Démontrer le résultat précédent. On pourra s’inspirer de la démonstration du résultat similaire, dans le cas
orienté, se trouvant dans la section suivante (Cf. 1.48).
1.3 Accessibilité dans le cas orienté et forte connexité

Dans toute cette section, on travaille sur un graphe orienté sans boucle G = (S, A). On notera
n = card(S) et m = card(A). On supposera que n > 0.

Définition 1.37
Pour (u, v) ∈ S 2 , on dit que v est accessible depuis u si et seulement s’il existe un chemin de u à
v dans G.
Remarque 1.38
∗
On note parfois u → v pour signifier ”v est accessible depuis u”. Cette notation est justifiée par le fait que
∗
→ est la clôture réflexive transitive de la relation → définie par A.
∗
On parlera parfois des descendants de u pour parler des sommets v tels que u → v et des descendants
∗ ∗
propres pour parler des sommets v tels que u → v et v → 6 u.
Dans la suite, on note ∼ la relation binaire sur S définie par ∀(u, v) ∈ S 2 , u ∼ v si et seulement si
u est accessible depuis v et v est accessible depuis u.
Proposition 1.39
La relation ∼ est une relation d’équivalence.

Démontrer le résultat précédent.
Remarque 1.41
Contrairement à ce qu’on avait pu faire pour les graphes non orientés, la relation binaire ∼ n’est pas la
clôture transitive de la relation définie sur S par ∀(u, v) ∈ S 2 , u v dès lors (u, v) ∈ A et (v, u) ∈ A.
En effet considérons le contre exemple ci-contre. Il y a une unique CFC contenant
les 3 sommets mais il n’existe aucun couple de sommets x et y tels que x y.
Définition 1.42
On appelle composantes fortement connexes (CFC) de G les classes d’équivalences de ∼.

Donner les composantes fortement connexes du graphe ci-dessous.
0 1 2
3 4 5
Définition 1.44
Soit W ⊆ S,
• le graphe G est dit fortement connexe si et seulement s’il admet une seule composante for-
tement connexe ;
• l’ensemble W est dit fortement connexe si et seulement le sous-graphe induit par G sur W
est fortement connexe.
Remarque 1.45
Un ensemble de sommets W ⊆ S est connexe si et seulement si les sommets de W sont deux à deux reliés
par une chaîne de G.

Donner l’ensemble des ensembles fortement connexes du graphe de l’exercice de cours 1.30.
Proposition 1.47
Si W est une composante fortement connexe d’un graphe G alors W est fortement connexe.
Démonstration : Soit W une composante fortement connexe de G. Soient u et v deux sommets de W .

Par définition de CFC, W est une classe d’équivalence de ∼G , donc u ∼ v. Ainsi il existe dans G :
• un chemin γ1 de u à v qu’on note u →G u1 →G . . . →G up−1 →G v ;
• un chemin γ2 de v à u qu’on note v →G v1 →G . . . → vq−1 →G u.
Pour tout i ∈ J1, nJ on a alors ui ∼G v, car il existe dans G
• un chemin de ui à v, à savoir ui →G ui+1 →G . . . →G v ;
• un chemin de v à ui à savoir v →G v1 →G . . . →G vq−1 →G u → u1 →G . . . →G ui−1 → ui
Ainsi pour tout i ∈ J1, pJ, ui ∈ W . De même pour tout i ∈ J1, qJ on a vi ∼G v donc vi ∈ W . Ainsi les
∗
chemins γ1 et γ2 sont aussi des chemins du graphe induit par W , GW = (W, A ∩ W 2 ), on a donc u →GW v
∗
et v →GW w, et donc u ∼GW v.
Ceci étant vrai pour tout couple de sommets (u, v) ∈ W 2 , on en déduit que GW admet une unique compo-
sante fortement connexe, et donc que W est fortement connexe par définition.
Proposition 1.48
Les composantes fortement connexes sont les ensembles de sommets fortement connexes maxi-
maux (au sens de ⊆).
Démonstration :
• Soit un ensemble V ⊆ S fortement connexe et maximal pour l’inclusion. On a V 6= ∅, en effet n’importe
quel singleton {s} avec s ∈ S est fortement connexe donc un sur-ensemble fortement connexe de ∅ ♣ .
Puisque V est fortement connexe, le graphe qu’il induit, GV = (V, A ∩ V 2 ), est fortement connexe.
Autrement dit V admet une unique classe pour la relation ∼GV . Ainsi pour tout (u, v) ∈ V 2 on a u ∼GV v,
et comme les arcs de GV sont des arcs de G on a aussi u ∼G v.
Ainsi V est non vide et ne contient que des éléments deux à deux équivalents pour ∼G , on peut donc
considérer W la classe d’équivalence des éléments de V pour ∼G . Par construction, W est une CFC de
G, et donc en particulier W est fortement connexe d’après la propriété précédente. Or on a V ⊆ W ,
donc par maximalité de V on en déduit V = W , ainsi V est bien une CFC de G.
• Réciproquement considérons V une CFC de G. D’après la propriété précédente, V est alors un ensemble
fortement connexe. Par l’absurde supposons qu’il existe W un sur-ensemble strict de V , i.e. V W,
fortement connexe. On peut alors considérer un sommet w ∈ W \ V . Considérons aussi u un sommet
de V (une CFC est nécessairement non vide) et donc de W . W étant fortement connexe, le graphe
GW = (W, A ∩ W 2 ) est fortement connexe, ainsi il existe dans GW un chemin de u à w et un chemin
de w à u. Puisque les arcs de GW sont des arcs de G, ces chemins existent aussi dans G, ainsi u ∼G w.
Or u ∈ V et V est une classe d’équivalence de ∼G en tant que CFC de G, donc w ∈ V par transitivité.
Absurde.
Ainsi V n’admet est bien fortement connexe maximal.

♣. Cet argument est concluant parce que S 6= ∅

Définition 1.49
On appelle graphe réduit de G le graphe orienté G b = (S, b où S
b A) b est l’ensemble des CFC de G
et n o
Ab = (C1 , C2 ) ∈ Sb2 C1 6= C2 , ∃(s1 , s2 ) ∈ C1 ×C2 , (s1 , s2 ) ∈ A .
Autrement dit le graphe réduit s’obtient en fusionnant les sommets équivalents pour ∼, et en supprimant
les éventuelles boucles apparues lors de ces fusions.
Exemple 1.50
Avant réduction Après réduction

Donner le graphe réduit du graphe ci-dessous.
Lemme 1.52
S’il existe un chemin de Ci à Cj dans G,
b alors il existe un chemin dans G de n’importe quel sommet
de Ci à n’importe quel sommet de Cj .

Démontrer le lemme précédent.
Proposition 1.54
Un graphe réduit est acyclique.
Démonstration : Corollaire direct du lemme : s’il y avait un circuit dans G, b il existerait deux classes dis-
tinctes Ci et Cj telles que dans G il existe un chemin de Ci à Cj et de Cj à Ci . D’après le lemme, pour tout
b
s ∈ Ci et t ∈ Cj il existe alors dans G un chemin de s à t et un chemin de t à s. Ainsi t ∼ s, donc s et t sont
dans la même CFC, soit Ci = Cj . Absurde.
Proposition 1.55
Si G est sans circuit alors :
• chacun de ses sommets est seul dans sa CFC ;
• le graphe réduit de G est G lui-même.

Démontrer la propriété précédente 1.55.

2 Parcours de graphes
2.1 Bordure et parcours : définitions
Dans cette section on travaille sur un graphe orienté G = (S, A) à n sommets, mais les définitions et
résultats se transposent facilement au cas non orienté. On prendra cependant garde à la différence
entre les propositions 2.13 et 2.14.
On appelle permutation des sommets une famille finie de sommets de S dans laquelle chaque
sommet apparaît exactement une fois. Mathématiquement un tel objet est une bijection de J1, nK
dans S, autrement dit c’est juste une numérotation des sommets.
Définition 2.1
La bordure d’un ensemble de sommets V ⊆ S, notée B(V ), est l’ensemble des successeurs des
sommets de V n’étant pas eux-mêmes dans V .
B(V ) = {u ∈ S \ V | ∃v ∈ V, (v, u) ∈ A}

Donner la bordure de l’ensemble encadré dans le graphe ci-dessous.
0 1 2 3
4 5 6
Définition 2.3
Un parcours (Li )i∈J1,nK de G est une permutation des sommets telle que :
∀i ∈ J1, nK, Li ∈ B({Lj | j ∈ J1, iJ }) ou B({Lj | j ∈ J1, iJ }) = ∅
Autrement dit, un parcours est une permutation dans laquelle un sommet n’apparaît que s’il est
dans la bordure des sommets précédents, à moins que celle-ci ne soit vide.
Définition 2.4
Soit L = (Li )i∈J1,nK un parcours de G et i ∈ J1, nK.
On dit que Li est un point de régénération de L dès lors que B({Lj | j ∈ J1, iJ }) = ∅.
Remarque 2.5
Le premier sommet d’un parcours est toujours un point de régénération car B(∅) = ∅.

Donner deux parcours distincts du graphe de l’exercice de cours 2.2. Souligner leurs points de régénération.
Lemme 2.7
Si V ⊆ S est tel que B(V ) = ∅, alors il n’existe aucun chemin allant d’un sommet de V vers un
sommet de S \ V .

Démonstration : Si un tel chemin existait, il passerait nécessairement par un arc (a, b) allant de a ∈ V vers
b ∈ S \ V , ainsi b serait un successeur de a ∈ V tel que b 6∈ V , donc b serait dans B(V ) ce qui nierait sa
vacuité. Absurde.
Remarque 2.8
Attention il peut exister des chemins allant de S \ V vers S car la bordure ne regarde que les successeurs,
pas les prédécesseurs.
2.2 Partition associée à un parcours

Les points de régénération “découpent” le parcours. On associe donc à un parcours le partitionne-
ment de l’ensemble des sommets induit par ce découpage : deux sommets sont dans la même partie
dès lors qu’ils se trouvent entre les deux mêmes points de régénération. C’est le sens de la définition
suivante.
Définition 2.9
Soit L = (Li )i∈J1,nK un parcours de G. On note K son nombre de points de régénération, et
(rk )k∈J1,KK ∈ J1, nKK la suite strictement croissante des indices des points de régénération de L ♣ .
En notant de plus rK+1 = n + 1, on peut définir la partition associée au parcours L comme
étant {Ck | k ∈ J1, KK} où pour tout k ∈ J1, KK, Ck = {Lj | j ∈ Jrk , rk+1 J}.

Donner le partitionnement associé au parcours (2, 6, 5, 1, 0, 4, 3) du graphe de l’exercice de cours 2.2.
Lemme 2.11
Soit L = (Li )i∈J1,nK un parcours de G. Soit (p, q) ∈ J1, nK2 tel que p < q.
S’il existe un chemin de Lp à Lq , alors aucun des Lk pour k ∈Kp, qK n’est point de régénération.
Démonstration : Soit (p, q) ∈ J1, nK2 tels que p < q. Supposons qu’il existe un chemin de Lp à Lq . Par
l’absurde supposons qu’il existe aussi k ∈Kp, qK tel que Lk est un point de régénération. Par définition
B({Lj | j ∈ J1, kJ}) = ∅. On déduit donc du lemme 2.7 qu’il n’existe aucun chemin allant d’un sommet de
{Lj | j ∈ J1, kJ} vers un sommet de {Lj | j ∈ Jk, nK}. Le chemin de Lp à Lq contredit ce fait. Absurde.
Lemme 2.12
Soit L = (Li )i∈J1,nK un parcours de G. Soit Lr pour r ∈ J1, nK un point de régénération de L.
Notons Cr la partie associée à ce point de régénération dans le partition associée à L.
Tout sommet de Cr est accessible depuis Lr par un chemin dont tous les sommets sont dans Cr .
Démonstration : Par définition de la partition associée à un parcours, il existe q ∈ J1, nK tel que Cr =
{Lr , Lr+1 , . . . , Lq }. On peut alors montrer par récurrence forte et finie sur k ∈ Jr, qK la propriété suivante.
Hk : il existe un chemin de Lr vers Lk dont tous les sommets sont dans Cr
• Si k = r alors le chemin réduit au sommet Lr convient, ainsi Hr est vraie.

• Soit k ∈ Jr, qJ. Supposons que ∀i ∈ Jr, kK, Hi est vraie. Montrons Hk+1 . Puisque Lk+1 ∈ Cr et k + 1 6= r,
Lk+1 n’est pas un point de régénération (par définition de la décomposition associée à un parcours).
Ainsi B({Lj | j ∈ J1, k + 1J}) 6= ∅, donc par définition d’un parcours Lk+1 ∈ B({Lj | j ∈ J1, k + 1J})
nécessairement. Comme B({Lj | j ∈ J1, rJ} = ∅ (car Lr est point de régénération), on en déduit que
Lk+1 est successeur d’un sommets de Lr , Lr+1 . . . Lk . Il existe donc i0 ∈ Jr, kK tel que (Li0 , Lk+1 ) ∈ A.
♣. Ainsi les points de régénération sont les (Lrk )k∈J1,KK .

Or d’après Hi0 , il existe un chemin de Lr à Li0 dont tous les sommets sont dans Cr . En composant ce
chemin avec l’arc (Li0 , Lk+1 ), on obtient bien un chemin de Lr à Lk+1 dont tous les sommets sont dans
Cr . Ainsi Hk+1 est vraie.

Proposition 2.13
Dans un graphe non orienté, la partition associée à un parcours quelconque est la décomposition
en composantes connexes.
Démonstration : C’est un corollaire des deux lemmes précédents.

En effet si deux sommets sont dans une même classe C du parcours, d’après le lemme 2.12 (dans sa version
non orientée) ils sont reliés par une chaîne qui ne passe que par des sommets de cette classe. Ainsi une
classe du parcours est un ensemble de sommets connexe. De plus il est connexe maximal, car les sommets
des autres classes ne peuvent être reliés à ces sommets par contraposée du lemme 2.11 (en s’appuyant sur
un point de régénération qui sépare C de l’autre sommet dans le parcours).
Proposition 2.14
Dans un graphe orienté, un parcours offre une partition dont la décomposition en CFC est un
raffinement. Autrement dit les parties associées à un parcours sont toujours des unions de CFC.
Démonstration : C’est un corollaire du lemme 2.11.

Il suffit de montrer qu’une même CFC ne s’étale pas sur plusieurs parties du parcours. Soient Li et Lj deux
sommets deux sommets d’une même CFC. Quitte à les échanger on peut supposer que i < j. Par définition
de CFC, il existe en particulier un chemin de Li à Lj . Donc d’après le lemme 2.11, aucun des Lk pour
k ∈Ki, jK n’est point de régénération. Par définition de la partition associée à un parcours, cela signifie que
Li et Lj sont nécessairement dans la même partie du parcours.
Exemple 2.15
Le parcours (a, c, b, d, e) (dont on a souligné les points de régénération) du graphe ci-dessous conduit à la
partition {a, c, b}, {d}, {e} de S. On remarque que les composantes fortement connexes sont {a, b}, {c},

{d} et finalement {e}.

2 5
c e
1 3 4
a b d
2.3 Parcours particuliers

Définition 2.16
Soit L = (Li )i∈J1,nK un parcours de G.
Pour k ∈ J1, nK et i ∈ J1, kJ, on dit que Li est ouvert à l’étape k dès lors que Succ(Li ) 6⊆
{Lj | j ∈ J1, kJ} ♣ , autrement dit si Li “contribue” à la bordure de {Lj | j ∈ J1, kJ}.

Donner, à chaque étape k du parcours l’ensemble des sommets ouverts à l’étape k lors du parcours
(2, 6, 5, 1, 0, 4, 3) du graphe de l’exercice de cours 2.2.
♣. Succ(Li ) est l’ensemble des successeurs du sommet Li

Définition 2.18
Soit L = (Li )i∈J1,nK un parcours de G.
• On dit que L est un parcours en largeur de G dès lors que chaque sommet du parcours qui
n’est pas point de régénération est successeur du premier sommet ouvert à cette étape, i.e. ∀k ∈
J1, nK, B({Lj | j ∈ J1, kJ}) = ∅ ou Lk ∈ Succ(Li0 ) avec i0 = min {i ∈ J1, kJ | Li ouvert à l’étape k}.
• On dit que L est un parcours en profondeur de G dès lors chaque sommet du parcours qui
n’est pas point de régénération est successeur du dernier sommet ouvert à cette étape, i.e. ∀k ∈
J1, nK, B({Lj | j ∈ J1, kJ}) = ∅ ou Lk ∈ Succ(Li0 ) avec i0 = max {i ∈ J1, kJ | Li ouvert à l’étape k}.
Exemple 2.19
2 4 5 4 5 3
c d f c d f
a b e a b e
1 3 6 1 2 6
Parcours largeur Parcours profondeur

3 5 4 5 6 1
c d f c d f
a b e a b e
2 6 1 4 2 3
Parcours ni largeur ni profondeur Parcours largeur et profondeur

Justifier les affirmations de l’exemple 2.3.

Donner une forme de graphe orienté à n sommets pour lequel tous les parcours sont à la fois des parcours en
largeur et en profondeur.
2.4 Forêt associée à un parcours

Dans un parcours L, les sommets qui ne sont pas point de régénération apparaissent dans le parcours
après un de leur prédécesseur. Une forêt associée à un parcours représente le choix, pour chaque
sommet non point de régénération, d’un père, à savoir un prédécesseur qui le précède dans le
parcours. L’ensemble de tels arcs père-sommet forme un graphe acyclique ♣ , c’est pourquoi on parle
de forêt.
Combien d’arcs a la forêt associée à un parcours d’un graphe à n sommets qui a p points de régénération ?
Dans le cas d’un parcours en largeur (resp. en profondeur), le père d’un sommet est fixé pour chaque
sommet Lk (non point de régénération) comme étant le premier (resp. dernier) sommet ouvert à
l’étape k. Aussi la forêt associé à un tel parcours est unique.
♣. les arcs sont de la forme (Li , Lj ) avec i < j, assurant la stricte croissance des indices le long d’un chemin

On considère le parcours [a, b, c, d] du graphe ci-dessous. b
• Donner la forêt associée à ce parcours vu comme un parcours en largeur.
a d
• Donner la forêt associée à ce parcours vu comme un parcours en profondeur.
• Donner une autre forêt associée à ce parcours vu comme un parcours quelconque. c
Remarque 2.24
La forêt associée à un parcours en largeur (resp. profondeur) est aussi une forêt associée à ce parcours vu
comme un parcours quelconque, mais la réciproque n’est pas toujours vraie.
Remarque 2.25
On peut définir formellement la notion de forêt associée à un parcours L de G = (S, A) comme un sous-
graphe (S, A0 ) où l’ensemble d’arcs A0 associe un père à chaque sommet non point de régénération dans L.
• Si L est un parcours en largeur (resp. en profondeur), pour tout k ∈ J1, nK tel que Lk n’est pas point de
régénération, on peut associer à k l’indice π(k) du premier (resp. dernier) sommet ouvert à l’étape k
de L, ainsi π(k) < k et (Lπ(k) , Lk ) est un arc de G. Dans ce cas la forêt associée au parcours en largeur
(resp. en profondeur) L est définie par l’ensemble A0 ci-dessous.
• Si L est un parcours quelconque, pour tout k ∈ J1, nK tel que Lk n’est pas point de régénération, on peut
associer à k un indice π(k) < k tel que Lk ∈ Succ(Lπ(k) ), i.e. tel que (Lπ(k) , Lk ) est un arc de G. Dans ce
cas une forêt associée au parcours L est définie par l’ensemble A0 ci-dessous.
A0 = {(Lπ(k) , Lk ) | Lk n’est pas point de régénération }
2.5 Implémentation de parcours

Attention : L’algorithme 1 donné ci-dessous a un intérêt purement pédagogique, il ne doit en
aucun cas être implémenté directement pour calculer un parcours.
Algorithme 1 : Parcours naïf
Entrée : Un graphe G = (S, A)
Sortie : Un parcours de G
1 n ← card(S) ;
2 L ← liste vide ;
3 Visités ← ∅ ;
4 pour k = 1 à n faire
5 si B(L) 6= ∅ alors
6 Choisir un sommet u dans B(L) ;
7 sinon
8 Choisir un sommet u quelconque de S \ Visités ;
9 Ajouter u à Visités ;
10 L ← L · u;
11 retourner L

Donner un invariant liant les variables L et Visités dans l’algorithme 1.

Proposition 2.27
Les parcours de G = (S, A) sont exactement les listes pouvant être fabriquées par l’algorithme 1.
On remarque que B(L) évolue peu entre chaque tour, puisqu’un seul élément est ajouté à L. Tirant
profit de cette observation, on raffine l’algorithme précédent en l’algorithme 2.
Algorithme 2 : Parcours avec ensemble todo
Entrée : Un graphe G = (S, A)
Sortie : Un parcours de G
1 L ← liste vide ;
2 Visités ← ∅ ;
3 Procedure ExploreDescendants :
Hypothèse : B(Visités) = ∅
Entrée : s ∈ S \ Visités
Effet : Ajoute à L et à Visités s et tous ses descendants, de manière à ce que L reste un
parcours partiel ♥ .
4 todo ← {s} ;
5 tant que todo 6= ∅ faire
6 Choisir un sommet u ∈ todo ;
7 Ôter u de todo ;
8 / Visités alors
si u ∈
9 Ajouter u à Visités ;
10 L ← L · u;
11 pour tout v ∈ succ(u) faire
12 Ajouter v à todo ;
13 tant que S \Visités 6= ∅ faire

14 s ← un sommet de S \Visités ;
15 ExploreDescendants(s) ;
16 retourner L ;

Donner un invariant liant B(L), todo et Visités dans l’algorithme 2.

Comment modifier l’algorithme 2, afin de réaliser efficacement le test ligne 13 ?
Proposition 2.30
Si le graphe G est représenté par table de listes d’adjacence ♣ , l’algorithme 2 effectue O(n + m)
itérations de la boucle ligne 5 et O(m) itérations de la boucle ligne 11.
Démonstration : Ces complexités découlent du fait que la boucle tant que de la ligne 5 est exécutée une
fois pour chaque ajout d’un élément dans todo, en effet chaque tour de cette boucle extrait un élément de
todo. Estimons donc le nombre de fois qu’un sommet est ajouté à todo.
Remarquons au préalable que le corps de la conditionnelle si ligne 8 est exécuté une seule fois par sommets
du graphe. En effet, pour un sommet u ∈ S donné, u n’est initialement pas dans Visités, y est ajouté si le
corps du si ligne 8 est exécuté pour u, et ne peut par la suite plus en être retiré, ce qui exclut d’entrer à
nouveau dans le si ligne 8.
♥. Pour les besoins des énoncés, on dira ici qu’une séquence de sommets L est un parcours partiel de G si L est un
parcours du sous-graphe de G induit par l’ensemble des sommets figurant dans L.

• Chaque point de régénération est ajouté dans todo une fois ligne 4 ;
• Un sommet v est ajouté dans todo ligne 12 à chaque exécution de la boucle ligne 8 telle que u est un
prédécesseur de v, ainsi on en déduit que chaque sommet v est ajouté d− (v) fois à la ligne 12.
Finalement par sommation v∈S (1 + d− (v)) = O(n + m).
P
Il est important de remarquer ici que l’algorithme de parcours ne se contente pas de visiter une fois chaque
sommet, mais visite en fait aussi une fois chaque arc du graphe.
Remarque 2.31
Intéressons nous aux structures de données concrètes usuellement utilisées pour implémenter les objets
todo et Visités.
• Les opérations requises pour l’objet todo sont l’ajout et l’extraction, aussi peut-on se contenter d’une
structure de pile ou de file pour l’implémenter. Les lignes 4, 5, 6, 7 et 12 se font alors en O(1).
• Les opérations requises pour l’objet Visités sont le test d’appartenance et l’ajout. On reconnaît le type
de données abstrait Ensemble. Dans le cas, usuel, où l’ensemble S des sommets peut être assimilé à
J0, n − 1K on utilise un tableau de booléens indicé par S = J0, n − 1K pour implémenter Visités. Les
lignes 8 et 9 se font alors en O(1).
Dans le cas où S = J0, n − 1K, le cumul des recherches des points de régénération (ligne 14) peut se faire
en O(n) ♣ . Ainsi on retiendra que, sous ces hypothèses, la complexité d’un parcours de graphe est en
O(n + m).
Remarque 2.32
Le choix d’une implémentation de todo au moyen d’une pile (resp. d’une file) conduit à un parcours en
profondeur (resp. largeur).
2.6 Implémentations en OCaml

Dans toute cette section, on suppose que l’ensemble des sommets du graphe est J0, n − 1K et qu’il
est représenté par une table de listes de successeurs. Ainsi le type utilisé (en OCaml) est le suivant.
1 type graphe = int list array
Par programmation impérative. On fournit ci-dessous une implémentation en OCaml de l’al-

gorithme de parcours présenté dans la section précédente. L’utilisation du module Stack pour la
gestion de l’ensemble todo assure un parcours en profondeur du graphe. Si on remplace l’utilisation
du module Stack par un module Queue, on obtient un parcours en largeur.
1 let parcours_avec_todo (g: graphe): int list =

2 (* nombre de sommets dans le graphe *)
3 let n = Array.length g in
4 (* parcours que nous sommes en train de fabriquer *)
5 let l = ref [] in
6 (* un sommet i est déjà traité et apparaît ds l ssi visité.(i) *)
7 let visites = Array.make n false in
8 let explore_descendants (s: int) : unit =
9 (* todo list *)
10 let todo = Stack.create () in
11 (* on ajoute s dans la pile des sommets à traiter *)
♣. on le verra dans la section suivante

12 Stack.push s todo;
13 while (not (Stack.is_empty todo)) do
14 (* on extrait un élément dans la pile des sommets à traiter *)
15 let u = Stack.pop todo in
16 (* on teste si u a déjà été visité *)
17 if not (visites.(u)) then
18 (* si ce n'est pas le cas on le visite *)
19 begin
20 (* on l'ajoute aux visités pour ne pas le revisiter plus tard *)
21 visites.(u) <- true;
22 (* on ajoute u au parcours *)
23 l := u :: !l;
24 (* on ajoute les successeurs de u dans todo *)
25 List.iter (fun v -> Stack.push v todo) g.(u)
26 end
27 done
28 in
29
30 (* fonction auxiliaire retournant l'indice du premier sommet non visités

31 d'indice supérieur à j < n, n s'il n'en existe pas *)
32 let trouve_non_visites (j: int) : int =
33 let i = ref j in
34 while (!i < n && visites.(!i)) do
35 incr i
36 done;
37 !i
38 in
39
40 let s = ref 0 in
41 (* tant qu'il existe un sommet s non encore visité *)
42 while (!s < n) do
43 (* on visite s et ses descendants *)
44 explore_descendants !s;
45 (* on calcule un nouveau sommet s non encore visité *)
46 s := trouve_non_visites (!s + 1)
47 done;
48 List.rev !l
49
En utilisant la récursivité. Dans le cas d’un parcours en profondeur, on peut utiliser la pile des
appels récursifs pour gérer les sommets à visiter plutôt qu’une pile explicite. En remplaçant la fonc-
tion explore_descendants de l’implémentation précédente par la fonction récursive ci-dessous, on
obtient une nouvelle implémentation de parcours en profondeur.
1 let rec explore_descendants (s: int) : unit =
2 (* on teste si u a déjà été visité *)
3 if not (visites.(s)) then
4 (* si ce n'est pas le cas on le visite *)
5 begin
6 (* on l'ajoute aux visités pour ne pas le revisiter plus tard *)
7 visites.(s) <- true;

8 (* on ajoute s au parcours *)
9 l := s :: !l;
10 (* on visite les successeurs de s au moyen d'appels récursifs *)
11 List.iter (fun v -> explore_descendants v) g.(s)
12 end
Comme annoncé précédemment (Remarque 2.31), nous avons ici précisé comment effectuer la recherche des
points de régénération. Donner le coût cumulé de ces recherches dans les implémentations ci-dessus.
Remarque 2.34
Dans cette section, nous avons fourni une implémentation “générique” de parcours : on se contente de
calculer une liste de sommets qui forme un parcours. Il faut être capable d’adapter cet algorithme pour
répondre à divers problèmes, par exemple : le langage d’un automate est-il vide ? Tous les sommets sont-
ils accessibles depuis un certain sommet ? Combien de composantes connexes a ce graphe non orienté ?
Donner un circuit de ce graphe orienté ….
3 Interlude : graphes implicites

Les algorithmes et structures de données présentées dans ce chapitre supposent que les graphes
manipulés sont des graphes pour lesquels nous avons accès aux ensembles de sommets et d’arcs ♣ .
Il est toutefois fréquent de devoir manipuler des graphes pour lesquels cette hypothèse n’est pas vé-
rifiée. Considérons par exemple le graphe du Web, dont les sommets sont les pages Web (identifiées
par leur URL) et dont les arcs correspondent à des liens hypertextes. Les données qui définissent
ce graphe ne sont pas accessibles sur une seule machine, mais l’information est au contraire distri-
buée sur plusieurs machines : les sites, et donc les pages sont hébergées sur différents serveurs, et
chaque page contient en elle-même ses liens sortants. La taille du graphe, et son caractère dyna-
mique rendent inenvisageable un algorithme contenant un “Pour chaque arc u du graphe du Web
...”.
Mentionnons aussi les graphes qui sont mathématiquement bien définis mais dont la taille rend
impossible la description exhaustive en machine. C’est le cas par exemple du graphe des échecs :
les sommets sont les différents états possibles de la partie (il y en a un nombre fini), ces états sont
reliés par des arcs représentant les coups pouvant être joués.
On dit de tels graphes que nous en avons une définition implicite : étant donné un sommet il est
possible de calculer la liste de ses successeurs, mais il est impossible d’obtenir une liste explicite des
sommets ou des arcs du graphe. De tels graphes sont donc représentés en machine par une fonction
qui calcule les successeurs d’un sommet. En OCaml et pour le graphe des échecs par exemple, on
aurait des définitions de types de la forme suivante.
1 type etat = ... (* Une définition de type pour un plateau d'échec *)
2
3 let init : etat =

4 ...
5 (* L'état initial de la partie d'échec *)
6
7 let successeurs (e: etat): etat list =

8 ...
9 (* La liste des états pouvant être obtenus après un coup depuis e *)
♣. on rédige cette partie pour le cas des graphes orientés, mais cela est vrai aussi pour des graphes non orientés

Dans le cas du graphe du Web on pourrait avoir les définitions de types suivantes.
1 type page = string (* Une page Web est identifiée par son URL *)
2
3 let successeurs (p: page): page list =

4 ...
5 (* La liste des pages accessibles en suivant un lien depuis p *)
Remarquons qu’avec de telles définitions il est possible de faire des parcours partiels (en profondeur,
en largeur, ou autres) des graphes implicites ainsi représentés. De plus, afin de réaliser de tels
parcours, on se dotera d’une structure de données pour représenter l’ensemble des sommets visités
(un ensemble d’etat ou de page ci-dessus), ainsi que des structures de mise en attente (pile, file,
ou autres, d’etat ou de page). Dans le cas du graphe du Web par exemple, on pourrait opter en
OCaml pour un ensemble des visités représenté au moyen d’une (string, bool) Hashtbl.t et une
structure de mise en attente de type String Queue.t.
4 Rangements particuliers des sommets

Dans cette section on étudie d’autres permutations remarquables ♣ pour les graphes orientés. Ainsi
dans toute cette section on considère G = (S, A) un graphe orienté. On notera n = card(S) et
m = card(A).
4.1 Tri topologique
Définition 4.1
Soit T = (Ti )i∈J1,nK une permutation des sommets de G.
On dit que T est un tri topologique de G dès lors que ∀(i, j) ∈ J1, nK2 , (Ti , Tj ) ∈ A ⇒ i 6 j,
autrement dit tous les arcs de G ont leur origine placée avant leur destination dans T .

Donner un tri topologique du graphe ci-dessous.
0 1 2
3 4 5 6 7 8
9 10 11

Que peut-on dire du premier sommet d’un tri topologique ?

Y a-t-il unicité du tri topologique ?
♣. autres que les parcours

Proposition 4.5
Un graphe admet un tri topologique si et seulement s’il est sans circuit.
Démonstration : Il s’agit de démontrer les deux implications.

• Si G admet un tri topologique des sommets (T1 , T2 , . . . , Tn ) et un circuit (Ti1 , Ti2 , . . . Tip = Ti1 ), on a
i1 6 i2 . . . 6 ip = i1 donc Ti1 = Ti2 = . . . = Tip donc G est sans circuit.
• On montre la réciproque par induction sur n. La propriété est bien sûr vraie si n = 1. Soit n > 2.
Supposons qu’elle le soit pour tout graphe à n − 1 sommets. Soit G un graphe à n sommets sans circuit.
Il existe au moins un sommet s0 sans successeurs car dans le cas contraire, on pourrait construire un
chemin infini. Or comme il y a un nombre fini de sommets, l’un d’eux serait nécessairement répété dans
ce chemin infini qui présenterait donc un circuit, ce qui est absurde.
Le sous-graphe G0 de G induit par S \ {s0 } a n − 1 sommets et ne possède pas de circuits. Par hypothèse
d’induction il existe donc un tri topologique L0 des sommets de G0 . En ajoutant le sommet s0 à la fin
du tri L0 on obtient un tri topologique des sommets de G, puisque les seuls arcs de G qui ne sont pas
dans G0 ont s0 comme extrémité, et même comme destination puisque s0 est sans successeur dans G.
Autrement dit ce sont bien des arcs qui vont d’un sommet de L0 , le début de L, vers s0 , la fin de L.

4.2 Tri préfixe

La notion de tri topologique introduite dans la section précédente n’a de sens que dans les graphes
sans circuit. On “relâche” la définition de tri topologique pour obtenir celle de tri préfixe : c’est une
permutation des sommets du graphe qui donne un tri topologique quand on passe au graphe réduit.
Définition 4.6
Soit T = (Ti )i∈J1,nK une permutation des sommets de G.
On définit le rang d’un sommet u dans la permutation T , noté rgT (u), comme étant le plus petit
indice d’un élément dans la même CFC que u.
déf
rgT (u) = min{i ∈ J1, nK | Ti ∼G u}
On dit que T est un tri préfixe de G dès lors que ∀(u, v) ∈ S 2 , (u, v) ∈ A ⇒ rgT (u) 6 rgT (v).
Remarque 4.7
Dans un tri topologique, on demande que si (u, v) est une arête du graphe alors u est placé avant v dans le tri
topologique ; dans le cas du tri préfixe on demande seulement que la composante connexe de u apparaisse
avant la composante connexe de v au sens où un des éléments de cette composante apparaît avant tous les
éléments de l’autre composante.
Lemme 4.8
Pour tout (u, v) ∈ S 2 et toute permutation des sommets T , u ∼ v ⇔ rgT (u) = rgT (v).
Démonstration :
• Si u ∼G v alors {i ∈ J1, nK | Ti ∼G u} = {i ∈ J1, nK | Ti ∼G v} et donc rgT (u) = rgT (v).
• Si rgT (u) = rgT (v) alors soit i = rgT (v), on a donc u ∼ Ti ∼ v.


Dans les permutations suivantes des sommets du graphe ci-contre, donner le rang de c f g
chaque sommet et dire si cette permutation est un tri préfixe.
• [g, d, e, f, a, c, b] • [d, f, a, e, g, c, b] • [d, a, g, e, b, c, f ] • [f, d, b, g, a, c, e] a b d e
Proposition 4.10
Un tri topologique est un tri préfixe.
Un tri préfixe d’un graphe sans circuit est un tri topologique.
Démonstration : S’il existe un tri topologique, le graphe est nécessairement sans circuit, et donc sa décom-
position en CFC est la partition en singletons. Ainsi le rang de n’importe quel sommet Ti est simplement
i, son propre indice puisqu’il est le seul, et donc le premier, représentant de sa classe. La condition sur T
pour qu’il soit tri préfixe se réécrit alors exactement comme la condition pour qu’il soit un tri topologique :
∀(Ti , Tj ) ∈ S 2 , (Ti , Tj ) ∈ A ⇒ i = rgT (Ti ) 6 rgT (Tj ) = j

Supposons connu la décomposition en CFC de G.
1. Connaissant un tri préfixe de G, comment obtenir un tri topologique de son graphe réduit G
b?
2. Connaissant un tri topologique du graphe réduit G, comment obtenir un tri préfixe de G ?
b
Calcul d’un tri préfixe. On s’intéresse à la mise en place d’un algorithme permettant le calcul
d’un tri préfixe. On remarque le fait suivant : si tous les descendants stricts d’un sommet u (les
descendants de u qui ne sont pas dans la même composante fortement connexe que u) sont déjà
placés dans une liste, alors on peut placer u en tête de cette liste.
Justifier cette affirmation.
Ainsi on construit le tri préfixe de la fin vers le début en adoptant la politique suivante : on ajoute
x en tête après que tous ses descendants stricts ont été ajoutés. On remarque que cet ajout corres-
pond alors au moment où on ferme l’appel récursif à explore_descendants lors d’un parcours en
profondeur. On implémente donc cette politique avec un algorithme récursif. La fonction Insérer
prend en argument un sommet x et insére le sommet x et ses descendants non encore ajoutés au
tri préfixe en cours de calcul. Si x n’est pas encore visité, on appelle récursivement Insérer sur les
descendants de x afin de s’assurer que tous les descendants de x sont déjà rangés dans le tri préfixe,

puis on ajoute x en tête du tri préfixe.
Algorithme 3 : Calcul d’un tri préfixe
Entrée : Un graphe orienté G = (S, A) représenté par une table de listes de successeurs
Sortie : Un tri préfixe des sommets de G
1 Res ← liste vide ;
2 Ouverts ← ∅ ;
3 Fermés ← ∅ ;
4 Procedure Insérer(s) :
Entrée : s ∈ S
Effet : Modifie Fermés et Res de sorte que Fermés contienne s et tous ses descendants
(sauf ceux qui sont dans Ouverts) et que Res reste un tri préfixe de Fermés
5 / Ouverts et s ∈
si s ∈ / Fermés alors
6 Ajouter s à Ouverts ;
7 pour tout x ∈ Succ(s) faire
8 Insérer(x) ;
9 Supprimer s de Ouverts ;
10 Ajouter s à Fermés ;
11 Res ← s · Res ;
12 tant que S \Fermés 6= ∅ faire
13 s ← un sommet de S \Fermés ;
14 Insérer(s) ;
15 retourner Res ;

Donner un invariant liant les ensembles Ouverts et Fermés.
Que peut-on dire de l’ensemble Ouverts à la ligne 13 ?

Exécuter l’algorithme précédent sur le graphe ci-contre, en choisissant les points c f g
de régénération selon les ordres suivants.
a b d e
• [a, b, c, d, e, f, g] • [g, f, e, d, c, b, a]
5 Calcul de plus courts chemins

L’algorithme A? , de la section suivante, sera présenté de manière incrémentale par rapport à l’algo-
rithme de Dijkstra. Pour cette raison on rappelle ici l’algorithme de Dijkstra, on ne redonne pas les
résultats de correction et de complexité de l’algorithme, on renvoit pour cela aux cours de première
année.
Ainsi dans toute cette section on considère G = (S, A, c) un graphe orienté pondéré où c : A → R+ .
On notera n = card(S) et m = card(A). Étant donnés deux sommets u et v de S, on définit la
distance de u à v dans G, ce que l’on note d(u, v), comme étant la plus petite longueur d’un chemin
de u à v dans G. Dans le cas où un tel chemin n’existe pas, on convient que d(u, v) = +∞.
Donner la définition formelle de d, comme un min sur un ensemble qui admet un minimum ou qui est vide.

Supposons que γ = γ0 γ1 . . . γq est un chemin de longueur minimale, i.e. de longueur d(γ0 , γq ). Soit (i, j) ∈
J[, 0K, q]2 tel que i 6 j. Montrer que le sous-chemin γi γi+1 . . . γj est aussi un chemin minimal (de γi à γj ).
5.1 L’algorithme de Dijkstra
Algorithme 4 : Dijkstra
Entrée : Un graphe pondéré G = (S, A, c) où c : A → R+ , une source s ∈ S
Sortie : Une table indexée par S donnant la distance depuis s de chaque sommet de G
1 Initialiser µ[u] à +∞ pour chaque u ∈ S ;
2 Initialiser π[u] à ?? pour chaque u ∈ S ;
3 µ[s] ← 0 ; (* La source est à distance 0 d'elle-même *)
4 π[s] ← s ; (* La source est la racine de l’arborescence *)
5 todo ← {s} ; (* La source est le premier sommet à traiter*)
6 Procedure Relâcher((u, v)) :
Entrée : u et v deux sommets voisins dans G ;
7 si µ[u] + c((u, v)) < µ[v] alors
8 µ[v] ← µ[u] + c((u, v)) ;
9 π[v] ← u ;
12 Extraire de todo un sommet u minimisant µ[u] ;
13 pour tout v ∈ succ(u) faire
14 Relâcher(u, v)
15 retourner µ

Quelle structure de donnée concrète est adaptée pour implémenter l’ensemble todo ?
Redonner alors la complexité de l’algorithme de Dijkstra, et justifier.

En quoi l’algorithme de Dijkstra est-il un algorithme de parcours ?
Donner un cas où l’algorithme de Dijkstra coïncide avec un algorithme de parcours vu précédemment.

Exécuter l’algorithme de Dijkstra sur le graphe ci-dessous, depuis la source s.
g
5
1 5
5
1 e
1 1
1
a b 3 s 2 2 f
1
3 2 3 1
c 1 d
5.2 L’algorithme A?
L’algorithme de Dijkstra est un algorithme de calcul des plus courts chemins depuis une source du
graphe, vers chacun des sommets du graphe. Il n’est pas rare que l’on ait seulement besoin d’un plus
court chemin entre deux sommets bien identifiés d’un graphe : non seulement nous disposons d’un
sommet source mais aussi d’un sommet objectif. On présente donc dans cette section une variante
de l’algorithme de Dijkstra : l’algorithme A? , qui met à profit cette information supplémentaire
d’objectif pour essayer d’améliorer le temps de calcul de l’algorithme de Dijkstra.
Si l’on connaît le sommet objectif o, et que l’on cherche à calculer seulement la distance d(s, o), peut-on arrêter
l’algorithme de Dijkstra dès que µ[o] prend une valeur finie ? Dès que o est sorti de todo ? Dans chaque cas, si
la réponse est oui justifier, et sinon donner un contre exemple.
L’algorithme de Dijkstra visite les sommets du graphe à la manière d’un parcours en largeur depuis
la source : les sommets sont parcourus par distances croissantes depuis la source. Toutefois dans
le cas où l’on connaît l’objectif, on aimerait aussi que l’algorithme cherche “dans la direction” de
l’objectif.
On fournit ci-dessous des exemples sur un graphe non orienté représentant les déplacements sur
les cases d’une grille : d’une case (un sommet du graphe) on peut se déplacer (les arcs du graphe)
dans une des 8 cases adjacentes ♣ , à moins qu’elles ne soient des murs. Les arcs sont pondérés de la
manière suivante : on se déplace√ horizontalement et verticalement pour un coût de 1, on se déplace
en diagonale pour un coût de 2.
On présente ci-dessous (Figure 1) les sommets parcourus par l’algorithme de Dijkstra lors de la
recherche d’un chemin depuis la source (en bas à gauche) et vers l’objectif . Les cases repré-
sentent des murs et ne sont donc pas accessibles. Les cases sont les sommets qui ont été visités
tandis que les cases sont les sommets se trouvant dans la file de priorité. Finalement les traits
représentent les plus courts chemins, soit l’arborescence encodée par le tableau de prédécesseurs
π. Cet exemple met en avant le fait que l’algorithme de Dijkstra parcourt les sommets ”en largeur”
depuis la source.
♣. Les huit cases sont : haut, bas, gauche, droite, coin haut gauche, coin haut droite, coin bas gauche, coin bas droite.

Figure 1 – Exécution de l’algorithme de Dijkstra Figure 2 – Exécution de l’algorithme A?
L’algorithme A évite l’écueil de l’algorithme de Dijkstra mis en avant dans l’exemple précédent
?
grâce à une fonction heuristique qui donne, pour chaque sommet du graphe, une estimation de la
distance restant à parcourir pour atteindre l’objectif. Dans ce cadre, on appelle heuristique une
fonction associant un score positif à chaque sommet du graphe, h : S → R+ .
Définition 5.7
On dit d’une heuristique qu’elle est admissible dès lors qu’elle donne une minoration de la dis-
tance à l’objectif dans le graphe. Autrement dit, h est une heuristique admissible dès lors que
pour tout sommet u ∈ S tel qu’il existe un chemin de u au sommet objectif o de longueur l, on a
h(u) 6 l.
Une telle heuristique est alors utilisée pour choisir le sommet à traiter dans l’ensemble todo comme
étant, non pas un de ceux qui minimisent y 7→ µ[y], mais un de ceux qui minimisent y 7→ µ[y]+h(y).
Autrement dit, au lieu de choisir d’explorer un sommet dont la distance connue à la source est
minimale ♣ , on choisit d’explorer un sommet par lequel pourrait passer un chemin de longueur
minimale reliant s et o si on en croit l’heuristique. On présente ci-dessus (Figure 2) les sommets
parcourus par l’algorithme de A? lors de la recherche d’un chemin dans les mêmes conditions que
précédemment, en utilisant la distance à vol d’oiseau comme heuristique.
Expliquer pourquoi la distance à vol d’oiseau donne une heuristique admissible.
On présente ci-dessous l’algorithme A? en mettant en jaune les lignes qui changent par rapport à
♣. ce qui assure en fait, on le rappelle, que la distance exacte à la source est minimale,

l’algorithme de Dijkstra.
Algorithme 5 : A?
Entrée : Un graphe pondéré G = (S, A, c) où c : A → R+ , une source s ∈ S, un objectif
o ∈ S, une heuristique h : S → R+
Sortie : La distance de s à o
1 Initialiser µ[u] à +∞ pour u ∈ S ;
2 Initialiser η[u] à +∞ pour u ∈ S ;
3 Initialiser π[u] à ? ? pour u ∈ S ;
4 µ[s] ← 0 ; (* La source est à distance 0 d'elle-même *)
5 η[s] ← µ[s] + h(s) ; (* Estimation de la distance source objectif *)
6 π[s] ← s ; (* La source est la racine de l'arborescence *)
7 todo ← {s} ; (* La racine est le premier sommet à traiter *)
8 Procedure Relâcher((u, v)) :
Entrée : u et v deux sommets voisins dans G ;
9 si µ[u] + c((u, v)) < µ[v] alors
10 µ[v] ← µ[u] + c((u, v)) ;
11 η[v] ← µ[v] + h(v) ;
12 π[v] ← u ;
15 Extraire de todo un sommet u minimisant η[u] ;
16 si u = o alors
17 retourner µ[o] ; (* Objectif atteint*)
18 pour tout v ∈ voisins(u) faire
19 Relâcher(u, v)
20 retourner ∞ ; (* Objectif inaccessible*)

Que dire de l’exécution de l’algorithme A? avec l’heuristique nulle (i.e. h : s ∈ S 7→ 0) ?
Théorème 5.10
Si l’heuristique utilisée est admissible, l’algorithme A? est correct.
Démonstration :
1) Remarquons tout d’abord que pour tout sommet x ∈ S, la valeur de µ[x] ne fait que décroître à me-
sure que l’algorithme A? s’exécute. En effet les valeurs de µ ne sont modifiées qu’à la ligne 10 de la
fonction Relâcher, et d’après le test qui précède cette instruction, la valeur est modifiée pour une valeur
strictement plus petite.
2) La boucle tant que de l’algorithme A? vérifie les invariants suivants ♣ .
I1 :∀x ∈ S, µ[x] < +∞ ⇒ ∃γ chemin de G de longueur µ[x] reliant s et x

I2 :∀x ∈ todo, µ[x] < +∞
• Initialement (i.e. l.6), le seul sommet dans todo est s, et on a alors µ[s] = 0 < +∞ d’où l’invariant
I2 . De plus le chemin (γ0 = s) étant un chemin de longueur nulle reliant s et s, l’invariant I1 est
bien vérifié.
♣. les mêmes que l’algorithme de Dijkstra

• Supposons que les deux invariants sont vérifiés au début d’un tour de la boucle tant que. Soit u ∈ S
le sommet traité lors de ce tour de boucle. D’après l’invariant I2 , on a donc µ[u] < +∞. Les seuls
sommets ajoutés à todo lors de ce tour de boucle sont les voisins v de u, dont la valeur de µ est
d’abord ajustée à µ[u] + c((u, v)), et donc en particulier finie. Ainsi l’invariant I2 reste vrai.
De plus, si l’on considère x ∈ S un sommet dont la valeur de µ passe de +∞ à une valeur finie au
cours de ce tour de boucle, on sait que x est nécessairement voisin de u. Or l’invariant I1 assure
(puisque µ[u] < +∞) qu’il existe un chemin de s à u. On en déduit l’existence d’un chemin, de
longueur convenable, de s à x. Ainsi l’invariant I1 se propage.
À ce point de la preuve, on peut déjà conclure quant à la correction de l’algorithme dans le cas où d(s, o) =
∞. Dans ce cas, il n’existe aucun chemin reliant s et o donc µ[o] ne peut jamais prendre une valeur finie,
en particulier o ne sera jamais ajouté à todo et on ne sortira pas de la fonction à la ligne 17. Ainsi, pourvu
que l’algorithme termine, la valeur renvoyée dans ce cas là est +∞ (Cf. l. 20).
Dans les autres cas, ces invariants assurent que la valeur µ[o] renvoyée par la ligne 17 est un majorant de la
distance d(s, o). On s’attache dans la suite à montrer qu’au moment où o est traité cette valeur est exacte.
Dans la suite de la preuve, on suppose donc que d(s, o) < +∞, ainsi il existe un chemin de G reliant s et o
de longueur d(s, o).
3) Soit γ un chemin reliant s = γ0 à o = γq de longueur minimale. On montre ici qu’à n’importe quelle
/ todo, alors
étape de l’algorithme après la ligne 6, et pour tout k ∈ J0, qJ, si µ[γk ] = d(s, γk ) et γk ∈
µ[γk+1 ] = d(s, γk+1 ).
Considérons un instant t de l’exécution de l’algorithme et k ∈ J0, qJ tel que µ[γk ] = d(s, γk ) et

/ todo . Puisque µ[γk ] < +∞, le sommet a été ajouté à todo au moins au moment où il a reçu
γk ∈
/ todo à l’instant t, on sait que γk a été
pour la première fois une valeur de µ finie. Du fait que γk ∈
extrait de todo.
Considérons l’instant t0 < t où γk a été extrait de todo pour la dernière fois. La valeur de µ[γk ] n’a
pas changé depuis (sans quoi γk aurait été remis dans todo). Lors du traitement de γk qui a précédé
son extraction à l’instant t0 , on a mis à jour la valeur de µ pour γk+1 voisin de γk . Ainsi à l’instant t0 :
µ[γk+1 ] 6 µ[γk ] + c((γk , γk+1 )).
Entre t0 et t la valeur de µ[γk+1 ] n’a pu que décroître d’après le point 1) et celle de µ[γk ] n’a pas
changé, ainsi à l’instant t on a :
µ[γk+1 ] 6 µ[γk ] + c((γk , γk+1 )).
Or par hypothèse on a aussi µ[γk ] = d(s, γk ), donc :
µ[γk+1 ] 6 d(s, γk ) + c((γk , γk+1 )).
De plus par minimalité de γ on a d(s, γk ) + c((γk , γk+1 )) = d(s, γk+1 ), d’où :
µ[γk+1 ] 6 d(s, γk+1 ).
Enfin par l’invariant vu au point 2) on a µ[γk+1 ] > d(s, γk+1 ), d’où l’égalité souhaitée :
µ[γk+1 ] = d(s, γk+1 ).
4) On montre ici que dès la ligne 6 et tant que o n’est pas extrait de todo, il existe un sommet x ∈ S
vérifiant les trois conditions suivantes :
a) x est dans todo ;
b) µ[x] = d(s, x) ;
c) il existe un chemin minimal de s à o passant par x.

• Initialement todo contient s qui est bien sur un chemin minimal reliant s et o (puisqu’un tel chemin
existe), et qui vérifie µ[s] = 0 d’après la ligne 4, soit µ[s] = d(s, s).
• Supposons qu’au début d’un tour de boucle il existe un tel sommet x dans todo et que l’on traite
un sommet u 6= o.
- Si u 6= x, alors x est encore dans todo à la fin du tour. L’existence d’un chemin minimal passant
par x n’est pas remise en cause. Enfin la valeur de µ[x] a pu être modifiée, mais seulement à la
baisse d’après le point 1) or on a aussi µ[x] > d(s, x) d’après le point 2). Ainsi x justifie encore
que la propriété est vérifiée à la fin du tour de boucle.
- Si u = x, alors x 6= o. De plus x est par hypothèse sur un chemin élémentaire γ reliant s = γ0 à
o = γq de longueur minimale. Notons i ∈ J0, qJ l’indice tel que γi = x. À la fin du tour de boucle
on a γi ∈ / todo et µ[γi ] = d(s, γi ), donc le point 3) assure que µ[γi+1 ] = d(s, γi+1 ). Ou bien
γi+1 ∈ todo, et alors ce sommet vérifie a) et b) et c), ou bien γi+1 ∈ / todo et on peut à nouveau
utiliser le point 3). En itérant ainsi, on aboutit nécessairement sur un indice k ∈ Ji + 1, qK tel que
γk ∈ todo et µ[γk ] = d(s, γk ), sans quoi on aurait o = γq ∈ / todo et aussi µ[γq ] = d(s, γq ), donc
µ[γq ] < ∞ ce qui contredit le fait qu’on n’ait pas encore traité o. Ce sommet γk vérifie donc a)
et b) et c), ainsi la propriété est vérifiée en fin de tour de boucle.
On a traité plus haut le cas où d(s, o) = ∞, on traite donc ici le cas où o est accessible depuis s. Ainsi
l’invariant du point 4) assure que la condition de sortie de la boucle while ne peut être satisfaite tant que
o n’a pas été traité, autrement dit on sort nécessairement de l’algorithme par la ligne 17.
Notons x un sommet vérifiant a), b), c) au moment où o est sélectionné à la ligne 15 précédant cette sortie.
Puisque x ∈ todo (propriété a), le choix de o comme sommet à traiter assure η[o] 6 η[x]. Or :
η[x] = µ[x] + h(x) par invariant immédiat sur η

= d(s, x) + h(x) par b
6 d(s, x) + d(x, o) car h est minorante
= d(s, o) par c
et h(o) = 0 puisque h est minorante. On en déduit que µ[o] + 0 6 d(s, o), or µ[o] > d(s, o) par invariant du
point 2) donc µ[o] = d(s, o) et la valeur renvoyée est bien celle attendue.

Exécuter l’algorithme A? sur le graphe ci-contre avec l’heuristique h définie a 100
10
comme suit.
s 10 o
- h = s 7→ 0, a 7→ 0, b 7→ 0, o 7→ 0 (heuristique nulle)
- h = s 7→ 10, a 7→ 1, b 7→ 20, o 7→ 0 (heuristique admissible non monotone) 1
b 20
- h = s 7→ 10, a 7→ 10, b 7→ 9, o 7→ 0 (heuristique admissible et monotone)
Remarque 5.12
On remarque que dans l’algorithme A? , contrairement à ce qui se passe dans l’algorithme de Dijkstra, un
sommet x peut être extrait de todo avec une valeur µ[x] > d(s, x) (et risque dans ce cas d’y être à nouveau
ajouté avec une valeur de µ[x] réduite), et qu’un arc peut être relâché plusieurs fois ♣ .
Remarque 5.13
Pour démontrer la correction de l’algorithme de Dijkstra, on peut utiliser de même la remarque du point 1)
et les invariants I1 et I2 , mais les points suivants se simplifient, car on peut directement montrer que
lorsqu’un sommet x est extrait de todo la valeurs µ[x] vaut d(s, x).
♣. Cf. le sommet a et l’arc (a, o) dans l’exercice de cours 5.11 pour l’heuristique non monotone.

Remarque 5.14
La terminaison de l’algorithme A? découle du fait qu’un sommet u ne peut être extrait de todo qu’un nombre
fini de fois, assurant ainsi un nombre de tours de boucle ligne 14 fini. En effet l’invariant I1 démontré ci-
avant peut être renforcé comme suit.
I10 : ∀x ∈ S, µ[x] < +∞ ⇒ ∃γ chemin élémentaire de G de longueur µ[x] reliant s et x
Ainsi, pour un sommet x fixé, la suite des valeurs prises par µ[x] à chaque fois que x est traité est une suite
strictement décroissante à valeurs dans un ensemble fini — à savoir l’ensemble des longueurs des chemins
élémentaires dans G — et donc finie.
Définition 5.15
On dit qu’une heuristique h est monotone dès lors que ∀(u, v) ∈ A, h(u) 6 c(u, v) + h(v)

La distance à vol d’oisau dans le graphe sur une grille donné en exemple plus haut est-elle une heuristique
monotone ?
Proposition 5.17
Si l’heuristique utilisée est admissible et monotone, chaque sommet u n’est traité qu’une seule
fois par l’algorithme A? , et dès qu’il est traité, µ[u] vaut d(s, u).
Démonstration : On reprend les invariants démontrés dans la preuve de la proposition 5.10. Ils assurent en
particulier qu’un sommet x hors de todo tel que µ[x] = d(s, x) ne peut pas être y ajouté à nouveau, car on
ajoute un sommet x dans todo que lorsqu’on donne à µ[x] une valeur strictement plus petite, or I1 assure
que µ[x] est déjà au minimum. Ainsi il suffit de montrer que lorsqu’un sommet u est traité la valeur µ[u]
donne d(s, u). On montre ce résultat par récurrence finie sur les étapes de traitement de sommet.
Lors de la première étape c’est le sommet s qui est traité, il a bien la valeur µ[s] = 0 = d(s, s).
Plaçons nous à une étape suivante de l’algorithme, et supposons que tous les sommets traités auparavant
vérifient la propriété. Notons v (v 6= s) le sommet traité à l’étape courante, et supposons par l’absurde que
µ[v] 6= d(s, v). D’après l’invariant I2 , µ[v] < ∞ puisque v ∈ todo, et donc µ[v] > d(s, v) par l’invariant
I1 . Ainsi on suppose en fait que µ[v] > d(s, v). Il existe donc un chemin γ de γ0 = s à γq = v de longueur
d(s, v) < µ[v]. On sait que γ0 = s a déjà été traité, et γq = v pas encore, on peut donc considérer k ∈ J0, qJ
l’indice du dernier sommet traité le long de γ. Ainsi par hypothèse de récurrence, µ[γk ] = d(s, k). Lors du
traitement de γk , son successeur γk+1 a été ajouté à todo et a reçu la valeur µ[γk+1 ] = µ[γk ] + c(γk , γk+1 ) =
d(s, k) + c(γk , γk+1 ) = ♣ d(s, γk+1 ). Ainsi d(s, v) la longueur du chemin γ se réécrit comme µ[γk+1 ] + l où
l = c(γk+1 , γk+2 ) + c(γk , γk+1 ) · · · + c(γq−1 , γq ) désigne la longueur du chemin γk+1 . . . γq .
• Si k = q − 1, lors du traitement du sommet γk , le sommet v a reçu la valeur µ[v] = µ[γk ] + c(γk , γk+1 )
soit d(s, v). Absurde.
• Si k < q − 1, on utilise la monotonie de h le long du chemin γk+1 . . . γq .
h(v) = h(γq ) > h(γq−1 ) − c(γq−1 , γq )

> h(γq−2 ) − c(γq−2 , γq−1 ) + c(γq−1 , γq )
...

> h(γk+1 ) − c(γk+1 , γk+2 ) + · · · + c(γq−1 , γq )
| {z }
=l
♣. On utilise implicitement le fait que le chemin γ0 . . . γk+1 est minimal, en tant que sous-chemin d’un chemin
minimal, et donc de longueur est d(s, γk+1 ).

Ainsi :
µ[v] + h(v) > µ[v] + h(γk+1 ) − l résultat de la monotonie ci-dessus

> d(s, v) − l + h(γk+1 ) par notre hypothèse absurde
> (µ[γk+1 ] + l) − l + h(γk+1 ) en décomposant la longueur de γ
> µ[γk+1 ] + h(γk+1 )
or il est absurde que µ[v] + h(v) > µ[γk+1 ] + h(γk+1 ) sans quoi on aurait traité γk+1 (présent dans todo
et de meilleur score) et pas v à cette étape.
Dans les deux cas on arrive à une contradiction, ainsi on a bien µ[v] = d(s, v).

Chap02 Graphes Parcours - Student

Transféré par

Droits d'auteur :

Formats disponibles

Chap02 Graphes Parcours - Student

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chap02 Graphes Parcours - Student

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 2 : Parcours de graphes

Exercice de cours 1.3

Exercice de cours 1.5

Exercice de cours 1.6

Informatique - MPI Lycée Fermat - 2024/2025 1/28

Exercice de cours 1.10

Exercice de cours 1.12

Exercice de cours 1.13

Exercice de cours 1.15

Exercice de cours 1.16

Informatique - MPI Lycée Fermat - 2024/2025 2/28

Exercice de cours 1.20

Exercice de cours 1.21

Exercice de cours 1.23

Exercice de cours 1.24

1.2 Accessibilité dans le cas non orienté et connexité

Informatique - MPI Lycée Fermat - 2024/2025 3/28

Exercice de cours 1.30

Exercice de cours 1.32

Exercice de cours 1.34

Exercice de cours 1.36

1.3 Accessibilité dans le cas orienté et forte connexité

Informatique - MPI Lycée Fermat - 2024/2025 4/28

Exercice de cours 1.40

Exercice de cours 1.43

Informatique - MPI Lycée Fermat - 2024/2025 5/28

Démonstration : Soit W une composante fortement connexe de G. Soient u et v deux sommets de W .

♣. Cet argument est concluant parce que S 6= ∅

Informatique - MPI Lycée Fermat - 2024/2025 6/28

Avant réduction Après réduction

Exercice de cours 1.51

Exercice de cours 1.53

Exercice de cours 1.56

Informatique - MPI Lycée Fermat - 2024/2025 7/28

Exercice de cours 2.2

∀i ∈ J1, nK, Li ∈ B({Lj | j ∈ J1, iJ }) ou B({Lj | j ∈ J1, iJ }) = ∅

Exercice de cours 2.6

Informatique - MPI Lycée Fermat - 2024/2025 8/28

2.2 Partition associée à un parcours

Exercice de cours 2.10

Hk : il existe un chemin de Lr vers Lk dont tous les sommets sont dans Cr

• Si k = r alors le chemin réduit au sommet Lr convient, ainsi Hr est vraie.

Informatique - MPI Lycée Fermat - 2024/2025 9/28

Démonstration : C’est un corollaire des deux lemmes précédents.

Démonstration : C’est un corollaire du lemme 2.11.

{d} et finalement {e}.

2.3 Parcours particuliers

Exercice de cours 2.17

♣. Succ(Li ) est l’ensemble des successeurs du sommet Li

Informatique - MPI Lycée Fermat - 2024/2025 10/28

Parcours largeur Parcours profondeur

Parcours ni largeur ni profondeur Parcours largeur et profondeur

Exercice de cours 2.20

Exercice de cours 2.21

2.4 Forêt associée à un parcours

Informatique - MPI Lycée Fermat - 2024/2025 11/28

A0 = {(Lπ(k) , Lk ) | Lk n’est pas point de régénération }

2.5 Implémentation de parcours

Exercice de cours 2.26