Consider a graph G=(V,E), its corresponding minimum spanning tree T, and some ed

Question

Consider a graph G=(V,E), its corresponding minimum spanning tree T, and some edge (u,v) that is in G but not in T. If the weight of (u,v) is decreased to produce a new graph G' such that T is not an MST for G', describe which edge in T you would replace to form an MST for G'. (Think about why (u,v) is not in T. What does that say about the reachability of nodes u and v in G?) Provide a general strategy for finding the edge to replace without again applying an MST algorithm. Describe your reasoning behind this approach.

Explanation / Answer

There are 2 possible reasons for the edge <u,v> not to be in the MST T:

1. The edge forms a cycle when added to the MST

2. The weight of the edge is higher than all other edges that forms the MST

If the edge <u,v> is not in the MST, there must be some other edges that connects nodes u and v to the MST. Hence, u and v are reachable from every other node in G.

To add the edge <u,v>, first add the edge to the existing MST and then check for any cycle. If it exists, remove the edge with the highest weight to break the cycle. If no cycle exists, remove the edge with the highest weight that does not disconnect the MST.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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