17

ここに演習があります：

以下を証明するか、反例を挙げてください。

(a) 無向グラフの最小全域木における頂点のペア間のパスは、必ずしも最短 (最小重み) パスですか?

(b) グラフの最小全域木が一意であるとします。無向グラフの最小全域木における頂点のペア間のパスは、必ずしも最短 (最小重み) パスですか?

私の答えは

(a)

いいえ、たとえば、グラフ 0、1、2、0-1 は 4、1-2 は 2、2-0 は 5、0-2 の真の最短パスは 5 ですが、mst は 0-1-2 です。 、mst で、0-2 は 6

(ロ)

私の問題はこれにあります（b）。

whether the MST is unique最短経路にどのように影響するかわかりません。

まず、私の理解では、エッジの重みが明確でない場合、複数の MST が同時に存在する可能性がありますよね?

第 2 に、MST が一意であっても、上記の (a) の答えは (b) にも当てはまりますよね?

4

4 に答える 4

25

それでは、非常に単純なグラフを見てみましょう。

(A)---2----(B)----2---(C)
 \                    /
  ---------3----------

このグラフの最小スパニング ツリーは、2 つのエッジA-Bとで構成されB-Cます。最小全域木を形成するエッジのセットは他にありません。

Aしかしもちろん、 からへの最短経路CはA-Cであり、MST には存在しません。

編集

したがって、パート (b) に答えるには、MST にはない短いパスが存在するため、答えはノーです。

于 2012-05-04T12:09:40.620 に答える
6

(a)については同意します。

(b) については、グラフによっては同じ重みを持つ最小全域木が多くなる場合があります。頂点 a、b、c を持つ円 C3 を考えてみましょう。重み a->b=1、b->c=2、a->c=2。このグラフには、{abc} と {cab} の 2 つの MST があります。

それにもかかわらず、MSTはそこで一意であるため、反例は依然として有効です。

于 2012-05-04T12:16:31.797 に答える
0

MST は開始ノードに関連していませんか?!
次に、MST 開始ノードからの最短パスを取得しようとしています。したがって、はい、最短パスはA!から始まる MST によって指定されます。

于 2014-02-03T18:32:08.427 に答える