"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
154
Exemple
0 1 0
1 1 0
2 3 0
Avec M = 1 1 0 , on a M[
4 l = 1 1 0 car M
4 = 3 5 0
0 0
1 1 0
1 2 0
La matrice booléenne permet d'affirmer qu'il y a au moins un chemin de longueur
4 entre A et A, ainsi qu'entre A et 8. Il en est de même entre 8 et A, 8 et 8, Cet A,
Cet 8.
6.2.4 Fermeture transitive d'un graphe
Faire la fermeture transitive d ' un graphe consiste à rajouter tous les arcs (ai.a) dès
qu'il existe un chemin allant du sommet a; au sommet aj"
Exemple
Sur le graphe présenté fig. 6.8, il existe un chemin allant de A à C en passant par
8 donc on ajoute l'arc (A,C).
c
A
B
Figure 6.8
De même, on constate qu'il faut ajouter les boucles (A,A) et (8,8). On obtient le
graphe complété fig. 6.9, sur lequel il ne reste aucun chemin sans l'arc« direct»
correspondant.
c
Figure 6.9
Ce nouveau graphe est la fermeture transitive du précédent.