Chapitre 3 • Éléments de la théorie des graphes
90
Nous allons don ner quelques pro prié tés carac té ris tiques des par cours en pro
fon deur (nommés aussi “Parcours en Profondeur D’Abord”, notés “P.P.D.A”.).
• Pre mière pro priété : lors qu’un som met est ouvert il est placé dans la pile et lors qu’il
est fermé il est sup primé de la pile. L’ordre de prévisite est donc celui dans lequel
les som mets sont insé rés dans la pile et l’ordre de postvisite, celui dans lequel, ils en
sont extraits. Il s’en suit qu’à chaque étape, les som mets ouverts sont les som mets
pré sents dans la pile.
• Deuxième pro priété : à chaque étape où la pile est vide, le par cours d’une compo -
sante connexe du graphe est ter miné. Ainsi juste avant qu’un som met cor res pon dant
à la racine d’une arbo res cence soit ouvert, la pile est vide, et lors qu’il vient d’être
fermé, la pile est vide à nou veau. La racine d’une arbo res cence est donc tou jours au
fond de la pile.
• Troisième propriété (uti li sée pour la concep tion de nom breux algo rithmes) : à chaque étape, les som mets pré sents dans la pile, consi dé rés dans le même ordre que dans
celle- ci, forment un che min de l’arbo res cence rela tive au par cours. Cette pro priété
est trivialement vraie lorsque, seule, la racine est dans la pile. Supposons- la satis faite
lorsque h – 1 som mets sont dans la pile. Soit alors x le som met au som met de la pile.
Lors qu’un som met y est inséré (h som mets sont alors dans la pile) un arc (x, y) est
ajouté à l’arbo res cence et, puisque par hypo thèse, il existe un che min de la racine
au som met x, dans l’arbo res cence il existe aussi un che min de la racine au som met y
ayant (x, y) comme der nier arc.
À l’issue du par cours en profondeur d’un graphe non orienté, ses arêtes sont de
deux types : une arête de liai son est une arête [x, y] telle que (x, y) est un arc de(s)
arborescence(s) rela tive(s) au par cours ; les autres arêtes du graphe sont appe lées
arêtes de retour. Ainsi pour le par cours effec tué dans notre exemple, [C, B] est une
arête de liai son et [C, A] est une arête de retour.
Nous mon trons main te nant une pro priété carac té ris tique des arêtes de retour.
Dans un par cours en pro fon deur, pour toute arête de retour [x, y] avec y ayant un
rang supé rieur à celui de x dans l’ordre de prévisite, le som met x est sur le che min
unique allant, dans l’arbo res cence, de la racine à y. La preuve est la sui vante : x a été
ouvert avant y et donc inséré dans la pile avant y ; si x n’est pas sur le che min de la
racine à y, d’après la pro priété pré cè dente, au moment où y est empilé, x n’est plus
dans la pile ; x est donc fermé, mais cela est impos sible car l’arête [x, y] appar te nant
au graphe, x ne peut pas être fermé avant que y soit ouvert.
Remar quons que toute arête de retour [x, y] ferme, avec le che min de x à y de
l’arbo res cence, un cycle. De même pour le parcours d’un graphe orienté : tout arc
de retour (y, x) ferme, avec le chemin de x à y de l’arborescence, un circuit. ainsi on
peut déterminer, par un simple parcours en profondeur, si un graphe comporte
des circuits ou non.
De nom breux algo rithmes, comme celui pré senté ci-après, uti lisent ces dif fé rentes
pro prié tés.
90
Nous allons don ner quelques pro prié tés carac té ris tiques des par cours en pro
fon deur (nommés aussi “Parcours en Profondeur D’Abord”, notés “P.P.D.A”.).
• Pre mière pro priété : lors qu’un som met est ouvert il est placé dans la pile et lors qu’il
est fermé il est sup primé de la pile. L’ordre de prévisite est donc celui dans lequel
les som mets sont insé rés dans la pile et l’ordre de postvisite, celui dans lequel, ils en
sont extraits. Il s’en suit qu’à chaque étape, les som mets ouverts sont les som mets
pré sents dans la pile.
• Deuxième pro priété : à chaque étape où la pile est vide, le par cours d’une compo -
sante connexe du graphe est ter miné. Ainsi juste avant qu’un som met cor res pon dant
à la racine d’une arbo res cence soit ouvert, la pile est vide, et lors qu’il vient d’être
fermé, la pile est vide à nou veau. La racine d’une arbo res cence est donc tou jours au
fond de la pile.
• Troisième propriété (uti li sée pour la concep tion de nom breux algo rithmes) : à chaque étape, les som mets pré sents dans la pile, consi dé rés dans le même ordre que dans
celle- ci, forment un che min de l’arbo res cence rela tive au par cours. Cette pro priété
est trivialement vraie lorsque, seule, la racine est dans la pile. Supposons- la satis faite
lorsque h – 1 som mets sont dans la pile. Soit alors x le som met au som met de la pile.
Lors qu’un som met y est inséré (h som mets sont alors dans la pile) un arc (x, y) est
ajouté à l’arbo res cence et, puisque par hypo thèse, il existe un che min de la racine
au som met x, dans l’arbo res cence il existe aussi un che min de la racine au som met y
ayant (x, y) comme der nier arc.
À l’issue du par cours en profondeur d’un graphe non orienté, ses arêtes sont de
deux types : une arête de liai son est une arête [x, y] telle que (x, y) est un arc de(s)
arborescence(s) rela tive(s) au par cours ; les autres arêtes du graphe sont appe lées
arêtes de retour. Ainsi pour le par cours effec tué dans notre exemple, [C, B] est une
arête de liai son et [C, A] est une arête de retour.
Nous mon trons main te nant une pro priété carac té ris tique des arêtes de retour.
Dans un par cours en pro fon deur, pour toute arête de retour [x, y] avec y ayant un
rang supé rieur à celui de x dans l’ordre de prévisite, le som met x est sur le che min
unique allant, dans l’arbo res cence, de la racine à y. La preuve est la sui vante : x a été
ouvert avant y et donc inséré dans la pile avant y ; si x n’est pas sur le che min de la
racine à y, d’après la pro priété pré cè dente, au moment où y est empilé, x n’est plus
dans la pile ; x est donc fermé, mais cela est impos sible car l’arête [x, y] appar te nant
au graphe, x ne peut pas être fermé avant que y soit ouvert.
Remar quons que toute arête de retour [x, y] ferme, avec le che min de x à y de
l’arbo res cence, un cycle. De même pour le parcours d’un graphe orienté : tout arc
de retour (y, x) ferme, avec le chemin de x à y de l’arborescence, un circuit. ainsi on
peut déterminer, par un simple parcours en profondeur, si un graphe comporte
des circuits ou non.
De nom breux algo rithmes, comme celui pré senté ci-après, uti lisent ces dif fé rentes
pro prié tés.