Graphes 08 : Arbres couvrants, Kruskal, Prim et union-find

Relier tous les bâtiments d'un campus demande de choisir des câbles, pas une tournée de véhicule. Chaque liaison installée coûte une somme fixe. On cherche à rendre tous les bâtiments accessibles les uns depuis les autres en minimisant la facture totale. Kruskal et Prim résolvent ce problème par deux constructions différentes. Leur comparaison montre pourquoi une règle de choix doit toujours être accompagnée d'un argument de correction.

1. Définir l'objet que l'on optimise

L'absence de cycle évite les liaisons redondantes dans la solution demandée. Cela ne veut pas dire qu'un réseau réel devrait toujours être un arbre : la résistance aux pannes peut justifier des liaisons de secours. Le problème mathématique minimise ici le coût sans imposer cette redondance. Ajouter une contrainte de disponibilité modifierait la question.

Les poids peuvent être négatifs pour ces algorithmes ; la sélection reste un ensemble fini d'arêtes sans répétition. Si le graphe n'est pas connexe, aucun arbre ne peut couvrir tous les sommets. On obtient alors une forêt couvrante minimale, avec un arbre par composante. Il faut annoncer cette différence au lieu d'appeler la forêt un arbre unique.

2. Ne pas confondre installation et trajets minimaux

Prenons un triangle avec AB de poids 2, AC de poids 2 et BC de poids 1. L'arbre des plus courts chemins depuis A utilise AB et AC, de coût total 4. Un arbre couvrant minimal utilise BC et AB, de coût total 3. Dans ce dernier, atteindre C depuis A coûte 3 au lieu de 2. Réduire la facture globale peut donc allonger certains trajets.

Sur notre réseau principal, les deux constructions se trouvent coïncider : c'est une propriété de cet exemple, pas un théorème général. Le triangle évite d'apprendre une fausse équivalence à partir d'un seul dessin. Pour comparer deux algorithmes, il faut commencer par vérifier qu'ils optimisent le même objet.

3. Kruskal : trier puis relier des groupes différents

Trier les arêtes par poids croissant
Créer un groupe séparé pour chaque sommet
Pour chaque arête (u, v, poids) dans cet ordre :
    Si u et v appartiennent à des groupes différents :
        retenir l'arête
        réunir les deux groupes
    Si n − 1 arêtes ont été retenues : arrêter

Sur notre réseau, les premières arêtes retenues sont BC de poids 1, AC de poids 2, DE de poids 2 et EF de poids 3. AB de poids 4 est refusée : A et B sont déjà reliés par A–C–B. BD de poids 5 réunit ensuite les deux groupes restants. Le coût final vaut 13.

Les égalités de poids sont départagées par les étiquettes pour stabiliser la trace. D'autres choix peuvent donner un autre arbre minimal si plusieurs solutions existent. L'égalité des coûts optimaux importe davantage que l'identité de toutes les arêtes. On peut arrêter dès que n − 1 arêtes sont acceptées, puisque la forêt est alors devenue un arbre.

4. Union-find : tester les groupes efficacement

Une implantation représente chaque ensemble par un arbre de parents. Le représentant est une racine dont le parent est elle-même. Ces parents sont internes à la structure : ils ne décrivent pas nécessairement les arêtes retenues dans le réseau. Les confondre produirait un dessin d'arbre couvrant incorrect.

La réunion par taille accroche le plus petit arbre de représentants sous le plus grand. La compression de chemin rapproche les sommets visités de leur racine lors d'une recherche. Ensemble, ces techniques donnent un coût amorti très faible, exprimé par la fonction inverse d'Ackermann α(n). Cela ne rend pas Kruskal entièrement constant : le tri des arêtes reste généralement dominant.

Avec une liste d'arêtes, Kruskal coûte O(m log m) pour le tri, plus O(m α(n)) pour les opérations de groupes et O(n) d'initialisation. La structure union-find utilise O(n) de mémoire ; les arêtes et leur ordre de tri doivent aussi être stockés. Sur un graphe simple, la borne de tri est couramment écrite O(m log n).

5. Prim : agrandir un seul arbre

Depuis A, Prim retient AC de poids 2, puis CB de poids 1, BD de poids 5, DE de poids 2 et EF de poids 3. Le total vaut encore 13. Contrairement à Kruskal, il ne trie pas toutes les arêtes pour fusionner des groupes dispersés : il étend un arbre unique depuis son point de départ.

Un tas binaire peut maintenir le meilleur coût d'accès à chaque sommet extérieur. Avec des listes d'adjacence et une gestion directe des priorités, le coût est O((n + m) log n), avec O(n) de mémoire auxiliaire. Avec une matrice et une sélection linéaire, une version simple coûte O(n²). Comme pour Dijkstra, il faut préciser la structure de priorité utilisée.

La clé de Prim est le poids d'une seule arête qui rattache le sommet à l'arbre. La clé de Dijkstra est le coût total d'un trajet depuis une source. Les deux pseudo-codes peuvent sembler proches, mais remplacer l'une de ces quantités par l'autre change complètement le problème résolu.

6. Justifier le choix par une coupe

Considérons un arbre optimal qui n'utilise pas l'arête candidate. L'ajouter crée un cycle. Ce cycle traverse aussi la coupe par une autre arête. Remplacer cette autre arête par la candidate conserve la connexité et supprime le cycle. Puisque la candidate n'est pas plus lourde, le coût n'augmente pas. Il existe donc un arbre optimal compatible avec le choix.

Pour Prim, la coupe sépare l'arbre courant du reste. Pour Kruskal, elle peut isoler une composante de la forêt courante ; l'ordre des poids garantit un choix approprié entre composantes. Cet argument explique pourquoi les règles fonctionnent. Il ne suffit pas de constater que les premières arêtes paraissent bon marché.

Une vérification indépendante a également énuméré les 126 ensembles de 5 arêtes possibles dans notre réseau et testé ceux qui forment un arbre. Leur coût minimal est bien 13. Cette vérification exhaustive sert de contrôle sur le petit exemple ; elle ne remplace pas les algorithmes pour les grands réseaux.

Exercices corrigés

Voir le programme complet · Faire les 30 exercices du TD