Problème de l'arbre de Steiner

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Arbre de Steiner)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Steiner.
Solution pour trois points. Le point de Steiner est au centre des trois autres points (il n'y a pas de connexion directe entre A, B et C).
Solution pour quatre points. Dans cet arbre, il y a deux points de Steiner : S_1 and S_2

En algorithmique, le problème de l'arbre de Steiner est un problème d'optimisation combinatoire.

Ce problème est relativement proche du problème de l'arbre couvrant minimal et a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications. Il porte le nom du mathématicien Jakob Steiner.

Définitions[modifier | modifier le code]

Il existe plusieurs variantes du problème.

Définition générale : espace métrique[modifier | modifier le code]

Dans un espace métrique, étant donné un ensemble de points P, un arbre pour P est un réseau (c'est-à-dire un ensemble de chemins connectés) tel que tous les points soient reliées, et un arbre est dit de Steiner si la longueur totale du réseau est minimale[1].

Définition géométrique : espace euclidien[modifier | modifier le code]

Dans la variante euclidienne du problème, l'espace métrique est un espace euclidien.

Définition d'optimisation combinatoire : graphes[modifier | modifier le code]

Le cadre le plus classique en optimisation combinatoire est le suivant : étant donné un graphe G, dont les arêtes ont des poids, et un sous-ensemble S de sommets de G, trouver un ensemble d'arêtes de poids minimal tel que le sous-graphe induit soit connexe et contienne tous les sommets de S[2].

Propriétés du problème euclidien[modifier | modifier le code]

Propriétés du problème d'optimisation combinatoire[modifier | modifier le code]

Comparaison avec le problème de l'arbre couvrant minimal[modifier | modifier le code]

Dans les deux problèmes, étant donné un ensemble V de sommets, il s'agit de trouver un arbre A de coût minimal reliant tous les sommets de V (où le coût de l'arbre est défini comme la somme du coût de ses arêtes). Contrairement au problème de l'arbre couvrant minimal où tous les sommets de l'arbre A doivent être dans V, dans le problème de l'arbre de Steiner il est autorisé d'utiliser des points en dehors de V.

Algorithmes et complexité[modifier | modifier le code]

Il existe différentes contraintes que l'on peut appliquer à l'arbre. La plupart des problèmes sont NP-complets (donc considérés comme difficiles à calculer). Quelques cas de figures sont solubles en temps polynomial. Il existe des algorithmes d'approximation pour le problème[2].

Applications[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer,‎ (ISBN 978-1556080104, lire en ligne)
  2. a et b (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems,‎

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Elsevier, North-Holland, 1992, ISBN 0-444-89098-X (Annals of Discrete Mathematics, vol. 53).