CODEWITHSUNDEEP
algorithmgraphgraph-algorithmminimum-spanning-tree
user8756425
user8756425

Reputation: 31

Weight change for an MST algorithm

enter image description here

Given the graph above and edge weights, if we increase the weight of edge A-B by 10.5, it would be no longer in MST.

If we increase by 7.5 or 4.5 or 1.5 - it would still be. Why? I am trying to solve these problems on my own.

Thank you.

Upvotes: 1

Views: 867

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59194

Kruskal's algorithm, with its proof of correctness, implies that an edge must be in the MST if its endpoints cannot be connected with other edges of equal or lesser weight, and that it must NOT be in the MST if it's endpoints can be connected with other edges of lesser weight.

Without using edge A-B, a path between the endpoints with the smallest maximum weight is A-E-G-B, with max weight 8. So if A-B has a cost less than 8, it will be in the MST. If it has a cost greater than 8, it will not.

Note that you are incorrect when you say that A-B would still be in the MST if you increase its cost by 7.5. It's new cost would then be 8.5, and it would not be included. Your probably meant to say that it would still be in the tree if you increase its cost to 7.5.

Upvotes: 1

Related Questions