Arbre couvrant de poids minimal

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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.

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.

Contexte et applications[modifier | modifier le code]

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

Propriétés[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

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.

Poids de l'arbre d'un ensemble de points[modifier | modifier le code]

Un problème classique est de savoir, étant donné un ensemble de points dans 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[modifier | modifier le code]

Algorithmes de recherche de l'arbre couvrant de poids minimal[modifier | modifier le code]

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. Ces algorithmes sont tous des algorithmes gloutons.

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

Algorithme de vérification de la minimalité d'un arbre couvrant[modifier | modifier le code]

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

Applications[modifier | modifier le code]

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[6]. Hors du contexte des réseaux, ils sont utiles par exemple pour le partitionnement de données et le traitement d'image[6].

Un arbre couvrant de poids minimal peut servir à résoudre d'autres problèmes, par exemple le problème du voyageur de commerce dans le cas métrique, avec l'algorithme de Christofides.

Variantes et objets proches[modifier | modifier le code]

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[modifier | modifier le code]

  1. « The shortest path through many points », Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, vol. 55, no 04,‎ 1959, p. 299-327
  2. Bernard Chazelle, « A minimum spanning tree algorithm with Inverse-Ackermann type complexity », Journal of the ACM, vol. 47, no 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, no 3,‎ 1987, p. 596-615.
  4. (en) Valerie King, « A Simpler Minimum Spanning Tree Verification Algorithm », Algorithmica, vol. 18, no 2,‎ 1997, p. 263-270
  5. Présentation de la méthode Minimum Spanning Tree Verification In Linear Time Complexity par Valerie King
  6. a et b R. L. Graham et Pavol Hell, « On the history of the minimum spanning tree problem », Annals of the History of Computing, vol. 7, no 1,‎ 1985, p. 43-57 (DOI 10.1109/MAHC.1985.10011)

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

Manuel[modifier | modifier le code]