<分区>
(a) Let T be a minimum spanning tree of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree of G. Prove the statement or give a counterexample.
(b) Let P = {s, . . . , t} describe a shortest weighted path between vertices s and t of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Does P describe a shortest path from s to t in G. Prove the statement or give a counterexample.
我的解决方案:
a) T 的边仍然形成 G 的最小生成树，因为所有边的权重都增加了相同的量。
b) P仍然描述了G中s到t的最短路径(同理)
有人可以验证答案吗？