In: Advanced Math
5. Suppose we are given both an undirected graph G with weighted
edges and
a minimum spanning tree T of G .
(a) Describe an algorithm to update the minimum spanning tree when
the
weight of a single edge e is decreased.
(b) Describe an algorithm to update the minimum spanning tree when
the
weight of a single edge e is increased.
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.
[Hint: Consider the cases e ∈ T and e 6∈ T separately.]