给图中所有边添加权重 - 对生成树和最短路径的影响

Question

（a）假设T是加权图G的最小生成树。构建一个新图G，将G的每条边的权重增加k。那么，T的边是否形成了G的最小生成树？请证明该陈述或举出反例。

（b）假设P={s,...,t}描述了加权图G中顶点s和t之间的最短路径。构建一个新图G，将G的每条边的权重增加k。那么，在G中，P是否描述了从s到t的最短路径？请证明该陈述或举出反例。

我的解决方案：

a) T的边仍形成G的最小生成树，因为所有边的权重都增加了相同的量。

b) P仍然描述了G中从s到t的最短路径（原因相同）

请有人验证答案吗？

- Jake

---

“viewed 3317 times” 的意思是“已被查看3317次”。我不明白为什么这句话被认为是“不太可能对任何未来的访问者有帮助”。 - User

Answer 1

尽管我认为SO不是您提问的最佳场所，但您对问题B的回答绝对是错误的。

考虑一个具有3个顶点（A,B,C）和以下边的图：

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

从A到B的最短加权路径是A-C-B。如果您将所有权重加2，则最短路径变为A-B。

（抱歉，错过了问题的第一部分，现在已经有了答案。 a 正确而 b 错误的原因是生成树总是包含恰好 n-1 条边，而最短加权路径中的边数可能会有所不同。）

- biziclop

Answer 2

a) 正确。因为每个最小生成树的成本都会增加 (n-1)*k。

b) 错误。考虑有3个顶点和边的图形： 1-2: 3 2-3: 3 1-3: 10 现在从1到3的最短路径经过2。 现在如果每条边都加上10，则最短路径直接从1到3。

- usamec