2

コーメンなどの最小全域木について読んでいます。以下は、一般的な最小スパニングツリーです。

重み関数w：E->Rを持つ接続された無向グラフG=（V、E）があり、Gの最小全域木を見つけたいと仮定します。ここでは欲張りアプローチを使用します。この欲張り戦略は、次の「一般的な」アルゴリズムによってキャプチャされます。このアルゴリズムは、最小スパニングツリーを一度に1つのエッジで成長させます。アルゴリズムはエッジAのセットを管理し、次のループ不変条件を維持します。

各反復の前に、Aはいくつかの最小全域木のサブセットです。

GENERIC-MST(G,w) 
A = NULL
while A is not a spanning tree 
  do find an edge (u, v) that is safe for A 
  A = A ∪ {(u, v)}
end while

return A

質問

  1. 「A」が最小全域木のサブセットであるという不変条件でのauthoreの意味は何ですか？この声明の「いくつか」とは何ですか？MSTは1つだけだと教えました。

  2. 上記の擬似コードで、作成者は「Aはスパニングツリーではない」とはどういう意味ですか？つまり、whileループがいつどのように終了するのでしょうか。

  3. 「いくつかの」最小スパニングツリーがある擬似コードでは、ここでの私の理解は1つだけです。私は正しいですか？

誰かが小さな例で説明できますか？

ありがとう！

4

4 に答える 4

4

1.絶対にありません。MSTは必ずしも一意ではありません。例えば：

すべてのエッジの重みは同じです。

u --- v
|     |
|     |
w --- x

上のグラフには、エッジを削除することにより、4つのMSTがあります。

2.のスパニングツリーT = (V,e)は次G = (V,E)のようなものです|e| = |V|-1

3.いいえ。

于 2011-11-16T12:22:02.970 に答える
1

  1. これは誤りです。2つのエッジだけが等しい場合でも、グラフには多くのMSTが含まれる場合があります。

  2. 次の理由により、 Aは最小スパニングツリーではありません。

    2.1まず第一に、Aはツリーではありません-それは切断されています。

    2.2グラフにまたがらない

    上記の条件が満たされると、ループは終了します

  3. 多くあるので、それはいくつかのMSTにあると言うのは正しいです。

于 2016-05-30T08:32:30.367 に答える
0
  1. グラフのスパニングツリーが一意であると言うとき、あなたは正しいです。ただし、これは、グラフのすべてのエッジの長さが異なる場合です。上記の回答で説明したように、エッジの長さが等しいグラフは、多くの異なるスパニングツリーを持つことができます（もちろん、それらはすべて同じ総重みを持ちます）。
  2. whileループは、グラフのすべての頂点をスパニングツリーに含めたときに存在します。このために、whileループにチェックを追加します。
于 2013-01-13T10:42:51.630 に答える
0

  1. @davinによると正しくありません

  2. アルゴリズムは、フォレストがあるという不変条件を維持しますが、十分なエッジを追加するまで、フォレストはグラフにまたがりません。したがって、安全でなくなるまでエッジを追加し続ける必要があります（その時点でループが壊れます）。

  3. 1を参照してください。

于 2013-09-26T19:09:36.423 に答える