最小全域木

無向連結グラフの全域木は、グラフが連結であるという条件を保ったまま辺を消去して得られる木のことです。 最小全域木は、全域木を構成する辺のコストの総和が最小となるもののことを指します。 最小全域木問題は、与えられたグラフの最小全域木またはそのコストを求める問題です。