(a) T を加重グラフ G の最小全域木とする. G のすべての辺に k の加重を追加することによって新しいグラフ G を構築する. T の辺は G の最小全域木を形成する. ステートメントまたは反例を出します。
(b) P = {s, . . . , t} は、加重グラフ G の頂点 s と t の間の最短加重経路を記述します。G のすべてのエッジに k の加重を追加することによって、新しいグラフ G を作成します。P は、G 内の s から t への最短経路を記述しますか?ステートメントまたは反例を与えます。
私の解決策：
a) すべてのエッジの重みが同じ量だけ増加するため、T のエッジは G の最小スパニング ツリーを形成します。
b) P は G で s から t への最短経路を記述します (同じ理由)
誰かが答えを確認できますか？
SO があなたの質問に最適な場所だとは思いませんが、質問 B に対するあなたの答えは間違いなく間違っています。
次のエッジを持つ 3 つの頂点 (A、B、C) を持つグラフを考えてみましょう。
A-B = 1
A-C = 0
C-B = 0
A と B の間の最短の加重パスは ACB です。すべての重みに 2 を加えると、最短経路は AB になります。
a（申し訳ありませんが、質問の最初の部分を見逃してしまいました。その答えはもうすでに出ています。正しいがb間違っている理由は、スパニング ツリーには常に正確なn-1エッジが含まれるのに対し、最短の重み付けされたパスのエッジの数はさまざまである可能性があるためです。 .)
a) 正しい。すべての MST のコストが (n-1)*k だけ増加するためです。
b) 間違っています。3 つの頂点とエッジを持つグラフを考えてみましょう: 1-2: 3 2-3: 3 1-3: 10 1 から 3 への最短パスは 2 を通過します。すべてのエッジの場合、コストに 10 を追加します。これで、最短経路は 1 から 3 に直接進みます。