next up previous
suivant: Chemin Eulérien, chemin Hamiltonien monter: Chemins, Chaînes, Circuits, Cycles précédent: Chemins, Chaînes, Circuits, Cycles

Définitions générales


\begin{defi}[Chemin] On appelle \emph{chemin} depuis un sommet $s$\ vers un s... ...\ ( & i_{k-1} & ,\, & i_k=t & ) \end{array} \end{displaymath} \end{defi}

Figure 1.4: Exemple de chemin (en trait gras) du sommet 1 au sommet 4
\begin{figure} \leavevmode \begin{center} \psfig{figure=graphec1.eps} \end{center} \end{figure}

De manière plus littéraire, un chemin est une succession d'arcs qui permet de relier un sommet $ s$, l'origine du chemin, à un sommet $ t$, la destination du chemin, en empruntant chaque arc dans le bon sens, c'est à dire depuis son origine vers sa destination. La figure (1.4) illuste la notion de chemin depuis le sommmet 1 vers le sommet 4. Les arcs utilisés sont dessinés en gras. L'on voit immédiatement qu'ils sont toujours parcourus depuis leur origine vers leur destination. Ainsi la destination d'un arc est l'origine de son successeur dans le chemin. Si l'on relâche cette dernière contrainte, c'est à dire que l'on s'autorise à emprunter un arc à l'endroit ou à l'envers, on parle alors de chaîne.
\begin{defi}[Chaîne] Une chaîne est un chemin sur lequel on a relaché la contrainte d'orientation. \end{defi}
La notion de chaîne est la seule à avoir une signification dans le cas des graphes non orientés. La figure (1.5) illustre la notion de chaîne. Dans ce cas, on voit clairement que l'arc $ c$ est parcouru à contre-courant.

Figure 1.5: Exemple de cycle et de circuit
\begin{figure} \leavevmode \begin{center} \psfig{figure=graphec2.eps} \end{center} \end{figure}


\begin{defi}[Circuit, Cycle] Un \emph{circuit} est un chemin dont l'origine e... ...confondues. Dans le cas non orienté, on parle de \emph{cycle}. \end{defi}
La figure suivante illustre ces deux notions. Notez l'inversion du sens de l'arc $ d$ entre les deux dessins.

Figure 1.6: Exemple de chemin (en trait gras) du sommet 1 au sommet 4
\begin{figure} \leavevmode \begin{center} \begin{tabular}{cc} \psfig{figure=... ...e=graphec3.eps}\\ Cycle & Circuit \end{tabular} \end{center} \end{figure}


\begin{defi}[Chemin simple] Un chemin qui ne passe qu'une seule fois par chacun des arcs qu'il emprunte est dit \emph{simple} \end{defi}

\begin{defi}[Chemin élémentaire] Un chemin qui ne passe qu'une seule fois par chacun des sommets qu'il traverse est dit \emph{élémentaire} \end{defi}
Corollaire immédiat : Un chemin élémentaire est nécessairement simple.
\begin{theo} Tout chemin de $s$\ vers $t$\ contient un chemin élémentaire de $s$\ vers $t$. \end{theo}
La démonstration de cette propriété est laissée en exercice. Dans la suite de ce cours, on ne s'intéressera désormais plus qu'aux chemins élémentaires. Aussi, à partir de maintenant, la notion de chemin devra être comprise comme chemin élémentaire.
next up previous
suivant: Chemin Eulérien, chemin Hamiltonien monter: Chemins, Chaînes, Circuits, Cycles précédent: Chemins, Chaînes, Circuits, Cycles
Bruno Garcia 2000-12-17