Chapitre 3 • Éléments de la théorie des graphes
72
Les figures 3.13 à 3.17 illus trent un dérou le ment pos sible de l’algo rithme pour le
graphe repré senté dans la figure 3.12 ; remar quons que ce graphe n’est pas connexe
et comporte p 5 3 compo santes connexes. Dans ces figures, les som mets gri sés sont
les som mets ouverts et les som mets cer clés d’un trait épais et non gri sés sont les
som mets fer més. Tout arc (x, y) repré senté par une flèche épaisse indique le som met
x à par tir duquel s’effec tue l’ouver ture du som met y.
Figure 3.12
Nous détaillons main te nant la façon dont le par cours est effec tué, le lec teur pourra suivre ce par cours sur les figures 3.13 et 3.17.
Le pre mier som met ouvert est le som met A. Ensuite, le som met B adja cent à A est
ouvert ; à noter cepen dant, que les som mets E ou F auraient tout aussi pu être ouverts
à cette étape. Les som mets I, puis E, puis H sont ensuite suc ces si ve ment ouverts. Le
som met E est alors fermé (L ou F auraient pu être ouverts à cette étape), le graphe
cor res pon dant est alors le der nier de la figure 3.14. L est ensuite ouvert, puis I fermé.
À ce moment, la reprise de la visite du som met A, per met l’ouver ture du som met
F. Les som mets H, A, B, F, L (fig. 3.16 en haut) sont alors suc ces si ve ment fer més ;
remar quons encore que tout autre ordre de fer me ture de ces cinq der niers som mets
aurait été compa tible avec l’algo rithme. À ce moment, plus aucun som met n’est
ouvert : c’est la fin de la première passe mais tous les som mets ne sont pas fer més :
le som met non mar qué C est alors ouvert : c’est le début de la seconde passe. Le
par cours se pour suit par l’ouver ture du som met J. Puis suc ces si ve ment s’exé cutent
les ouver tures de K puis de D, la fer me ture de J sui vie de l’ouver ture de G, puis des
fer me tures suc ces sives des som mets C, K, G et D (fig. 3.16, en bas). À nou veau,
aucun som met n’est ouvert, mais tous les som mets ne sont pas fer més. Le par cours
se pour suit (troisième passe) par l’ouver ture du som met M, puis celles de N et O,
suc ces si ve ment. Les som mets N, M, O sont alors suc ces si ve ment fer més (fig. 3.17,
second graphe) ; ici encore, tout autre ordre de fer me ture de ces trois der niers som -
mets aurait pu conve nir. Tous les som mets sont fer més à cette étape de l’algo rithme ;
le par cours du graphe est alors ter miné.
72
Les figures 3.13 à 3.17 illus trent un dérou le ment pos sible de l’algo rithme pour le
graphe repré senté dans la figure 3.12 ; remar quons que ce graphe n’est pas connexe
et comporte p 5 3 compo santes connexes. Dans ces figures, les som mets gri sés sont
les som mets ouverts et les som mets cer clés d’un trait épais et non gri sés sont les
som mets fer més. Tout arc (x, y) repré senté par une flèche épaisse indique le som met
x à par tir duquel s’effec tue l’ouver ture du som met y.
Figure 3.12
Nous détaillons main te nant la façon dont le par cours est effec tué, le lec teur pourra suivre ce par cours sur les figures 3.13 et 3.17.
Le pre mier som met ouvert est le som met A. Ensuite, le som met B adja cent à A est
ouvert ; à noter cepen dant, que les som mets E ou F auraient tout aussi pu être ouverts
à cette étape. Les som mets I, puis E, puis H sont ensuite suc ces si ve ment ouverts. Le
som met E est alors fermé (L ou F auraient pu être ouverts à cette étape), le graphe
cor res pon dant est alors le der nier de la figure 3.14. L est ensuite ouvert, puis I fermé.
À ce moment, la reprise de la visite du som met A, per met l’ouver ture du som met
F. Les som mets H, A, B, F, L (fig. 3.16 en haut) sont alors suc ces si ve ment fer més ;
remar quons encore que tout autre ordre de fer me ture de ces cinq der niers som mets
aurait été compa tible avec l’algo rithme. À ce moment, plus aucun som met n’est
ouvert : c’est la fin de la première passe mais tous les som mets ne sont pas fer més :
le som met non mar qué C est alors ouvert : c’est le début de la seconde passe. Le
par cours se pour suit par l’ouver ture du som met J. Puis suc ces si ve ment s’exé cutent
les ouver tures de K puis de D, la fer me ture de J sui vie de l’ouver ture de G, puis des
fer me tures suc ces sives des som mets C, K, G et D (fig. 3.16, en bas). À nou veau,
aucun som met n’est ouvert, mais tous les som mets ne sont pas fer més. Le par cours
se pour suit (troisième passe) par l’ouver ture du som met M, puis celles de N et O,
suc ces si ve ment. Les som mets N, M, O sont alors suc ces si ve ment fer més (fig. 3.17,
second graphe) ; ici encore, tout autre ordre de fer me ture de ces trois der niers som -
mets aurait pu conve nir. Tous les som mets sont fer més à cette étape de l’algo rithme ;
le par cours du graphe est alors ter miné.