全域木・最小全域木とは

全域木(Spanning tree)とは

グラフG = (V,E)の全域木G = (V',E')とは、
グラフの全ての頂点Vを含む部分グラフであり(V = V')、木である限りできるだけ多くの辺を持つものをいう。 グラフの全域木は、深さ優先探索や幅優先探索で求めることができますが、求める全域木は一つになるとは 限らず、探索方法により変化します。

最小全域木(Minimum Spanning Tree)とは

グラフの全域木の中で辺の重みの総和が最小のもののこと

参考