fc2ブログ



最小全域木

2006.04.26 22:52  グラフ 最小全域木

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

isTree.gif

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

ST.gif

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

MST.gif


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



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ