3.2 Par cours des graphes
81
© Dunod – Toute reproduction non autorisée est un délit.
9
10
début de la seconde passe
on a fermé C et
on a ouvert E
on a fermé E
Fin de la seconde passe
7
8
Fin de la première passe
puis on ferme G
puis on ouvre C
Figure 3.21
Acces si bi lité
Le pro blème de l’acces si bi lité dans un graphe consiste à déter mi ner l’ensemble des
des cen dants d’un som met donné s (que l’on a nommé en 3.1.3 : « fer me ture tran si -
tive » de s). Nous allons mon trer ici qu’un algo rithme résol vant ce pro blème peut
être sim ple ment obtenu en adap tant l’algo rithme géné rique pré senté pré cé de ment.
Consi dé rons l’algo rithme sui vant.
1. Ini tia le ment tous les som mets sont non mar qués ;
2. ouvrir s ;
3. tant que cela est pos sible exé cu ter l’une des ins truc tions 4 ou 5 ;
4.
ouvrir un som met y non mar qué s’il est suc ces seur d’un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets suc ces seurs sont ouverts ou fer més.
Le résul tat de l’appli ca tion de cet algo rithme au graphe donné par la figure 3.19,
pour le som met s 5 A, est repré senté en bas à droite de la figure 3.21. Les som mets
des cen dants de A sont les som mets appar te nant à l’arbo res cence (en traits épais)
ayant A pour racine.
Cet algo rithme se jus ti fie par la pro priété sui vante : si s est le pre mier som met
ouvert dans un par cours, alors il existe un che min du som met s au som met x dans
l’arbo res cence rela tive au par cours, si et seule ment si, il existe un che min de s à x
dans le graphe par couru. La preuve de cette pro priété est la sui vante : d’une part le