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

La condition est nécessaire

Supposons qu'il existe une arête $ (k,\,l) \, \in \, [S,\,\overline{S}]$ tel que $ c_{kl} < c_{ij}$. Formons alors l'arbre $ \overline{T} = T^* \backslash \{(i,\,j)\} \cup
\{(k,\,l)\}$. $ \overline{T}$ est un arbre car la suppression de $ (i,\,j)$ crée une coupe à laquelle appartient également $ (k,\,l)$. Du coup, l'ajout de $ (k,\,l)$ n'ajoute pas de cycle et l'on obtient un arbre. Finalement, on obtient :

$\displaystyle C(\overline{T}) = C(T^*) - c_{ij} + c_{kl}
$

or comme $ c_{kl} < c_{ij}$, il en suit que $ C(\overline{T}) < C(T^*)$ ce qui contredit l'hypothèse selon laquelle $ T^*$ était optimal.

Bruno Garcia 2000-12-17