2

私はいくつかの真/偽の質問を終わらせようとしています。それらの多くに true で答えると不安になります...すべてのグラフは無向であり、明確な重みを持たないと仮定してください。負の重みは問題ないはずです。

Qa) G に一意の最も重いエッジ e を持つサイクルがある場合、e は MST の一部になることはできません。

私の答えは本当です。たとえば、ノード A、B、C、D、E を持つグラフがあります。

AB = 1
BC = 2
BD = 3
CD = 100
DE = 4

ご覧のとおり、BCD はサイクルです。私の主張は、これはサイクルであるため、他のルートを利用することで、唯一の最も重いエッジ CD を常に回避できるということです。したがって、それは本当です。私の議論は（十分に）正しいですか？

Qb) ダイクストラのアルゴリズムによって計算された最短パス ツリーは、必然的に MST です。

私の答えは正しいですが、私の本能は何かがおかしいと教えてくれます。ええと... Disjkstra と Prim はどちらも貪欲なアルゴリズムです。どちらも常に最も軽量なエッジを使用します。最短経路木が最小全域木でない場合はありますか? 実は、この二人の違いを理解するのに苦労しています。

Qc) Prim のアルゴリズムは、負の加重エッジで機能します。

私の答えは本当です。それがウィキが言ったことだから... :p アルゴリズムは、すべてのエッジの中で最低コストのエッジを見つけることです。では、負の加重エッジは問題にならないはずですよね? しかし、負の加重サイクルはどうでしょうか?

Qd) G に一意の最軽量エッジ e を持つサイクルがある場合、e はすべての MST の一部でなければなりません。

私の答えは本当です。MST 内のすべてのノードにアクセスする必要があります。たとえば、長さ 3 のサイクルでは、そのサイクル内のすべてのノードを常に 2 ステップでトラバースできます。独自の最も軽いエッジがあれば、MST で間違いなくそれを選択します。

私の主張は正しいですか？おそらくそれらは不十分ですか？何か提案はありますか？

4

2 に答える 2

5

b) の提案: あなたの本能はそれが間違っていると言っているので、反例を構築してみてください。見つけた場合は解決済みです。そうでない場合は、反例の構成が失敗した理由を分析することで、主張が正しい理由を確認できることがよくあります。ただし、あなたの答えや本能が正しいかどうかはわかりません。

宿題は確かにずっと前に期限が切れているので、答えは次のとおりです。

Qa) G に一意の最も重いエッジ e を持つサイクルがある場合、e は MST の一部になることはできません。

真実。Tedge を含むスパニング ツリーがあるとしますe。ツリーからエッジを削除するeと、2 つの空でない連結要素 C1 と C2 を含むグラフが得られます。サイクル内の他のエッジの少なくとも 1 つは、C1 と C2 を接続する必要があります (そうでない場合、サイクルにはなりません)。gそのようなエッジになりましょう。からを削除および追加してT'得られるツリーは、 より重みの小さいスパニング ツリーです。したがって、MST ではありませんでした。TegTT

Qb) ダイクストラのアルゴリズムによって計算された最短パス ツリーは、必然的に MST です。

私の答えは正しいのですが、私の本能が何かがおかしいと教えてくれます。

本能は正しかった、それは誤りだ。検討

    6
  A---B
3 |   | 1
  C---D
    3

ここで、最短パス ツリーは頂点から計算されAます。最短経路木は

    6
  A---B
3 |
  C---D
    3

総重量は 12 ですが、独自の MST は

  A   B
3 |   | 1
  C---D
    3

重量7で。

Qc) Prim のアルゴリズムは、負の加重エッジで機能します。

真実。W正の重みの正しさからそれを推測する 1 つの方法は、すべてのエッジの重みが正になるように、すべてのエッジに一定の重みを追加することです (例: W = 1 + max { |weight(e)| : e ∈ E })。

頂点を持つツリーにはV常にV - 1エッジがあるため、スパニング ツリーの重みの合計は(V - 1)*W、変更された重みと変更されていない重みの間で異なります。そのため、ツリーが変更されていないエッジの重みの MST である場合にのみ、ツリーは変更された重みの MST になります。

重みによるエッジの順序は、すべての重みに定数を追加しても変更されないため、Prim のアルゴリズムは、変更されていない重みと同じ順序で、変更されたエッジの重みに対して同じスパニング ツリーを構築します。

正の重みの正確さにより、Prim のアルゴリズムによって修正された重みで構築されたツリーは、修正された重みの MST になります。

Qd) G に一意の最軽量エッジ e を持つサイクルがある場合、e はすべての MST の一部でなければなりません。

間違い。検討

     1   1
   A---B---C
   |  / \  |
 1 | /4 5\ | 1
   |/  6  \|
   D-------E

サイクルBDEには重み 4 の一意の最も軽いエッジBDがありますが、MST にはそのサイクルのエッジが含まれていません。

e ただし、グラフGに一意の最も明るいエッジがある場合、それはすべての MST の一部である必要があります。それは a) と双対です: を含まないのスパニング ツリーTを考えてみましょう。に追加することにより、循環を持たなければならないグラフが得られます (はスパニング ツリーであり、 ではありません)。のすべてのサイクルには が含まれている必要があります。そうでない場合は、 のサイクルになります。したがって、任意のサイクルを選択し(1 つだけありますが、それは重要ではありません)、 from以外のエッジをすべて削除します。結果のグラフを とします。GeeTT'TeTT'eTCT'eCT''

総重み otT''は のそれよりも小さいですT。なぜなら、はエッジをより軽いエッジに置き換えることによってT''得られるからです。は接続されており (サイクルのエッジを削除して から取得されたため)、頂点とエッジが含まれています。したがって、これはスパニング ツリーであり、最小ではありませんでした。TT''T'VV - 1T

于 2011-10-29T12:15:50.500 に答える
0

D は真です。
Qd) G に一意の最軽量エッジ e を持つサイクルがある場合、e はすべての MST の一部でなければなりません。真実。

ライト エッジ = カットを横切るエッジで、その重みがカットを横切るエッジの最小値です。

ここで、T を G の MST とします。(矛盾を避けるために) T' は G の異なる MST であると仮定します。T と T' は同じツリーではなく、両方とも |V|–1 のエッジを持つため、 T' にない T のエッジ e。T からエッジ e を削除すると、G のカットが誘導 (作成) されます。T はスパニング ツリーであるため、e を削除すると、G が 2 つのばらばらな頂点のセットに分割されます。これらのセットには、G のすべての頂点が含まれます。これがまさにカットです。ここで、T は MST であるため、エッジ e はそのカットの (一意の) 明るいエッジでなければならず、したがってすべての MST に存在します。しかし、構造上、エッジ e は T' にありません。したがって、T' は MST ではなく、元の仮定と矛盾します。

于 2012-10-18T07:41:11.603 に答える