Problèmes de chemins
111
est appelé une entrée du graphe
est un sommet isolé
est le nombre d’arcs ayant pour extrémité
6.2.5. Chemins et chaînes
Soit un graphe
.
Un chemin dans le graphe est constitué par une suite d'arcs
telle que
tout arc de cette suite, sauf le dernier, a pour extrémité terminale l'extrémité initiale de
l'arc suivant.
Un chemin fini dont le sommet terminal coïncide avec le sommet initial est appelé
circuit.
La longueur d'un chemin est le nombre d'arcs qu'il comporte.
Un chemin est dit simple s'il ne comporte pas plusieurs fois le même arc; il est
élémentaire s'il ne passe pas plus d'une fois par le même sommet.
Un chemin qui passe une fois et une seule par tous les sommets du graphe est dit
hamiltonien; si en plus, c'est un circuit, on dira que c'est un circuit hamiltonien.
Si le nombre de sommets
, tout chemin hamiltonien comporte
arcs, et tout
circuit hamiltonien arcs.
Par exemple sur le graphe ci-dessous :
la suite :
constitue un chemin qui n'est ni simple ni élémentaire.
Par contre le chemin de longueur 3 :
est simple et élémentaire ainsi que le
circuit
, de longueur 4.
Figure 5
Enfin, on peut trouver un chemin hamiltonien :
et un circuit
hamiltonien :
.