20 marks] For any graph G (V, E) with positive edge weights, the minimum spanning tree T is the "cheapest" subgraph (both in terms of total weight and in terms of number of edges) that connects all the vertices. However, two vertices that are "close" in G may be "far apart" n I. More precisely, let dc(u, v) be the length of a shortest path between u and v in G. Let H be any subgraph of G formed by deleting some edges, and let dH(u, v) be the length of a shortest path between u and v in H. Note that dH (u, v) 2 dc(u, v). Consider the worst case ratio of dH (u, v) to dc(u, v): dH(u, v) dad, : u, v vertices of G (a) 4 marks] Show that if T is the minimum spanning tree of G then (T) can be linear in n, the number of vertices. In particular, describe for any n, an example of an edge- weighted graph on n vertices and a pair of vertices u and v in the graph s.t. dT(u, v) - endG(u, u)). For the purpose of bounding , there are alternatives to the minimum spanning tree. Consider the following generalization of Kruskal's greedy minimum spanning tree algorithm. Input to the algorithm is a graph G = (V,E) and a weight w(e) for each edge e with w(e) > 0. The algorithm depends on a real-valued parameter t >1. Let the graph produced by the algorithm be called Ht