"'O
0
c
:J
0
LI)
..--t
0
N
@
.......
..c
O'l
·;::::
>0..
0
u
Chapitre 6 • Graphes et ordonnancement
176
Tableau 6.28
Sommet
A
B
c
D
E
Successeurs
C, D
A,E
B, D
B, E
A,C
Prédécesseurs
B, E
C,D
A, E
A,C
B, D
0 1 0 1
( B a)M=
1 0 1 0
0 0 0 1
0 0 0 0
1 0 1 0
b) M
2 =
0 1 0 2
0 0 0 0
0 0 0 0
On sait que les coefficients de M
2 représentent les nombres de chemins de longueur
2 qui relient un sommet à un autre. Donc il n'y a pas de tels chemins reliant B à A, ou
à C. Un chemin relie B à lui-même et deux chemins relient B à D.
c) Dans la matrice, la somme des coefficients non nuls est 5 : il y a donc cinq
chemins de longueur 2 dans le graphe. Ces cinq chemins sont: (A,B,A), (A ,B,C),
(B,A,B), (B,A,D) et (B,C,D).
0 1 0 1
0 0 1
0 0 0
1
m a)M=
1
0 0 1 0
M 3 =
1 1 1 1
2 0 1 1
1 0 1 1
0 1 0 1
M4 =
2 1 1 2
1 2 1 2
1 1 1 1
1 0 1 1
b) Les coefficients de la matrice M
3 représentent le nombre de chemins de longueur
3 reliant chaque sommet aux autres. À l'intersection de la deuxième ligne et de la
première colonne, se trouve le nombre 2 qui est le nombre de chemins de longueur 3
reliant B à A. Ces deux chemins sont (B,A,B,A) et (B,D,C ,A) .
c) Un circuit étant un chemin dont le sommet de départ coïncide avec le sommet
d'arrivée, la matrice M
3 montre qu'il y a trois circuits : au départ de A, de Cet de D.
d) Il n'y a aucun chemin de longueur 4 entre D et B.