シュタイナー木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

シュタイナー木(Steiner tree)とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。特に、エッジが重みづけされたグラフGにおいて、Tのシュタイナー木を構成するエッジの重みの総和が最も小さいシュタイナー木のことを最小シュタイナー木(Minimum Steiner tree)と呼ぶ。最小シュタイナー木を求める問題は「最小シュタイナー木問題」、または「シュタイナー木問題」と呼ばれ、NP困難であることが知られている。最小シュタイナー木問題を解くアルゴリズムを「シュタイナー木アルゴリズム」と呼ぶ。シュタイナー木アルゴリズムの一例として、Dreyfus–Wagner法[1]などがある。

脚注[編集]

  1. ^ S. Dreyfus, R. Wagner, “The Steiner problem in graphs,” Networks 1, pp.195-207, (1972).

関連項目[編集]