全域木とは何？ わかりやすく解説 Weblio辞書 (original) (raw)

全域木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/07 01:31 UTC 版)

4×4のグリッドグラフにおける全域木の一例

8x8 グリッド グラフ上の 3 つの例

グラフ理論において、グラフの全域木（ぜんいきぎ、英: 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} の全域木である。

※この「全域木」の解説は、「クラスカル法」の解説の一部です。
「全域木」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。

ウィキペディア小見出し辞書の「全域木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。

• 全域木のページへのリンク