Chapitre 3 • Éléments de la théorie des graphes
78
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 adja cent à un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets adja cents sont ouverts ou fer més ;
c(x) d p.
La figure 3.18 four nit le résul tat de l’appli ca tion de cet algo rithme au graphe
donné par la figure 3.12. La valeur ins crite à côté de chaque som met x, soit c(x),
indique le numéro de la compo sante connexe à laquelle appar tient le som met x.
Figure 3.18 La forêt couvrante importe p 5 3 arborescences : G a 3 composantes connexes.
La jus ti fi cation de la vali dité de cet algo rithme se fait de la manière sui vante :
soit x le som met le pre mier ouvert d’une compo sante connexe (donc dans l’ordre
de prévisite). Dans la forêt cou vrante (c’est- à-dire à l’ensemble des arbo res cences)
rela tive au par cours effec tué, x n’a pas de pré dé ces seur (sinon x ne pour rait pas être
le pre mier som met prévisité de sa compo sante connexe), x est donc une racine. Si
un som met y appar tient à la même compo sante que x, il existe une chaîne du graphe
reliant x et y. Il est aisé de véri fier que, dans ce cas, il y a un che min de x à y dans la
forêt cou vrante. Réci pro que ment, si un som met y n’appar tient pas à la compo sante
connexe de x, il n’existe pas de chaîne reliant x et y dans le graphe et, a for tiori, il n’y
a pas de che min de x à y dans la forêt cou vrante rela tive au par cours effec tué. Donc
chaque arbo res cence de la forêt cor res pond à une compo sante connexe du graphe et
réci pro que ment. Il est aisé de véri fier que les som mets ouverts lors des exécutions de
l’ins truc tion 2 sont les racines de la forêt cou vrante : A, C et M dans la figure 3.18.
Ceci ter mine notre démons tra tion.
Nous pou vons faci le ment remar quer que la complexité de cet algo rithme est iden -
tique à celle du par cours, soit O(m 1 n).
3.2.2 Par cours d’un graphe orienté
Nous pré sen tons dans ce para graphe un algo rithme géné rique effec tuant le par cours
d’un graphe orienté. La simi li tude avec l’algo rithme pré senté plus haut pour les graphes non orien tés étant impor tante, le lec teur est invité à se repor ter au para graphe pré -
cé dent pour tout ce qui concerne la ter mi no logie uti li sée. L’algo rithme est le sui vant.
78
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 adja cent à un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets adja cents sont ouverts ou fer més ;
c(x) d p.
La figure 3.18 four nit le résul tat de l’appli ca tion de cet algo rithme au graphe
donné par la figure 3.12. La valeur ins crite à côté de chaque som met x, soit c(x),
indique le numéro de la compo sante connexe à laquelle appar tient le som met x.
Figure 3.18 La forêt couvrante importe p 5 3 arborescences : G a 3 composantes connexes.
La jus ti fi cation de la vali dité de cet algo rithme se fait de la manière sui vante :
soit x le som met le pre mier ouvert d’une compo sante connexe (donc dans l’ordre
de prévisite). Dans la forêt cou vrante (c’est- à-dire à l’ensemble des arbo res cences)
rela tive au par cours effec tué, x n’a pas de pré dé ces seur (sinon x ne pour rait pas être
le pre mier som met prévisité de sa compo sante connexe), x est donc une racine. Si
un som met y appar tient à la même compo sante que x, il existe une chaîne du graphe
reliant x et y. Il est aisé de véri fier que, dans ce cas, il y a un che min de x à y dans la
forêt cou vrante. Réci pro que ment, si un som met y n’appar tient pas à la compo sante
connexe de x, il n’existe pas de chaîne reliant x et y dans le graphe et, a for tiori, il n’y
a pas de che min de x à y dans la forêt cou vrante rela tive au par cours effec tué. Donc
chaque arbo res cence de la forêt cor res pond à une compo sante connexe du graphe et
réci pro que ment. Il est aisé de véri fier que les som mets ouverts lors des exécutions de
l’ins truc tion 2 sont les racines de la forêt cou vrante : A, C et M dans la figure 3.18.
Ceci ter mine notre démons tra tion.
Nous pou vons faci le ment remar quer que la complexité de cet algo rithme est iden -
tique à celle du par cours, soit O(m 1 n).
3.2.2 Par cours d’un graphe orienté
Nous pré sen tons dans ce para graphe un algo rithme géné rique effec tuant le par cours
d’un graphe orienté. La simi li tude avec l’algo rithme pré senté plus haut pour les graphes non orien tés étant impor tante, le lec teur est invité à se repor ter au para graphe pré -
cé dent pour tout ce qui concerne la ter mi no logie uti li sée. L’algo rithme est le sui vant.