suivant: Sous graphes, graphes partiels
monter: Chemins, Chaînes, Circuits, Cycles
précédent: Définitions générales
Ces deux types particuliers de chemin et de cycle, que l'on retrouve dans les
cas orientés ou non orientés sont particulièrement intéressants car on les
retrouve dans de nombreux problèmes appliqués.
![\begin{defi}[Chemin Eulérien]
On qualifie d'Eulérien un chemin qui passe une et une seule fois par chaque
arc du graphe qui lui sert de support.
\end{defi}](img61.png)
En outre, si l'on impose que l'origine et la destination du chemin soit
confondues, on parle de circuit Eulérien.
L'application industrielle la plus spectaculaire est connue sous le nom de
problème du postier Chinois (ou problème Chinois du facteur) et consiste à
chercher le circuit Eulérien de longueur minimale sur un graphe aux arcs
valués.
![\begin{defi}[Chemin Hamiltonien]
On qualifie d'Hamiltonien un chemin qui passe ...
...une seule fois par chaque
sommet du graphe qui lui sert de support.
\end{defi}](img62.png)
En outre, si l'on impose que l'origine et la destination du chemin soit
confondues, on parle de circuit Hamiltonien.
A présent, valuons chaque arc du graphe et recherchons le circuit Hamiltonien
de longueur minimale sur le graphe. On obtient le problème ultra classique du
Voyageur de Commerce.
Bruno Garcia
2000-12-17