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

La condition est nécessaire

En remplaçant $ (i,\,j)$ par $ (j,\,k)$ dans $ T^*$, on conserve la structure d'arbre couvrant. Si $ c_{kl} < c_{ij}$, alors le remplacement de $ (i,\,j)$ par $ (k,\,l)$ permet d'obtenir un meilleur arbre ce qui contredit l'hypothèse d'optimalité.

Bruno Garcia 2000-12-17