next up previous
suivant: La condition d'optimalité de monter: La condition d'optimalité de précédent: La condition est nécessaire

La condition est également suffisante

En effet, soit $ T^*$ un arbre satisfaisant la condition précédente et $ T^0$ un ACM tel que $ T^* \neq T^0$. Soit alors $ (i,\,j)$ une arête de $ T^* \, \backslash
\, T^0$. Si l'on supprime $ (i,\,j)$ de $ T^*$, on crée une coupe $ [S, \, \overline{S}]$ telle que $ i \, \in \,S$ et $ j \, \in \, \overline{S}$. Ajoutons maintenant cette arête $ (i,\,j)$ dans $ T^0$. Il va alors y avoir création d'un cycle qui contient nécessairement une arête $ (k,\,l)$ avec $ k \, \in \,S$ et $ l \, \in \,
\overline{S}$. Or : \begin{displaymath}\left\{
\begin{array}{lll}
T^* & \text{~Vérifie la conditio...
... ACM, d'où~:~} & c_{kl} \leqslant c_{ij}
\end{array}
\right.\end{displaymath} On en déduit immédiatement que $ c_{ij} = c_{kl}$. On peut donc remplacer $ (i,\,j)$ par $ (k,\,l)$ dans $ T^*$ sans altérer la propriété ce qui fait qu'à chaque étape $ T^*$ et $ T^0$ ont un arc commun de plus. On itère alors ce processus jusqu'au moment où $ T^*$ et $ T^0$ sont identiques.

Bruno Garcia 2000-12-17