シュタイナー木
出典: フリー百科事典『ウィキペディア(Wikipedia)』
印刷用ページはサポート対象外です。表示エラーが発生する可能性があります。ブラウザーのブックマークを更新し、印刷にはブラウザーの印刷機能を使用してください。
この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月)
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
- 英語版記事を日本語へ機械翻訳したバージョン(Google翻訳)。
- 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
- 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
- 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
- 翻訳後、
{{翻訳告知|en|Steiner tree problem|...}}をノートに追加することもできます。 - Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
シュタイナー木(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).