We know that adding some constant value to each edge weight might change the set

Question

We know that adding some constant value to each edge weight might change the set of shortest paths in a graph. Prove that this is not true for minimum spanning trees. That is, prove that, for all integers c, the set of minimum spanning trees of weighted graph G is is the same as the set of minimum spanning trees of G where each of the edge weights have been increased by c.

NOTE: The answer does not need to be coded in any language or pseudocode, just give a step-by-step algorithm in english of how to achieve this so that I may be able to understand it.

Explanation / Answer

No, the minimum spanning tree does not change. To see this, lets run Kruskal's algorithm to find the MST. Because there are distinct edge weights(and they remain distinct after being increased by 1), there is exactly one MST.
Kruskal's algorithm will consider the edges in the same order, because we increased all of the edge weights by the same amount. We have the same graph structure, so Kruskal's algorithm will add the same edges to the MST. We proved
in class that Kruskal's algorithm is correct, so, therefore, the MST cannot change.
Therefore the shortest path will remain the same in the modified MST.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.