Solutions
456
Voici main te nant g
t
, le graphe- miroir de g et la forêt constituée de 3 arbo res cences de son
par cours en pro fon deur ; le sommet initial est celui de plus fort rang dans le premier parcours
en profondeur : cʼest E puisque p (E) 5 8.
B
A
H
C
D
G
F
E
1
2
3
E
G
F
1
A
C
B
D
2
H
3
Dans la première passe de ce second parcours en profondeur, on visite seulement les 3
sommets {E, F, G}. Ensuite le second sommet non encore visité est A puisque p (A) 5 5 :
A est le sommet initial de la seconde passe ; on visite alors {A, B, C, D}. Enfin il reste un seul
sommet non encore visité : H qui est le sommet initial de la troisième passe... et final puisque
il était seul.
Le graphe ini tial com porte donc 3 com po santes for te ment connexes :
K 1 = {E, F, G} , K 2 = {A, B, C, D} , K 3 = {H}
Le som met H est le seul dans sa com po sante for te ment connexe car H est une sor tie du
graphe ini tial. À titre de véri fi ca tion (visuelle) dans le graphe initial : les trois som mets E, F
et G appar te nant à un même cir cuit : (E, F, G, E) appar tiennent à la même com po sante for te -
ment connexe ; il en va de même pour A, B, C et D avec le cir cuit (A, B, D, C, A).