Arbre couvrant de poids minimal

Soit $G = (S, A)$ un graphe non orienté muni d'une valuation des arêtes $c$, $T = (S_T, S_A)$ est un arbre couvrant $G$ si

• $T$ est un arbre
• $S_T = S$
• $T$ est connexe

Le poids de $T$ est

$$\sum_{a \in A_T}c(a)$$

Le problème de l'arbre couvrant de poids minimal est le suivant :

• données : un graphe $G$, une valuation $c$
• question : trouver l'arbre $T$ de plus petit poids parmi les arbres couvrant $G$.

Ce problème (d'optimisation) est facile, les deux algorithmes les plus connus sont ceux de Primm et de Kruskall.