next up previous
suivant: Sous graphes, graphes partiels monter: Chemins, Chaînes, Circuits, Cycles précédent: Définitions générales

Chemin Eulérien, chemin Hamiltonien

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}
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}
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