-0
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"' c::
·;::::
0
>c
o.
c
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c
:l
0
QJ
Solution du TD
b)
Tableau 6. l 0
Sommets
A
B
c
D
E
F
Successeurs
D
A
B,E
C,F
B
A,E
Prédécesseurs
B,F
C,E
D
A
C,F
D
c) Chaque sommet a au moins un prédécesseur, donc on ne peut pas ordonner le
graphe par niveaux.
d)
0 0 0 1 0 0
1 0 0 0 0 0
0 1 0 0 1 0
M=
0 0 1 0 0 1
0 1 0 0 0 0
1 0 0 0 1 0
Partie B
a)
1 1 0 0 2 0
0 0 1 0 0 1
M 3=
1 0 0 1 0 0
1 2 0 1 0 0
0 0 0 1 0 0
1 0 1 0 0 1
La dernière ligne donne le nombre de chemins de longueur 3 qui relient F à chacun
des autres sommets. Il y a donc :
• Un seul chemin qui va de F à A, à C ou à F.
• Aucun chemin de F à B, à C ou à E.
b) La dernière ligne de la matrice M
4 est : 1 1 0 1 2 O. Cette ligne donne le nombre
de chemins de longueur 4 reliant F aux autres sommets.
En quatre déplacements, on peut se retrouver en A, en B, en D ou en E.
Pour aller de F en A, le trajet est FADFA.
De F à B, le trajet est FADCB.
De F à D, on emprunte FEBAD. De F à E, les deux possibilités sont FADCE et
FADFE.
165