Arbre couvrant de poids minimal
 |
Cet article est une ébauche concernant l'informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
|
En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale. L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum.
Sommaire |
Propriété [modifier]
Un graphe peut comporter plusieurs arbres couvrants différents. On peut associer un poids à chaque arête, ce qui est un nombre qui représente le coût de cette arête, et prendre la somme des poids des arêtes de l'arbre couvrant. Un arbre couvrant de poids minimal est un arbre couvrant dont le poids est plus petit ou égal à celui de tous les autres arbres couvrants du graphe.
Un graphe non orienté et général possède une forêt couvrante de poids minimal.
Contexte [modifier]
Les graphes sont un outil de représentation puissant et l'arbre couvrant minimum peut s'interpréter de différentes manières selon ce que représente le graphe. De manière générale si on considère un réseau où un ensemble d'objets doivent être reliés entre eux (par exemple un réseau électrique et des habitations), l'arbre couvrant minimum est la façon de construire un tel réseau en minimisant un coût représenté par le poids des arêtes (par exemple la longueur totale de câble utilisée pour construire un réseau électrique).
Algorithmes liés à l'arbre couvrant de poids minimal [modifier]
Algorithmes de recherche de l'arbre couvrant de poids minimal [modifier]
Il existe de nombreux algorithmes de recherche d'un arbre couvrant de poids minimal. On citera, entre autres, l'algorithme de Borůvka (le premier algorithme inventé pour ce problème), l'algorithme de Prim et l'algorithme de Kruskal.
Algorithme de vérification de la minimalité d'un arbre couvrant [modifier]
Il existe un algorithme linéaire qui, étant donné un arbre couvrant, vérifie si il est ou non de poids minimal[1].
Un exemple de problème associé [modifier]
Un problème connu utilisant l'arbre du poids minimal est le suivant :
- on génère n points aléatoirement dans un carré de côté 1 ;
- on génère le graphe complet dont les sommets sont les points générés ;
- on résout le problème de l'arbre de poids minimal ;
- on calcule le poids total de l'arbre.
Ce poids est asymptotiquement égal à β√n avec β = 0,658…
Références [modifier]
- (en) Valerie King, Minimum Spanning Tree Verification In Linear Time Complexity
- (en) Jaroslav Nesetril, Eva Milková et Helena Nesetrilová, Otakar Boruvka on Minimum Spanning Tree Problem, 2000 (Translation of the both 1926 papers, comments, history ; section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.)
- (en) Bernard Chazelle, A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, 1999
- (en)[PDF] James Allen Fill et J. Michael Steele, Exact expectations of minimal spanning trees for graphs with random edge weights, 2004
- (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001 [détail de l’édition], chap. 23 : Minimum Spanning Trees, p. 561–579
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Minimum spanning tree » (voir la liste des auteurs)
