Arbre de Steiner

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

L'arbre de Steiner (nommé en référence au mathématicien Jakob Steiner) est un problème d'optimisation combinatoire relativement proche du problème de l'arbre couvrant minimal. 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.

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

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. Pour les autres cas, la résolution se fait via une recherche heuristique.

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