[CLRS 23.1-11] Given a graph $G$ and a minimum spanning tree $T$, suppose that we decrease the
weight of one of the edges not in $T$. Give an algorithm for finding the minimum
spanning tree in the modified graph.
Well, this one is dependent upon 23.1-5 , which states that there is always an MST that doesn't include the maximum weight edge of a cycle of a graph. Now, let's add the edge whose weight was decreased (say $E_0$) to $T$. This will, obviously make a cycle. Now, we check for the maximum weight edge in the graph thus formed, and remove it (it might be $E_0$ too). The tree thus formed is the MST of the graph.
weight of one of the edges not in $T$. Give an algorithm for finding the minimum
spanning tree in the modified graph.
Well, this one is dependent upon 23.1-5 , which states that there is always an MST that doesn't include the maximum weight edge of a cycle of a graph. Now, let's add the edge whose weight was decreased (say $E_0$) to $T$. This will, obviously make a cycle. Now, we check for the maximum weight edge in the graph thus formed, and remove it (it might be $E_0$ too). The tree thus formed is the MST of the graph.
No comments:
Post a Comment