# Question: Let G V E be an undirected connected graph

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.

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.

**View Solution:**## Answer to relevant Questions

Suppose that a graph G has a minimum spanning tree already computed. How quickly can the minimum spanning tree be updated if a new vertex and incident edges are added to G?We are given a directed graph G = (V, E) on which each edge (u, v) ¬ E has an associated value r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a communication ...Give a type definition for a scalar type called CIRCLE, what selectors and The-operators apply to this type? Also:a. Define a set of read only operators to compute the diameter, circumference, and area of a given circle.b. ...What do you understand by the term first normal form?Consider the SQL type point and the SQL table points as defined in the subsection “Structured Types” Type Point has a representation involving Cartesian coordinates X and Y. What happens if we replace that type by a ...Post your question