(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边,而最短加权路径中的边数可能会有所不同.)