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 , are modified from w(e) to w'(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. Ve E E, update u'(e) w(e)C where C is a positive constant 2. Ve E E, update u'(e)-(e)- C where C' is a positive constant 3. for a single edge e E, update w,(e)-w(e) + C where C is a positive constant 4. for a single edge e E: update w,(e)-w(e)-C where C is a positive constant 5. for a single edge e E E', update w,(e) = w(e)-C where C is a positive constant 6, for a single edge e E', update w,(e) = w(e) + C where C is a positive constant