Démonstration

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