全域木
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2012年7月) |
![]() | この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|


グラフ理論において、グラフの全域木(ぜんいきぎ、英: Spanning tree)、極大木(きょくだいき)、スパニング木、スパニングツリーとは、全域部分グラフ(そのグラフの全頂点を含む部分グラフ)のうち、木(連結で閉路を持たないグラフ)であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。
最小全域木
各辺に重み(コスト)がある場合、最小の総和コストで構成される全域木を最小全域木という。
- 最小全域木問題のページへのリンク