最小全域木

Tree
木 (tree)とは、閉路をもたないグラフのことを言います。以下に例を示します。下図の左のグラフは、例えば、0 → 3 → 1 → 0 のような閉路をもつので、木ではありません。一方、残りの２つは、閉路をもたないグラフなので木です。 あるノード r から v まで、必ず１通りの path があります。



Spanning Tree
グラフ G(V, E) の極大木（spanning tree）G(V', E') とは、グラフの全ての頂点 V を含む部分グラフであって（V = V'）、木である限りできるだけ多くのエッジを持つものをいいます。グラフの極大木は、DFS または BFS で求めることができます。グラフの極大木は１つとは限りません。以下に、与えられたグラフの極大木の例を示します。



Minimum Spanning Tree
最小極大木 (minimum spanning tree)とは、与えられたグラフの極大木の中で、エッジの重みの総和が最小のものをいいます。以下に、与えられたグラフの最小極大木の例を示します。




最小極大木を求めることは、現実問題で非常に重要になり、多くの応用をもちます。例えば、グラフ G の各ノード u を都市とし、各エッジ (u, v) の重みを都市 u から都市 v への高速道路を建設する費用とすれば、G の最小全域木は、すべての都市を結ぶ高速道路網を可能な限り最小の費用で建設する解となります。