Let G = (V, E) be an undirected, connected graph with weight function w : E → R, and suppose that |E| ≥ |V| and all edge weights are distinct. A second-best minimum spanning tree is defined as follows. Let be the set of all spanning trees of G, and let T′ be a minimum spanning tree of G. Then a second-best minimum spanning tree is a spanning tree T such that w(T) = min T” ε T - |T’| {w(T’’)}.
a. Show that the minimum spanning tree is unique, but that the second-best minimum spanning tree need not be unique.
b. Let T be a minimum spanning tree of G. Prove that there exist edges (u, v) ¬ T and (x, y) ∉ T such that T - {(u, v)} ¬ {(x, y)} is a second-best minimum spanning tree of G.
c. Let T be a spanning tree of G and, for any two vertices u, v ¬ V, let max[u, v] be an edge of maximum weight on the unique path between u and v in T. Describe an O(V2)- time algorithm that, given T, computes max[u, v] for all u, v ¬ V.
d. Give an efficient algorithm to compute the second-best minimum spanning tree of G.