Arbres couvrants minimaux

Un arbre couvrant minimal connecte tous les sommets d'un graphe pondéré et connexe avec le poids total d'arêtes le plus faible possible ; des algorithmes gloutons tels que ceux de Kruskal et de Prim en calculent un efficacement.

Definition

Un arbre couvrant minimal d'un graphe connexe et pondéré par les arêtes est un sous-ensemble d'arêtes qui connecte tous les sommets, ne contient aucun cycle et possède le poids total minimal parmi tous les arbres couvrants de ce type.

Scope

Ce sujet couvre le problème de l'arbre couvrant minimal et ses solutions gloutonnes classiques — l'algorithme de Kruskal, qui ajoute des arêtes par ordre de poids croissant en utilisant une structure d'ensembles disjoints, et l'algorithme de Prim, qui construit un arbre unique à l'aide d'une file de priorité — ainsi que les propriétés de coupe et de cycle qui prouvent la correction de ces algorithmes. Il aborde également la structure de données d'ensembles disjoints (union-find) qui les supporte.

Core questions

• Qu'est-ce qu'un arbre couvrant, et qu'est-ce qui en fait un arbre de poids minimal ?
• Pourquoi les ajouts gloutons d'arêtes produisent-ils un arbre couvrant minimal global ?
• Comment la propriété de coupe et la propriété de cycle justifient-elles les algorithmes d'ACM ?
• En quoi les algorithmes de Kruskal et de Prim diffèrent-ils en termes de stratégie et de structures de données ?
• Comment la structure d'ensembles disjoints (union-find) rend-elle l'algorithme de Kruskal efficace ?

Key concepts

• arbre couvrant
• propriété de coupe
• propriété de cycle
• algorithme de Kruskal
• algorithme de Prim
• ensembles disjoints (union-find)
• arête sûre gloutonne
• poids des arêtes

Key theories

Propriété de coupe

Pour toute partition des sommets en deux ensembles, l'arête de poids minimal traversant la partition appartient à un certain arbre couvrant minimal ; cette garantie d'arête sûre est la base de la correction des algorithmes gloutons de Kruskal et de Prim.

Support union-find d'ensembles disjoints

L'algorithme de Kruskal utilise une structure union-find avec union par rang et compression de chemin pour tester, en temps amorti quasi constant, si l'ajout d'une arête créerait un cycle.

Clinical relevance

Les arbres couvrants minimaux modélisent la conception de réseaux à coût minimal : la mise en place de réseaux de communication, électriques ou de transport qui connectent tous les sites à moindre coût. Ils servent également de blocs de construction dans le regroupement (clustering), la segmentation d'images, les algorithmes d'approximation pour le problème du voyageur de commerce et l'analyse d'ensembles de points.

History

Le problème de l'arbre couvrant minimal a été résolu pour la première fois par Otakar Borůvka en 1926 pour la conception de réseaux électriques. Vojtěch Jarník (1930), puis Prim (1957) et Dijkstra ont développé l'approche de construction d'arbre, tandis que Kruskal (1956) a proposé la méthode gloutonne de tri des arêtes, faisant de ce problème l'un des premiers problèmes d'optimisation combinatoire bien compris.

Key figures

• Joseph Kruskal
• Robert Prim
• Otakar Borůvka
• Vojtěch Jarník

Seminal works

• kruskal1956
• cormen2009

Frequently asked questions

Quelle est la différence entre les algorithmes de Kruskal et de Prim ?

L'algorithme de Kruskal trie toutes les arêtes et les ajoute par ordre de poids croissant, en ignorant celles qui formeraient un cycle, en utilisant union-find pour détecter les cycles. L'algorithme de Prim construit un arbre connexe unique à partir d'un sommet de départ, en ajoutant de manière répétée l'arête la moins chère quittant l'arbre actuel, à l'aide d'une file de priorité. Les deux produisent un arbre couvrant minimal.

L'arbre couvrant minimal est-il unique ?

Si tous les poids des arêtes sont distincts, l'arbre couvrant minimal est unique. Lorsque certains poids sont égaux, il peut exister plusieurs arbres couvrants minimaux différents, tous ayant le même poids total minimal.