Solu tions des exer cices du cha pitre 3
455
© Dunod – Toute reproduction non autorisée est un délit.
3) (E, G) et (F, A) sont des arcs-arrière : ils ferment respectivement les circuits
(E, G, C, D, E) et (F, A, B, F).
3.7 Voici le par cours en pro fon deur du graphe de l’appli ca tion, depuis A, puis dans une
seconde phase depuis E, donné par les 2 arbo res cences (ou « forêt ») et aussi par les dif fé rents
états de la pile asso ciée à ce par cours :
graphe g
C
D
G
E
F
B
A
H
π(G) = 6
π(B) = 4
π(A) = 5
π(H) = 1
π(F) = 7
8 = π(E)
π(D) = 3
π(C) = 2
2
1
A
B
C
H
D
E
F
G
A
B
A
C
H
C
C
B
B
A
B
B
A
A
fin
phase 1
fin
phase 2
début
phase 1
début
phase 2
pile vide
D
A
A
B
A
E
F
E
G
F
E
F
E
E
B
A
NB Ici (G, E ) et (C, A) sont des arcs-arrières : ils ferment les circuits (G, E, F, G ) et
(C, A, B, C ).
(A, H ) est un arc-avant. (D, C), (E, B) et (G, D) sont des arcs-transverses.