next up previous
suivant: Application à l'algorithme de monter: Les algorithmes de recherche précédent: L'algorithme de Prim

Démonstration unifiée

Ce résultat permet de déduire un algorithme générique de recherche d'un ACM incluant, en cas particuliers, ceux de Kruskal et de Prim.
\begin{lemme}
Soit $F$\ un ensemble de $p\,<\,n-1$\ arètes inclus dans un ACM d...
...um de $H$. Alors,
$F\:\Cup\:(i,\,j)$\ est inclus dans un ACM de G.
\end{lemme}
Démonstration : Soit $ T$ l'ACM contenant $ F$. Si $ (i,\,j)$ est aussi dans $ T$ le lemme est démontré. Sinon, nous allons exhiber un procédé de construction d'un nouvel ACM $ T'$ contenant $ F\:\Cup\:(i,\,j)$. $ T$ étant un ACM il existe une chaîne unique reliant $ i$ à $ j$. Soit $ (z,\,t)$ l'arète de cette chaîne incluse dans $ [S, \, \overline{S}]$. Par construction $ (z,\,t) \:
\not\in \; F$. On pose alors $ T'\,=\,T \: \backslash \: \{(z,\,t)\} \: \Cup \:
\{(i,\,j)\}$. $ T'$ est assurément un arbre couvrant car l'ajout de l'arète $ (i,\,j)$ reconnecte les 2 parties séparées par la suppression de $ (z,\,t)$. En outre, par hypothèse sur le coût de $ (i,\,j)$ il est de coût minimal : c'est donc un ACM. Finalement $ F\:\Cup\:\{(i,\,j)\}\:\subset\:T'$ ce qui conclue la démonstration. Les algorithmes de Kruskal et Prim sont des applications directes de ce théorème où initialement $ F\,=\,\emptyset$.

Sous-sections

Bruno Garcia 2000-12-17