向圖的所有邊添加權重 - 生成樹中的變化和最短路徑

Question

（a）設T是加權圖G的最小生成樹。通過向每個圖像添加權重k構造新圖G G的邊緣。T的邊緣 構成G的最小生成樹。證明語句或給出 反例。 （b）令P = {s，...，（）。 。 。 ，t}描述了加權圖G的 個頂點s和t之間的最短加權路徑。通過 構建新的圖G，將權重k添加到G的每個邊.P是否描述了從s到t的最短路徑 G.證明陳述或舉一個反例。

我的解決辦法：

一個）筆的邊緣仍然形成的G的最小生成樹，因爲所有的邊緣權重增加了相同的量。

b）p還描述了從最短的路徑在G（同樣的原因）到T

可有人請覈實答案？

Answer 1

儘管我不認爲SO是你問題的最佳位置，但你對問題B的回答肯定是錯誤的。

考慮具有3個頂點（A，B，C），具有以下邊的圖：

A-B = 1 
A-C = 0 
C-B = 0 

甲乙之間的最短路徑的加權是A-C-B。如果你給所有權重加2，你的最短路徑變成A-B。

（對不起，錯過了問題的第一部分，有一個答案已經通過了。之所以a是正確的，但b是錯誤的是，生成樹總是恰好包含n-1邊緣，而邊緣的數在最短加權路徑中可能會有所不同。）

Answer 2

a）正確。因爲每個MST的成本增加了（n-1）* k。

b）錯誤。考慮圖3點的頂點和邊： 1-2：3 2-3：3 1-3：10 現在從1最短路徑做3經過2 現在加上10，如果每個邊緣成本。現在最短路徑直接從1到3.