Combien d'arbres couvrants minimaux ?

1. Supposons deux arbres couvrants minimaux distincts $T_1$ et $T_2$, et soit $e$ l'arête de plus petit poids appartenant à l'un et pas à l'autre — disons $e\in T_1\setminus T_2$ ; elle est unique car les poids sont distincts. Ajouter $e$ à $T_2$ crée un cycle, qui contient au moins une arête $f\notin T_1$ (sinon $T_1$ contiendrait un cycle). Cette $f$ est dans $T_2\setminus T_1$, donc $p(f)>p(e)$ par le choix de $e$. Alors $T_2\cup \{e\}\setminus \{f\}$ est un arbre couvrant de poids $p(T_2)+p(e)-p(f)<p(T_2)$ : $T_2$ n'était pas minimal. Contradiction.

2. Non, et le graphe de l'exercice précédent en est le contre-exemple : le poids $5$ y figure deux fois ($ad$ et $ce$), le poids $7$ aussi ($ab$ et $be$), et pourtant la force brute ne trouve qu'un arbre de poids $39$ sur les $141$ arbres couvrants. La distinction des poids est suffisante, pas nécessaire.

3. Le triangle dont les trois arêtes pèsent $1$. Il a $3$ arbres couvrants — on en écarte une, au choix — et tous trois pèsent $2$ : les trois sont minimaux (vérifié par énumération). De même, le carré de côtés unitaires a $4$ arbres couvrants, tous minimaux de poids $3$.

Ce qu'il faut en retenir pour l'écriture du code. Kruskal rend un arbre minimal, celui que son ordre de tri lui a fait rencontrer. Deux exécutions avec deux tris différents peuvent rendre des ensembles d'arêtes différents — de même poids. Un jeu de tests doit donc comparer des poids, jamais des listes d'arêtes.