"'O
0
c
:J
0
:<:;
li)
.,,
c::
..--t
: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
Exercices corrigés
0 0 1 0 0
1 0 0 0 0
m
a)M= 0 1 0 1 0
0 1 0 0 1
0 1 1 0 0
1 1 2 0 0
1 1 0 0 1
b) M
4 = 1 2 1 2 0
1 2 1 1 1
1 2 2 1 0
c) Il y a 1 + 1 + 2 + 0 + 0 = 4 chemins de longueur 4 qui partent de A.
Un chemin relie A àA: (A,C,D,B,A).
Un chemjn relie A àB: (A,C,D,E,B), il est hamiltonien.
Deux chemins relient A à C: (A,C,B,A ,C) et (A,C,D,E ,C).
0 0 1
@Ill] a) M = 0 0 1
0 1 0
b) Il faut ajouter les arcs (B,B), (C,C) et ( A ,B).
0 1 0
0 0 1
c) M[
2 l = 0 1 0
M [3J = 0 0 1
0 0 1
0 1 0
0 1 0 1
0 0 1 0
@lll a) M =
0 0 0 1
0 0 0 0
b) Il faut ajouter les arcs (A,C) et (B ,D).
0 1 1 1
0 0 1 1
c) M = M + M [
2 l + M [ 3 l + M [
4 ] =
0 0 0 1
0 0 0 0
M =M +M[
2 l +M[ 3 l =
0 1 1
0 1 1
0 1 1
177