-0
0
c
:J
0
LI)
..--t
0
N
@
.......
..c
O'l
·;::::
>0..
0
u
Chapitre 6 • Graphes et ordonnancement
168
Tableau 6.14
Sommet
A
B
c
D
E
Successeurs
Prédécesseurs
B
C, D, E
A,E
c
D
15!1 M 1 et M 2 sont les matrices d'adjacence de deux graphes définis respectivement sur les ensembles S 1 = {A; B; C; D} et S 2 = {A; B; C; D; E}. Faire le tableau
des successeurs et des prédécesseurs de chaque graphe.
c) Combien y a-t-il de chemins de longueur 2 dans le graphe ? Les citer.
D
c
Figure 6.19
m a) Écrire la matrice d'adjacence M du graphe de la fig. 6.20 .
b) Calculer M 3 Expliquer pourquoi on peut affirmer qu'il existe deux chemins de
longueur 3 reliant B à A. Citer ces deux chemins.
c) Le graphe possède-t-il des circuits de longueur 3 ?
d) Calculer M
4 . Entre quels sommets n'existe-t-il pas de chemin de longueur 4?