(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。