next up previous
suivant: Plus courts chemins monter: Démonstration de l'équivalence des précédent: Démonstration

Démonstration $ 5 \:\Rightarrow\: 0$

Supposons qu'il existe un cycle, alors, il est possible d'obtenir 2 chaînes reliant chaque sommet du cycle à un autre. En outre, l'existence d'une chaîne permettant de relier chaque couple du graphe est la définition même de la propriété de connexité. Ainsi se termine la démonstration d'équivalence des propriétés d'un arbre !
\begin{corollaire}
Ajouter un arc à un arbre créée un et un seul cycle
\end{corollaire}

\begin{corollaire}
Tout graphe connexe contient un graphe partiel qui est un arbre.
\end{corollaire}
Ce second corollaire est évident à démontrer par construction. Supprimons toutes les arêtes du graphe avant de les réintroduire sans créer de cycle : nous venons bien de créer un graphe partiel qui est un arbre !
\begin{defi}[Racine]
Soit un graphe orienté $G$. Le sommet $s$\ est dit \emph...
...ackslash \{s\} \quad$\ il existe un \emph{chemin}
de $s$\ vers $x$.
\end{defi}

\begin{defi}[Arborescence]
Un arbre \emph{orienté} admettant une racine est une \emph{arborescence}
\end{defi}
C'est un abus de langage commun que d'appeler arbre une arborescence. La figure suivante illuste 2 arbres, l'un est une arborescence, l'autre non.

Figure 2.3: Arborescence ou pas ?
\begin{figure}
\leavevmode
\begin{center}
\begin{tabular}{cc}
\psfig{figure=...
...arbo1.eps}\\
Arborescence & Arbre
\end{tabular}
\end{center}
\end{figure}



Bruno Garcia 2000-12-17