9

(任意の) 接続された無向グラフ G があり、そのエッジが異なる重みを持つ場合、

  1. G のすべての MST には最小の加重エッジが含まれていますか?
  2. 最大加重エッジを含まない G の MST はありますか?

また、このような MST の質問に対処する際に心に留めておく必要がある重要な事柄について、誰かがヒントを与えることができれば、さらに感謝しています。

これは宿題の問題です。ありがとう。

4

4 に答える 4

8

最大加重エッジを含まない G の MST はありますか?

あるかもしれませんが、ある必要はありません。次のような 4 頂点グラフを考えてみましょう。

[A]--{2}--[B]
 |         |
 |         |
{1}       {3}
 |         |
 |         |
[C]-{50}--[D]

最小スパニング ツリーは、エッジ セット {CA、AB、BD} で構成されます。{CD} 沿いの最大エッジ ウェイトは 50 ですが、MST の一部ではありません。しかし、G がすでにそれ自身の MST に等しい場合、明らかにそれ自身の最大エッジが含まれます。

G のすべての MST には最小の加重エッジが含まれていますか?

はい。MST にはカット特性があります。カットとは、グラフの頂点を 2 つの互いに素な集合に分割することです。作成できる任意のカットについて、そのカット内のエッジの重みがカット内の他のエッジの重みよりも小さい場合、このエッジはグラフ内のすべての MST に属します。エッジの重みが異なることが保証されているため、他のすべてのエッジよりも小さいエッジがあることも保証されています。

また、このような MST の質問に対処する際に心に留めておかなければならない重要な点について、誰かがヒントを与えることができれば、さらに感謝しています。

あなたの最善の策は、一般的な MST の特性を使用して物事について推論し、あなたの主張を証明すると思われる特定の反例を構築しようとすることです。上記の推論の各行の例を挙げました。カットとサイクルのプロパティにより、どのエッジが MST にあるかを常に正確に判断できるため、各エッジを体系的にテストして、MST にあるかどうかを判断できます。

于 2010-04-11T12:42:13.530 に答える
6

G のすべての MST には最小の重み付きエッジが含まれていますか?

はい。MST最小重みエッジを含まない があると仮定しましょう。このエッジを に含めると、 にMSTなりcycleます。これで、サイクルを削除してグラフ ( ) の接続cycleを維持するために削除できる別のエッジが常に存在します。MST

最大加重エッジを含まない G の MST はありますか?

グラフによります。graphそれ自体がツリーである場合、そのすべてのn-1エッジを に含める必要がMSTあるため、最大重みエッジを除外することはできません。また、最大重みエッジがcut-edge除外されても接続が発生しないように、最大​​重みエッジを除外することはできません。ただし、最大重みエッジが の一部であるcycle場合、 から除外することができMSTます。

于 2010-04-11T12:44:46.020 に答える
0

あなたも2009年のテストを通してCSC263の勉強をしているのですね。（こっちも一緒！）

最小値が常に MST にあることを確認する別の方法は、この最小エッジ (e と呼びます) を単純に調べることです。

          e 
v1 ---------------- v2

(これには他の頂点への接続があると仮定します)。ここで、最終的な MST に e NOT が含まれるということは、一般性を失うことなく、ある時点で MST に v1 があり、v2 がないことを意味します。ただし、e を追加せずに v2 を追加する唯一の方法は、v1 を追加しても e がキューに追加されなかったということです (定義上、優先度が最も低い e はキューの先頭にあるため)。 MST 構成定理に矛盾します。

したがって、基本的に、重みが最小のエッジをキューに到達させないことは不可能です。つまり、構築された MST はそれを持ちます。

于 2010-04-12T13:16:49.540 に答える
0

最初の質問に対する答えはノーで、クルスカルのアルゴリズムがそれを証明しています。常に最小コスト エッジが選択されます。

2 番目の質問の答えは「はい」です。グラフの例を見つけるのは簡単です。

1 - 2 (cost 10)
2 - 3 (cost 100)
3 - 1 (cost 1000)

3 番目のエッジはサイクルを導入するため、選択されることはありません。基本的に、最大コストのエッジが MST に挿入された場合にサイクルが作成される場合は、挿入されません。

于 2010-04-11T12:43:50.550 に答える