"'O
0
c
::J
..;
0
'03
lJ)
""'
......
c:
::l
0
~
N
"
@
]
..._,
Ci
.s::
:;
Ol
"'
'i:
c:
0
>c:
o.
c:
0
.9
u
ü
::l
""' 2
P.
!.:!
2l
::l
0
11
""' 0
c:
::l
0
©
Exercices corrigés
A
B
c
Figure 6.20
m a) Écrire la matrice d'adjacence M du graphe de la fig. 6.21.
b) Calculer M
4 .
c) Combien y a-t-il de chemins de longueur 4 qui partent de A ? Citer ces chemins.
Parmi eux, y a-t-il des chemins hamiltoniens ?
A
Figure 6.21
1!1111 a) Écrire la matrice d'adjacence M du graphe de la fig. 6.22.
b) Quels arcs doit-on rajouter pour faire la fermeture transitive du graphe ?
c) Calculer les matrices booléennes M [
2
] et M [
3 l. En déduire la matrice M de la
fermeture transitive.
A
c
B
Figure 6.22
169