全域木
正式名称
Spanning Tree（スパニングツリー）
一言でいうと
元のグラフの全頂点を残して作る木
初心者向け説明
全域木とは、連結グラフから一部の辺を取り除き、
- すべての頂点を残す
- すべての頂点をつなぐ
- 閉路をなくす
ように作った木です。
例えば、
A ----- B
| |
C ----- D
から辺を1本取り除いて、
A ----- B
|
C ----- D
とすれば全域木になります。
ポイント
- 元のグラフのすべての頂点を含む
- 木なので閉路を持たない
- 頂点数がnなら辺はn−1本
関連用語
関連記事
- グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう
🍯 はちみつメモ
全域木 = 全頂点を残し、閉路をなくして作った木