-0
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
152
A
B
c
D
Figure 6.7
0 0 1 1
1 0 1 0
La matrice d'adjacence du graphe présenté fig. 6.7 est M =
0 0 0 1
0 1 0 0
0 1 0 1
Prenons p = 2. Les calculs matriciels nous donnent M
2
=
0 0 1 2
0 1 0 0
1 0 1 0
Considérons la deuxième ligne de la matrice M 2 . Elle concerne le sommet B du
graphe. Les deux premiers coefficients sont 0, cela veut dire qu'il n'y a pas de
chemin de longueur 2 qui relie B à A , ou B à B. Le troisième coefficient est 1, donc
il y a un chemin de longueur 2 qui relie B à C : le chemin (B,A, C).
Enfin, le dernier coefficient est 2, attestant l'existence de deux chemins de
longueur 2 reliant B à D : les chemins (B,A,D) et (B, C,D).
1 1 1 0
Prenons maintenantp = 3: M
3
=
0 2 0 1
1 0 1 0
0 0 1 2
Cette fois, la matrice M 3 permet de connaître le nombre de chemins de longueur 3
qui relient un sommet à un autre .
Par exemple, puisque le coefficient m 3 1 de la matrice M 3 vaut 1, cela signifie qu' il
,
y a un chemin de longueur 3 qui relie le sommet Cau sommet A : c' est le chemin
(C,D,B,A).
6.2.3 Opérations sur les matrices booléennes
Les matrices d'adjacences ne comportant que des 0 et des 1, on peut appliquer sur
leurs coefficients 1 ' addition et la multiplication booléennes.