(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.
My solution:
a) Edges of T still form minimum spanning tree of G, since all edge weights are increased by same amount.
b) P still describes shortest path from s to t in G (same reason)
Can someone please verify the answers?
Although I don't think SO is the best place for your question, your answer to question B is definitely wrong.
Consider a graph with 3 vertices (A,B,C), with the following edges:
A-B = 1
A-C = 0
C-B = 0
The shortest weighted path between A and B is A-C-B. If you add 2 to all the weights, your shortest path becomes A-B.
(Sorry, missed the first part of the question, there is an answer for that already by now. The reason why a
is correct but b
is wrong is that spanning trees always contain exactly n-1
edges, while the number of edges in a shortest weighted path may vary.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With