next up previous
suivant: Démonstration monter: Notion d'arbre précédent: Définitions fondamentales

Démonstration de l'équivalence des définitions sur les arbres

La démonstration de l'équivalence de ces propositions nécessite un théorème intermédiaire.
\begin{theo}
Soit $G\,=\,\left\{X,\,E\right\}$\ un graphe quelconque, alors~:...
...q n-1$
\item Si $G$\ est connexe, alors $m \geq n-1$
\end{itemize}
\end{theo}
La démonstration de ce théorème se fait de manière constructive. En effet, considérons un graphe $ G\,=\,\left\{X,\,E\right\}$, $ \vert X\vert=n$ dont l'on retire tous les arcs. On ajoute alors les arcs 1 par 1. A un instant donné, la situation peut être telle que représentée par la figure (2.1).

Figure 2.1: Construction d'un arbre : situation de base
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=carbre1.eps}
\end{center}
\end{figure}

Lorsque l'on rajoute un arc, 2 cas peuvent se présenter :
  1. L'arc réunit 2 sommets de la même composante connexe (2.2.a).
  2. L'arc réunit 2 sommets appartenant à des composantes connexes différentes (2.2.b).

    Figure 2.2: Construction d'un arbre : opérations élémentaires
    \begin{figure}
\leavevmode
\begin{center}
\begin{tabular}{c}
\psfig{figure=c...
...
\psfig{figure=carbre3.eps}\\
(b)
\end{tabular}
\end{center}
\end{figure}

    Appliquons ce principe de construction à la démonstration du théorème précédent. Si l'on désire que le graphe soit sans cycle, il nous faut procéder par la deuxième méthode d'ajout d'arc. Initialement, comme il n'y a pas d'arcs, il y a $ n$ composantes connexes. A chaque ajout d'arc, le nombre de composantes connexes diminue de 1 unité. Après avoir ajouté $ n-1$ arcs par cette méthode, il ne reste qu'une seule composante connexe, le graphe est donc connexe. Si maintenant, l'on construit un graphe par l'un ou l'autre principe de construction, il faut ajouter au moins (n-1) arcs avant d'obtenir une seule composante et donc un graphe connexe. D'où la seconde partie du théorème. En vertu du premier principe de construction, tout ajout d'arc rajoutera un cycle, ce qui démontre la première partie du théorème. Une fois le théorème démontré, les implications suivantes sont évidentes :

    \begin{displaymath}
\left\{
\begin{array}{@{(}l@{)}@{\:\Rightarrow\:}@{(}r@{)}...
... 1 \\
0 & 2 \\
1 & 4 \\
2 & 3
\end{array}
\right.
\end{displaymath}

    Pour démontrer l'équivalence des propriétés sur les arbres, nous allons créer la boucle d'implications suivante (les implications non encore démontrées sont en gras) :

    \begin{displaymath}
\left\{
\begin{array}{@{(}l@{)}@{\:\Rightarrow\:}@{(}r@{)}...
...f{5} \\
\mathbf{5} & \mathbf{0} \\
\end{array}
\right.
\end{displaymath}



Sous-sections
next up previous
suivant: Démonstration monter: Notion d'arbre précédent: Définitions fondamentales
Bruno Garcia 2000-12-17