You are given a tree T which is a MST of a graph G = (V, E). For one particular edge e which is not in T , its edge weight is decreased (all other edges stay the same).

Specifically the weight of echanged from a to b where a > b > 0.

Find a MST T ⁰ for this new graph using the MST T for the old graph.

The set T is given as a list of edges or in adjacency list representation (whichever is convenient for you). You can access the function w() for the weight of each edge. You are given one particular edge e = (y, z) where e 2/ T and you are given the old weight a and new weight b for this edge e.

Part (a): Explain your algorithm for finding a MST T ⁰ for these new weights.

Part (b): State and explain the running time in terms of n = V and m = E . F