3.2 Par cours des graphes
91
© Dunod – Toute reproduction non autorisée est un délit.
Som mets d’arti cu lation
Nous allons, à présent, mon trer comment un par cours en pro fon deur per met de
déter mi ner les som mets d’arti cu lation d’un graphe. Sans perte de géné ra lité, dans ce
qui suit, nous consi dé rons un graphe non orienté et connexe. En effet, la notion de
som met d’arti cu lation ne fait pas appel à l’orien ta tion du graphe.
Un som met x est appelé som met d’arti cu lation, si et seule ment si sa sup pres sion
rend le graphe non connexe. Ainsi les som mets A et E de la figure 3.27 sont des
som mets d’arti cu lation.
Figure 3.27
Nous lais sons le soin au lec teur de démon trer, à titre d’exer cice, la pro priété :
un som met x d’un graphe est un som met d’arti cu lation si et seule ment si il existe
deux som mets u et v dif fé rents de x, tels que toute chaîne reliant u à v passe par
x. Ainsi dans notre exemple, toute chaîne de I à B passe par x 5 A (et aussi par
xr 5 E) : A et E, nous l’avons déjà vu, sont des som mets d’arti cu lation. Ces pro -
prié tés sont uti li sées plus loin lors de la jus ti fi cation de la vali dité de l’algo rithme
que nous pro po sons.
Nous don nons ci- après un algo rithme déter mi nant les som mets d’arti cu lation
d’un graphe sup posé connexe. Cet algo rithme effec tue un par cours en pro fon deur à
par tir d’un som met ini tial s (choisi arbitrairement). L’ensemble d’arcs A, déter miné
au cours de l’algo rithme, cor res pond en fin d’application de l’algorithme aux arcs de
l’arbo res cence rela tive au par cours effec tué. Pour chaque som met x du graphe, deux
valeurs sont cal cu lées : prévisite(x) est le rang de x dans l’ordre de prévisite et hau -
teur(x) (qui est défi nie plus bas dans l’algo rithme) ; nous ver rons plus loin comment
la compa rai son des valeurs prévisite(x) avec les valeurs hau teur(x), per met de déter -
mi ner les som mets d’arti cu lation.
1. Ini tia le ment tous les som mets sont non mar qués ; prévisite d 1 ; A d \ ;
2. ouvrir le som met s et insé rer s au som met de la pile ;
3. prévisite(s) d prévisite ; prévisite d prévisite 1 1 ;
4. tant que la pile n’est pas vide faire (x étant le som met en haut de la pile) ;
5.
s’il existe un som met y non mar qué, adja cent au som met x ;
6.
alors ouvrir y ; insé rer y dans la pile ; 1 x, y2 H A ;
7.
prévisite(y) d prévisite ; prévisite d prévisite 1 1 ;
8.
hau teur(y) d prévisite(y) ;
91
© Dunod – Toute reproduction non autorisée est un délit.
Som mets d’arti cu lation
Nous allons, à présent, mon trer comment un par cours en pro fon deur per met de
déter mi ner les som mets d’arti cu lation d’un graphe. Sans perte de géné ra lité, dans ce
qui suit, nous consi dé rons un graphe non orienté et connexe. En effet, la notion de
som met d’arti cu lation ne fait pas appel à l’orien ta tion du graphe.
Un som met x est appelé som met d’arti cu lation, si et seule ment si sa sup pres sion
rend le graphe non connexe. Ainsi les som mets A et E de la figure 3.27 sont des
som mets d’arti cu lation.
Figure 3.27
Nous lais sons le soin au lec teur de démon trer, à titre d’exer cice, la pro priété :
un som met x d’un graphe est un som met d’arti cu lation si et seule ment si il existe
deux som mets u et v dif fé rents de x, tels que toute chaîne reliant u à v passe par
x. Ainsi dans notre exemple, toute chaîne de I à B passe par x 5 A (et aussi par
xr 5 E) : A et E, nous l’avons déjà vu, sont des som mets d’arti cu lation. Ces pro -
prié tés sont uti li sées plus loin lors de la jus ti fi cation de la vali dité de l’algo rithme
que nous pro po sons.
Nous don nons ci- après un algo rithme déter mi nant les som mets d’arti cu lation
d’un graphe sup posé connexe. Cet algo rithme effec tue un par cours en pro fon deur à
par tir d’un som met ini tial s (choisi arbitrairement). L’ensemble d’arcs A, déter miné
au cours de l’algo rithme, cor res pond en fin d’application de l’algorithme aux arcs de
l’arbo res cence rela tive au par cours effec tué. Pour chaque som met x du graphe, deux
valeurs sont cal cu lées : prévisite(x) est le rang de x dans l’ordre de prévisite et hau -
teur(x) (qui est défi nie plus bas dans l’algo rithme) ; nous ver rons plus loin comment
la compa rai son des valeurs prévisite(x) avec les valeurs hau teur(x), per met de déter -
mi ner les som mets d’arti cu lation.
1. Ini tia le ment tous les som mets sont non mar qués ; prévisite d 1 ; A d \ ;
2. ouvrir le som met s et insé rer s au som met de la pile ;
3. prévisite(s) d prévisite ; prévisite d prévisite 1 1 ;
4. tant que la pile n’est pas vide faire (x étant le som met en haut de la pile) ;
5.
s’il existe un som met y non mar qué, adja cent au som met x ;
6.
alors ouvrir y ; insé rer y dans la pile ; 1 x, y2 H A ;
7.
prévisite(y) d prévisite ; prévisite d prévisite 1 1 ;
8.
hau teur(y) d prévisite(y) ;