全域木
(最小全域木問題 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/19 14:48 UTC 版)
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2012年7月)
|
|
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
グラフ理論において、グラフの全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（連結で閉路を持たないグラフ）であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。
最小全域木
各辺に重み（コスト）がある場合、最小の総和コストで構成される全域木を最小全域木という。
|
|
||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 非線形（無制約） |
|
|
||||||||||||
| 非線形（制約付き） |
|
|||||||||||||
| 凸最適化 |
|
|||||||||||||
| 組合せ最適化 |
|
|||||||||||||
| メタヒューリスティクス | ||||||||||||||
| 典拠管理データベース: 国立図書館 |
|---|
- 最小全域木問題のページへのリンク
