Chapitre 3 • Éléments de la théorie des graphes
92
9.
sinon fer mer le som met x et sup pri mer x de la pile ;
10.
pour tout som met z suc ces seur de x tel que 1 z, x2 x A faire ;
11.
hau teur(x) d min (hau teur(x), hau teur(z)) ;
12. si s a, au moins, deux suc ces seurs dans A alors s est un som met d’arti cu lation ;
13. pour x 2 s, s’il existe y suc ces seur de x dans A tel que hau teur(y) > prévisite(x)
alors x est un som met d’arti cu lation
Les figures 3.28 et 3.29 illus trent l’appli ca tion de l’algo rithme à par tir du som ­
met ini tial A. Les valeurs prévisite (x) et hau teur (x) sont ins crites res pec ti ve ment
à gauche et à droite dans le rec tangle situé à côté de chaque som met x. Le choix
du som met ini tial ainsi que cer taines phases de l’algo rithme étant arbi traires, nous
allons effec tuer une autre exé cu tion de l’algo rithme sur le même graphe. La figure
3.30 illustre le résul tat d’une autre appli ca tion de l’algo rithme à par tir, cette fois- ci,
du som met ini tial B.
on ouvre A.
on ouvre C.
on ferme B.
on ouvre E.
ici (z, x) = (C, A)
on ferme C.
on ouvre B.
Figure 3.28