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. L'arbre de Steiner a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications.

Définition et comparaison avec 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.

Définition formelle du problème[modifier | modifier le code]

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