"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Mathématiques pour l'informatique
288
b) Calculer M
2 . Expliquer la signification des nombres de la quatrième ligne de la
matrice.
c) Calculer M 3 . En déduire le nombre de chemins de longueur 3.
d) Parmi tous les chemins de longueur 3, combien y en a-t-il qui ne relient pas un
sommet à lui-même ? Et parmi eux, y a-t-il des chemins hamiltoniens ? Lesquels ?
lif.J:J Un graphe est défini par le tableau 6.39.
Tableau 6.39
Sommets
A
B
c
D
E
Successeurs
C, D
A
E
A
B, D
a) Écrire la matrice d'adjacence M de ce graphe.
b) Combien y a-t-il de chemins de longueur 4 au départ de D? Les citer.
c) Combien y a-t-il de chemins de longueur 4 arrivant sur D? Les citer.
lifil Un graphe est défini par le tableau 6.40.
Tableau 6.40
Sommets
A
B
c
D
E
F
Prédécesseurs
B
E
B, F
A
F
D
a) Écrire la matrice d'adjacence du graphe.
b) En utilisant une puissance de la matrice M, déterminer le nombre maximum de
chemins hamiltoniens du graphe. S'il en existe, écrire ces chemins.
c) Le graphe possède-t-il des circuits de longueur 6? Si oui, lesquels ?
@ln Un graphe défini sur l 'ensemble S = {A; B; C} est constitué de trois arcs: un
arc relie A à B, un autre relie B à C, et le troisième arc relie Cà A.
a) Tracer le graphe et faire sa fermeture transitive.
b) Écrire la matrice d 'adjacence M du graphe.
c) Calculer les matrices booléennes M[
2 l et M[
3
l
En déduire la matrice M de la fermeture transitive.
ml Un graphe est défini par le tableau 6.41.
Tableau 6.4 l
Sommets
A
B
c
Successeurs
B, E
--a) Dessiner le graphe.
D
E
E
c