シュタイナー木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/24 19:08 UTC 版)
シュタイナー木（Steiner tree）とは、辺の集合Eと頂点の集合Vから成る無向グラフG=(V,E)と、ターミナルと呼ばれるVの部分集合Tが与えられたとき、Tの全ての頂点を連結する木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。特に、辺が重みづけされたグラフGにおいて、Tのシュタイナー木を構成する辺の重みの総和が最も小さいシュタイナー木のことを最小シュタイナー木（Minimum Steiner tree）と呼ぶ。最小シュタイナー木を求める問題はシュタイナー問題、 最短連結問題、最短ネットワーク問題などと呼ばれ、NP困難であることが知られている。最小シュタイナー木問題を解くアルゴリズムを「シュタイナー木アルゴリズム」と呼ぶ。シュタイナー木アルゴリズムの一例として、Dreyfus–Wagner法[1]などがある。
- ^ S. Dreyfus, R. Wagner, “The Steiner problem in graphs,” Networks 1, pp.195-207, (1972).
[続きの解説]
「シュタイナー木」の続きの解説一覧
- 1 シュタイナー木とは
- 2 シュタイナー木の概要
- 3 関連項目
- シュタイナー木のページへのリンク
