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. Il porte le nom du mathématicien Jakob Steiner.

L'arbre de Steiner a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications.

Définitions[modifier | modifier le code]

Définition informelle[modifier | modifier le code]

Il existe plusieurs variante du problème de l'arbre de Steiner. Une description globale est la suivante : étant donné un certain nombre de sommet, trouver un «réseau» dont la longueur totale est minimale, et tel qu'il existe un chemin entre toute paire de points.

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.

Applications[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[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).