全域木と最小全域木

全域木とは

あるグラフがあったとき、そのグラフの全ての頂点といくつかの辺を使って作られた新たなグラフが連結で閉路を持たないとき、新たなグラフを元のグラフの全域木という。

最小全域木

辺がコストを持つとき、コストの総和が最小の全域木を最小全域木という。

アルゴリズムとして クラスカル法 などがある。