最小全域木

木(tree)とは閉路を持たないグラフをいう。下図(a)は閉路を持つので木ではない。下図(b)は閉路を持たないので木である。

木の例

全域木

全域木(spanning tree)とは、グラフ \(G=(V,E)\) の全ての頂点 \(V\) と、そのグラフを構成する辺の一部分のみで構成される木のことをいう。下図のように、\(1\) つのグラフに対して、いくつかの全域木がある場合もある。

グラフと全域木

最小全域木

最小全域木(Minimun Spanning Tree)とは、グラフの全域木の中で、辺の重みの総和が最小のものをいう。

最小全域木

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」294〜295頁