Arbre couvrant de poids minimal

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 (ACM) 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 (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum^{[réf. nécessaire]}.

L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur.

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).

Propriétés

Multiplicité ou unicité

Un graphe connexe (en haut) et le dessin deux arbres couvrants minimums (en bas).

Comme le montre la figure ci-contre, un graphe connexe peut comporter plusieurs arbres couvrants minimum différents, mais si tous les poids sont différents, alors il est unique. Un graphe non orienté et général possède une forêt couvrante de poids minimal.

Propriétés des cycles et des coupes

Pour tout cycle dans le graphe, si une arête est de poids strictement plus grand que les autres, alors cette arête n'est pas dans l'arbre couvrant de poids minimal. Autrement dit, toute arête (u,v) du graphe est de poids supérieur ou égal à l'arête de poids maximum sur le chemin reliant u à v dans l'arbre.

Pour toute coupe du graphe, si une arête est de poids strictement inférieur aux autres, alors elle appartient à l'arbre couvrant de poids minimal.

Poids de l'arbre d'un ensemble de points

Un problème classique est de savoir, étant donné un ensemble de points dans $\mathbb {R} ^{d}$ avec la norme euclidienne, quel est le poids de l'arbre couvrant minimal. Il est de l'ordre de $n^{\frac {d-1}{d}}$ en moyenne et avec probabilité 1[1].

Aspects algorithmiques

Algorithmes classiques

Il existe de nombreux algorithmes de construction d'un arbre couvrant de poids minimal. Par exemple l'algorithme de Borůvka (le premier algorithme inventé pour ce problème), l'algorithme de Prim et l'algorithme de Kruskal. Ces algorithmes sont tous des algorithmes gloutons.

Algorithmes rapides

Un algorithme plus rapide et plus complexe est dû à Bernard Chazelle[2]. Sa complexité est presque linéaire.

Il existe des algorithmes en temps linéaire pour certains cas particuliers, par exemple les graphes denses[3]. On peut aussi atteindre un temps linéaire avec un algorithme probabiliste[4].

Algorithme de vérification

Il existe un algorithme en temps linéaire qui, étant donné un arbre couvrant, vérifie s'il est ou non de poids minimal[5]^,[6].

Applications

Les arbres couvrants sont notamment utilisés dans plusieurs types de réseaux, comme les réseaux téléphoniques et les réseaux de distribution[7]. Hors du contexte des réseaux, ils sont utiles par exemple pour le partitionnement de données et le traitement d'image[7].

D'autres algorithmes calculent un arbre couvrant de poids minimal. Par exemple, l'algorithme de Christofides calcule un arbre couvrant de poids minimal pour approximer le problème du voyageur de commerce dans le cas métrique.

Variantes et objets proches

On peut définir diverses variantes du problème de l'arbre couvrant minimum, par exemple un plongement géométrique du graphe, ou avec un modèle dynamique, distribué, etc. Un problème proche est le problème de l'arbre de Steiner.

Notes et références

Jillian Beardwood, John H Halton et John Michael Hammersley, « The shortest path through many points », Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, vol. 55, n^o 04,‎ 1959, p. 299-327
Bernard Chazelle, « A minimum spanning tree algorithm with Inverse-Ackermann type complexity », Journal of the ACM, vol. 47, n^o 6,‎ 2000, p. 1028-1047.
Michael L. Fredman et Robert Endre Tarjan, « Fibonacci heaps and their uses in improved network optimization algorithms », Journal of the ACM, vol. 34, n^o 3,‎ 1987, p. 596-615.
David R. Karger, Philip N. Klein et Robert Endre Tarjan, « A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees », Journal of the ACM, vol. 42, n^o 2,‎ 1995, p. 321-328 (DOI 10.1145/201019.201022)
(en) Valerie King, « A Simpler Minimum Spanning Tree Verification Algorithm », Algorithmica, vol. 18, n^o 2,‎ 1997, p. 263-270
Présentation de la méthode Minimum Spanning Tree Verification In Linear Time Complexity par Valerie King
R. L. Graham et Pavol Hell, « On the history of the minimum spanning tree problem », Annals of the History of Computing, vol. 7, n^o 1,‎ 1985, p. 43-57 (DOI 10.1109/MAHC.1985.10011, Math Reviews 783327)

(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).

Bibliographie

Articles

(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)[PDF] James Allen Fill et J. Michael Steele, Exact expectations of minimal spanning trees for graphs with random edge weights, 2004

Ouvrages

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition], chap. 23 : Minimum Spanning Trees, p. 561–579

Liens externes

Jason Eisner, « State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion », sur Université de Pennsylvanie, 1997

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Jillian Beardwood, John H Halton et John Michael Hammersley, « The shortest path through many points », Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, vol. 55, n^o 04,‎ 1959, p. 299-327

[2] Bernard Chazelle, « A minimum spanning tree algorithm with Inverse-Ackermann type complexity », Journal of the ACM, vol. 47, n^o 6,‎ 2000, p. 1028-1047.

[3] Michael L. Fredman et Robert Endre Tarjan, « Fibonacci heaps and their uses in improved network optimization algorithms », Journal of the ACM, vol. 34, n^o 3,‎ 1987, p. 596-615.

[4] David R. Karger, Philip N. Klein et Robert Endre Tarjan, « A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees », Journal of the ACM, vol. 42, n^o 2,‎ 1995, p. 321-328 (DOI 10.1145/201019.201022)

[5] (en) Valerie King, « A Simpler Minimum Spanning Tree Verification Algorithm », Algorithmica, vol. 18, n^o 2,‎ 1997, p. 263-270

[6] Présentation de la méthode Minimum Spanning Tree Verification In Linear Time Complexity par Valerie King

[history-7] R. L. Graham et Pavol Hell, « On the history of the minimum spanning tree problem », Annals of the History of Computing, vol. 7, n^o 1,‎ 1985, p. 43-57 (DOI 10.1109/MAHC.1985.10011, Math Reviews 783327)