|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。特に、エッジが重みづけされたグラフGにおいて、Tのシュタイナー木を構成するエッジの重みの総和が最も小さいシュタイナー木のことを最小シュタイナー木（Minimum Steiner tree）と呼ぶ。最小シュタイナー木を求める問題はシュタイナー問題、 最短連結問題、最短ネットワーク問題などと呼ばれ、NP困難であることが知られている。最小シュタイナー木問題を解くアルゴリズムを「シュタイナー木アルゴリズム」と呼ぶ。シュタイナー木アルゴリズムの一例として、Dreyfus–Wagner法〔S. Dreyfus, R. Wagner, “The Steiner problem in graphs,” Networks 1, pp.195-207, (1972).〕などがある。 == 脚注 == 〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「シュタイナー木」の詳細全文を読む スポンサード リンク
|