ある地域に、次のグラフで示すようなネットワークを組みたいとしましょう。辺を通じて、情報や電気などが伝わるとします。 通信網の建設には、ある程度のコストがかかるとします。そこで、全頂点がつながったまま、全体がつながるような辺の残し方はできないでしょうか。つまり、頂点を保ったままサイクルを持たない連結なグラフ（木）を求める問題、これが全域木の問題です。 \(G=(V,E)\)を抽象グラフとします。\(E^{\prime }\subset E\)として、\(G^{\prime}=(V,E^{\prime})\)が木となるとき、\(G^{\prime}\)をグラフ\(G\)の全域木（spanning tree）と呼びます。スパニング木とも。spanは数学では生成するという意味を持つので、グラフを生成する木、生成木と呼びたいですね。 例えば、さきほどのグラフから点線で表した辺を除けば、サイクルを持た