3.2 Par cours des graphes
95
© Dunod – Toute reproduction non autorisée est un délit.
Les valeurs hau teur(y), cal cu lées par l’algo rithme, déter minent pour chaque som -
met y de l’arbo res cence le pre mier som met t pré cé dant y dans l’ordre de prévisite tel
que {u, t} soit une arête de retour, u étant le som met y ou un des cen dant de y. L’ins -
truc tion 13 de l’algo rithme per met de tester si la pro priété mon trée au para graphe
pré cé dant est satis faite. La preuve de l’algo rithme est alors ter mi née.
Rap pe lons que, sur l’exemple traité, pour le par cours effec tué à par tir de A, la
racine A a deux suc ces seurs dans l’arbo res cence. D’autre part, le som met E, qui est
un som met d’arti cu lation, est le qua trième dans la liste de prévisite et son suc ces seur,
le som met I, a pour valeur hau teur(I) 5 4. Dans le par cours effec tué à par tir de B
(figure 3.30), la racine B qui n’est pas un som met d’arti cu lation n’a qu’un seul suc -
ces seur dans l’arbo res cence. Le som met A de rang 3 dans la liste de prévisite, a pour
suc ces seur E pour lequel hau teur(E) 5 4 > 3. En revanche, le som met C qui n’est
pas un som met d’arti cu lation, qui a le deuxième rang dans l’ordre de prévisite, a
pour suc ces seur dans l’arbo res cence le som met A pour lequel hau teur(A) 5 1 , 2.
L’algo rithme pro posé étant appli qué à des graphes connexes, nous avons m > n 2 1
et la complexité obte nue est O1 n 1 m2 5 O1 m2 . En effet, les opé ra tions autres que
celles effec tuant le par cours sont en nombre infé rieur à celles du par cours.
NUMEROTATION “TOPOLOGIQUE” DES SOMMETS :
Si un graphe ne comporte pas de circuit, on peut numéroter ses sommets de manière
« topologique », c’est-à-dire que pour tout arc (x i , x j ), on ait : i < j.
On a vu plus haut que par un parcours en profondeur on peut déterminer si un
graphe comporte des circuits ou non.
Pour un graphe sans circuit, on peut trouver une numérotation topologique en
associant à tout sommet x k le numéro :
(n 1 1) 2 (numéro de fermeture de x k ) 5 N (x k )
Exemple : en gras, on a figuré l’arborescence d’un parcours en profondeur.
On a figuré à côté
de chaque sommet
son numéro d’ordre de
fermeture : 1 pour I, 2
pour H,..., 10 pour A.
Une numérotation
topologique est alors :
N(I) 5 11 2 1 5 10, N(H) 5 9, N(F 5 8), N(Dr) 5 7, N(G) 5 6, N(E) 5 5,
N(C) 5 4, N(D) 5 3, N(B) 5 2, N(A ) 5 1.
La figure 3. 32 illustre ce graphe avec ses sommets ainsi numérotés.
Figure 3.31
G
H
2
5
E
6
F
3
D´
4
A
10
B9
D8
7C
I
1
95
© Dunod – Toute reproduction non autorisée est un délit.
Les valeurs hau teur(y), cal cu lées par l’algo rithme, déter minent pour chaque som -
met y de l’arbo res cence le pre mier som met t pré cé dant y dans l’ordre de prévisite tel
que {u, t} soit une arête de retour, u étant le som met y ou un des cen dant de y. L’ins -
truc tion 13 de l’algo rithme per met de tester si la pro priété mon trée au para graphe
pré cé dant est satis faite. La preuve de l’algo rithme est alors ter mi née.
Rap pe lons que, sur l’exemple traité, pour le par cours effec tué à par tir de A, la
racine A a deux suc ces seurs dans l’arbo res cence. D’autre part, le som met E, qui est
un som met d’arti cu lation, est le qua trième dans la liste de prévisite et son suc ces seur,
le som met I, a pour valeur hau teur(I) 5 4. Dans le par cours effec tué à par tir de B
(figure 3.30), la racine B qui n’est pas un som met d’arti cu lation n’a qu’un seul suc -
ces seur dans l’arbo res cence. Le som met A de rang 3 dans la liste de prévisite, a pour
suc ces seur E pour lequel hau teur(E) 5 4 > 3. En revanche, le som met C qui n’est
pas un som met d’arti cu lation, qui a le deuxième rang dans l’ordre de prévisite, a
pour suc ces seur dans l’arbo res cence le som met A pour lequel hau teur(A) 5 1 , 2.
L’algo rithme pro posé étant appli qué à des graphes connexes, nous avons m > n 2 1
et la complexité obte nue est O1 n 1 m2 5 O1 m2 . En effet, les opé ra tions autres que
celles effec tuant le par cours sont en nombre infé rieur à celles du par cours.
NUMEROTATION “TOPOLOGIQUE” DES SOMMETS :
Si un graphe ne comporte pas de circuit, on peut numéroter ses sommets de manière
« topologique », c’est-à-dire que pour tout arc (x i , x j ), on ait : i < j.
On a vu plus haut que par un parcours en profondeur on peut déterminer si un
graphe comporte des circuits ou non.
Pour un graphe sans circuit, on peut trouver une numérotation topologique en
associant à tout sommet x k le numéro :
(n 1 1) 2 (numéro de fermeture de x k ) 5 N (x k )
Exemple : en gras, on a figuré l’arborescence d’un parcours en profondeur.
On a figuré à côté
de chaque sommet
son numéro d’ordre de
fermeture : 1 pour I, 2
pour H,..., 10 pour A.
Une numérotation
topologique est alors :
N(I) 5 11 2 1 5 10, N(H) 5 9, N(F 5 8), N(Dr) 5 7, N(G) 5 6, N(E) 5 5,
N(C) 5 4, N(D) 5 3, N(B) 5 2, N(A ) 5 1.
La figure 3. 32 illustre ce graphe avec ses sommets ainsi numérotés.
Figure 3.31
G
H
2
5
E
6
F
3
D´
4
A
10
B9
D8
7C
I
1