Problem 3. (20 points) You are given an undirected graph G = (V, E) with positive weights, and a minimum spanning tree T = (V,E') for G; you might assume that G and T are given to you as adjacency lists. Now suppose that edges weights in G are modified from w(e) to u'(e). You wish to quickly update the minimum spanning tree T to reflect these changes, without recomputing the tree from scratch. Consider the following six distinct scenarios for updates for each give a O(n +m)-time algorithm to update the MST 1. VeE E. update w,(e) = w(e) + C where C is a positive constant 2. Ve e E, update u'(e) - w(e) - C where C is a positive constant 3. for a single edge e E', update u'(e) = w(e) + C where C is a positive constant 4, for a single edge E', update w,(e)-w(e)-C where C is a positive constant 5. for a single edge e E. update w'(e) = w(e)-C where C is a positive constant 6, for a single edge e E E. update w,(e) = w(e) + C where C is a positive constant Problem 3. (20 points) You are given an undirected graph G = (V, E) with positive weights, and a minimum spanning tree T = (V,E') for G; you might assume that G and T are given to you as adjacency lists. Now suppose that edges weights in G are modified from w(e) to u'(e). You wish to quickly update the minimum spanning tree T to reflect these changes, without recomputing the tree from scratch. Consider the following six distinct scenarios for updates for each give a O(n +m)-time algorithm to update the MST 1. VeE E. update w,(e) = w(e) + C where C is a positive constant 2. Ve e E, update u'(e) - w(e) - C where C is a positive constant 3. for a single edge e E', update u'(e) = w(e) + C where C is a positive constant 4, for a single edge E', update w,(e)-w(e)-C where C is a positive constant 5. for a single edge e E. update w'(e) = w(e)-C where C is a positive constant 6, for a single edge e E E. update w,(e) = w(e) + C where C is a positive constant