2. Graded Problem (Page limit: 1 sheet; 2 sides) This problem is on finding a Minimum width spanning tree Let G (V, E, W) be a weighted connected (undirected) graph, where V is the set of vertices, E is the set of edges, we E W for each e EE is a nonnegative weight of the edge e. A spanning tree is defined as usual namely T- (V,Te) where Te C E and T is a tree. The width of a spanning tree T is max{we |e TEl Thus it is the most "expensive" edge in the tree. T is a Minimum width spanning tree of G if it is a spanning tree and achieves the minimum width among all spanning trees of G Show that even if the weights of G = (V, E, W) are all distinct, there could be more than one Minimum width spanning trees Suppose Est -{e E E | we S t} is the set of edges in G with weights at most t. Suppose Gst has connected components C1, C2,... , Cs, for some s 2 1. Let Ti be a Minimum width spanning tree of C (for 1iK s), prove that there is a Minimum width spanning tree T of G that contains U-14, i.e., T is obtained by adding some number of (zero or more) edges from E to the edge sets of T1,T2,...,Ts. Can you write down what is the number of edges to be added (in terms of the data already given)? . Suppose wi W2 Um are all the edges of G. Find an algorithm for Minimum width spanning tree that implements the following idea: Imagine a threshold t rises from 0, to wi, then to w2, (You can use a min-heap for this.) At each threshold level t, you can consider the graph Gt (V, E