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.

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$.