12

グラフ理論を勉強していますが、最小全域木と最短経路木の関係について質問があります。

Gを、すべてのエッジが異なるコストで重み付けされている無向の連結グラフとします。TをGのMSTとし、T sをあるノードs の最短経路ツリーとする。TとTは、少なくとも 1 つのエッジを共有することが保証されていますか?

これは常に正しいとは限りませんが、反例を見つけることができません。反例を見つける方法について誰か提案がありますか?

4

2 に答える 2

6

このステートメントは実際にtrueだと思うので、反例を見つけることができるとは思えません。

ここにヒントがあります - グラフ内の任意のノードを取り、そのノードの最短パス ツリーを見つけます。ここで、そのノードから始まるPrim のアルゴリズムを実行するとどうなるかを考えてみましょう。MSTからの少なくとも 1 つのエッジが最短パス ツリーへの道を見つけることを保証できますか?

お役に立てれば！

于 2013-06-13T17:55:10.147 に答える
3

証明頂点sとその最短経路木T sに対して、MST Tのウェッジは w( s , v ) であり、それがT sに存在しないと仮定します。次に、 vからsへのより短いパスが必要であり、パスに頂点があり ( w( s , v ) は最短パスではないため)、これはpであると想定され、s -> p -> vになります, w( s , v ) >= パス( s -> p -> v）。w( s , v ) を削除し、 Tにw( s , p )を追加します。すべてのエッジが正であり、 w( s , p ) < w( s , v ) の場合です。より少ない最小全域木T ' を取得します。

しかし、Tは MST です。ここに矛盾があります。TとT sが少なくとも 1 つのエッジを共有する必要があることを証明する仮定は成り立たず、MST Tでは w( s , v )です。

コストが 0 の重みがある場合も同様です。w(a,b) = 0 の 2 つの頂点を同じ頂点と見なし、そのうちの 1 つを削除できます。この証明は、重みが負でない場合に機能します。

一部の重みが負で、w( s , p ) > w( s , v ) の場合、つまり w( p , v ) <0, w( s , v ) >= path( s -> p -> v ) w ( s , p ) < w( s , v )は作成できません。しかし、MST Tではw( s , v )も存在しないはずです。より少ないコストで、w( sを置き換えます, v ) in T with w( s , p ) および w( p , v ) は、必要に応じて aa を最小スパニング ツリーT ' より小さくします。やはり矛盾。

于 2013-06-14T01:53:30.490 に答える