"'O
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
6.2 • Chemins d'un graphe
Un chemin hamiltonien est un chemjn quj passe une seule fois par tous les
sommets du graphe.
Un circuit est un chemin dans lequel le premier et le dernier sommet sont identiques.
Exemple
Considérons le graphe présenté fig . 6. 5.
A
B
D
c
Figure 6.5
(B,D,C) et (B,A,D) sont des chemins, (A,C,0) n'en est pas un.
(A,D,C,A) est un circuit car c'est un chemin, et le premier sommet est le même que
le dernier.
(B,A,D,C) est un chemin hamiltonien. (B,O,C,A) en est un autre.
La longueur d'un chemin est égale au nombre d' arcs qui constituent ce chemin.
La longueur d'un chemin ayant n sommets est n - 1.
Exemple
A
B
D
c
Figure 6.6
Pour aller de A à D, il y a un chemin de longueur 2 : le chemin (A,B,D) .
Il y a aussi un chemin hamiltonien, de longueur 3 : le chemin (A,C,B,D).
6.2.2 Nombre de chemins de longueur donnée
Propriété 6.1
Soit M la matdce d'adjacence d'un graphe orienté à n sommets a 1 , a2' ... , anSoit p un entier et MP = (mi) la puissance d'exposant p de la matrice M.
Alors mi,j est le nombre de chemins de longueur p allant du sommet ai au sommet
af
151