Arbre De Steiner

Arbre de Steiner

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 : S1 and S2

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

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).
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Arbre de Steiner ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre De Steiner de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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 …   Wikipédia en Français

  • 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) …   Wikipédia en Français

  • Steiner — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sommaire 1 Patronyme 2 Éducation 3 …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Jakob Steiner — Pour les articles homonymes, voir Steiner. Jakob Steiner Naissance 18 mars 1796 …   Wikipédia en Français

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • 21 problemes NP-complets de Karp — 21 problèmes NP complets de Karp Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”