全域木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/10 01:42 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2012年7月) |
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
グラフ理論において、グラフの全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（連結で閉路を持たないグラフ）であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。
最小全域木
各辺に重み（コスト）がある場合、最小の総和コストで構成される全域木を最小全域木という。
| 非線形（無制約） |
|  | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 非線形（制約付き） |
| |||||||||||||
| 凸最適化 |
| |||||||||||||
| 組合せ最適化 |
| |||||||||||||
| メタヒューリスティクス | ||||||||||||||
| 典拠管理データベース: 国立図書館 |
|---|
全域木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)
重み付き連結グラフ P {\displaystyle P} があり、クラスカル法で生成した P {\displaystyle P} の部分グラフを Y {\displaystyle Y} とする。常に異なる2つの木を連結する辺を加えているので、 Y {\displaystyle Y} には閉路がない。また、 Y {\displaystyle Y} の2つの部分を連結する辺を全て選んでいるので、全頂点は連結されている。したがって Y {\displaystyle Y} は P {\displaystyle P} の全域木である。
※この「全域木」の解説は、「クラスカル法」の解説の一部です。
「全域木」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。
ウィキペディア小見出し辞書の「全域 - 木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 全域 - 木のページへのリンク
