Chapitre 3 • Éléments de la théorie des graphes
94
Nous allons main te nant mon trer la vali dité de cet algo rithme
1
. Nous mon trons pre -
mière ment que le som met s, som met à par tir duquel commence le par cours, est un som -
met d’arti cu lation si et seule ment si s a au moins deux suc ces seurs dans l’arbo res cence
rela tive au par cours. Soient u et v deux suc ces seurs de s dans l’arbo res cence. Mon trons
que toute chaîne reliant u et v passe par le som met racine s. S’il exis tait une chaîne
reliant u et v ne pas sant pas par s, il exis te rait une arête de retour {x, y} avec x som met
de la sous- arborescence de racine u et y n’appar te nant pas à cette sous- arborescence.
Cela est impos sible, car comme nous l’avons mon tré pré cé dem ment, dans un par cours
en pro fon deur, les arêtes de retour ont leurs deux extré mi tés sur un même che min de
l’arbo res cence rela tive au par cours. Nous en concluons que toute chaîne reliant les
som mets u et v passe par s : s est donc un som met d’arti cu lation.
Réci pro que ment, sup po sons que la racine s de l’arbo res cence soit un som met
d’arti cu lation. Il existe alors deux som mets u et v tels que toute chaîne les reliant
passe par s. Si la racine s de l’arbo res cence a un suc ces seur unique x, alors il existe
dans l’arbo res cence un che min de x à u et un che min de x à v. Cela implique l’exis -
tence, dans le graphe par couru, d’une chaîne reliant u et v pas sant par x et ne pas sant
pas par s. La pro priété est donc démon trée.
Dans l’algo rithme pro posé, l’ins truc tion 12 teste si la racine s a, au moins, deux
suc ces seurs.
Consi dé rons main te nant un som met x 2 s. Nous allons mon trer que x est un
som met d’arti cu lation, si et seule ment si, il n’existe pas d’arête de retour {u, t} telle
que le som met u soit un des cen dant de x (suc ces seur non néces sai re ment immé diat)
et le som met t soit un pré dé ces seur de x dans l’arbo res cence rela tive au par cours.
S’il existe une arête de retour {u, t} satis faisant à la défi ni tion pré cé dente, alors il
existe une chaîne reliant u et t pas sant par le som met x, cette chaîne cor res pon dant
au che min allant de t à u dans l’arbo res cence ; il existe aussi une chaîne reliant u et t
ne pas sant pas par le som met x, cette chaîne est consti tuée de la seule arête {u, t}. La
réunion de ces deux chaînes forme un cycle pas sant par x, le som met x n’est donc pas
un som met d’arti cu lation. Réci pro que ment, si pour tout des cen dant u et pré dé ces -
seur t de x dans l’arbo res cence, il n’existe pas d’arête de retour {u, t}, les arêtes de
retour dans un par cours en pro fon deur ayant leurs deux extré mi tés sur un même che -
min de l’arbo res cence, toute chaîne reliant t et u passe néces sai re ment par le som met
x. x est donc un som met d’arti cu lation. La pro priété est alors démon trée.
1. le lecteur pourra sauter cette preuve, en première lecture.
Figure 3.30
94
Nous allons main te nant mon trer la vali dité de cet algo rithme
1
. Nous mon trons pre -
mière ment que le som met s, som met à par tir duquel commence le par cours, est un som -
met d’arti cu lation si et seule ment si s a au moins deux suc ces seurs dans l’arbo res cence
rela tive au par cours. Soient u et v deux suc ces seurs de s dans l’arbo res cence. Mon trons
que toute chaîne reliant u et v passe par le som met racine s. S’il exis tait une chaîne
reliant u et v ne pas sant pas par s, il exis te rait une arête de retour {x, y} avec x som met
de la sous- arborescence de racine u et y n’appar te nant pas à cette sous- arborescence.
Cela est impos sible, car comme nous l’avons mon tré pré cé dem ment, dans un par cours
en pro fon deur, les arêtes de retour ont leurs deux extré mi tés sur un même che min de
l’arbo res cence rela tive au par cours. Nous en concluons que toute chaîne reliant les
som mets u et v passe par s : s est donc un som met d’arti cu lation.
Réci pro que ment, sup po sons que la racine s de l’arbo res cence soit un som met
d’arti cu lation. Il existe alors deux som mets u et v tels que toute chaîne les reliant
passe par s. Si la racine s de l’arbo res cence a un suc ces seur unique x, alors il existe
dans l’arbo res cence un che min de x à u et un che min de x à v. Cela implique l’exis -
tence, dans le graphe par couru, d’une chaîne reliant u et v pas sant par x et ne pas sant
pas par s. La pro priété est donc démon trée.
Dans l’algo rithme pro posé, l’ins truc tion 12 teste si la racine s a, au moins, deux
suc ces seurs.
Consi dé rons main te nant un som met x 2 s. Nous allons mon trer que x est un
som met d’arti cu lation, si et seule ment si, il n’existe pas d’arête de retour {u, t} telle
que le som met u soit un des cen dant de x (suc ces seur non néces sai re ment immé diat)
et le som met t soit un pré dé ces seur de x dans l’arbo res cence rela tive au par cours.
S’il existe une arête de retour {u, t} satis faisant à la défi ni tion pré cé dente, alors il
existe une chaîne reliant u et t pas sant par le som met x, cette chaîne cor res pon dant
au che min allant de t à u dans l’arbo res cence ; il existe aussi une chaîne reliant u et t
ne pas sant pas par le som met x, cette chaîne est consti tuée de la seule arête {u, t}. La
réunion de ces deux chaînes forme un cycle pas sant par x, le som met x n’est donc pas
un som met d’arti cu lation. Réci pro que ment, si pour tout des cen dant u et pré dé ces -
seur t de x dans l’arbo res cence, il n’existe pas d’arête de retour {u, t}, les arêtes de
retour dans un par cours en pro fon deur ayant leurs deux extré mi tés sur un même che -
min de l’arbo res cence, toute chaîne reliant t et u passe néces sai re ment par le som met
x. x est donc un som met d’arti cu lation. La pro priété est alors démon trée.
1. le lecteur pourra sauter cette preuve, en première lecture.
Figure 3.30