Suppose you are given an undirected graph G with weighted edges and a minimum spanning tree T of G.
• Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.
• Design an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased.
In both cases, the input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree. Analyze the running time of your algorithms and prove the correctness.