Arbre De Steiner

Arbre de Steiner

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₁ and S₂

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, il s'agit de trouver, étant donné un ensemble V de sommets, un arbre A reliant tous les sommets de V. Alors que dans le problème de l'arbre couvrant minimal, tous les sommets de l'arbre A doivent être dans V, il est autorisé dans le problème de l'arbre de Steiner d'utiliser des points en dehors de V. Dans les deux problèmes, chaque arête a un coût donné. Le coût de l'arbre étant donné par la somme du coût de ses arêtes, il s'agit de trouver l'arbre de coût minimal.

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 (c'est-à-dire considérés comme difficiles à calculer). Quelques cas de figures sont résolubles en un temps polynomial. Pour les autres cas, la résolution se fait via une recherche heuristique.

Liens externes

• (en) Serveur d'applications Mathcad
• (en) GeoSteiner (un logiciel licence libre de recherche de solutions)
• (en) Ronald L Graham: The Shortest Network Problem, film de 1988
• (fr) Un logiciel constructeur d'arbres de Steiner pour Windows (gratuit)

Références

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

Ce document provient de « Arbre de Steiner ».