Chapter 23, Problem 1P

(a)

Program Plan Intro

To show that the minimum spanning tree is unique but not the second best spanning tree.

Explanation of Solution

Suppose there are 4 vertices { p, q, r, s } in the following graph. Consider the edge weights and vertices as follows:

  

The minimum spanning tree has weight of 7 and there exists two second best minimum spanning tree having weight 8.

(b)

Program Plan Intro

To prove that there exists edges ( u , v ) $\in$ Tand ( x , y ) $\notin$ Tsuc that $T-\left\{\left(u,v\right)\right\}\cup \left\{\left(x,y\right)\right\}$ is a second-best minimum spanning tree of G , where T is the minimum spanning tree.

Explanation of Solution

T is the minimum spanning tree of graph G . Consider adding an edge that is ( u , v ) $\notin$ T after removing another edge from the particular path that exists between u , v . This replacement of edge will certainly raise weight of the tree. Suppose two or more edges gets replaced, then the new tree will certainly not be better than next best minimum spanning tree.

(c)

Program Plan Intro

To describe an O ( $V^2$ )-time algorithm that, given T , computes maximum of [ u , v ] $\in$ V

Explanation of Solution

The algorithm is as follows:

Consider using dynamic programming approach. For u , v , consider the path from u , v and identify vertex x that is supposed to be occurring right after u . Then, maximum of [ u , v ] is equated to maximum of w ( u , x ) and maximum of [ w , v ]. At last, analyze the case where u , vare adjacent to each other, in this case the max edge weight is the only edge by which they are connected. Once the value of x is found in a constant time, then the program will run in time complexity of O ( $V^2$ ).

(d)

Program Plan Intro

To give an efficient algorithm to compute the second-best minimum spanning tree of graph G.

Explanation of Solution

Firstly, compute the minimum spanning tree in O ( E + Vlog ( V )), this is in time O ( $V^2$ ). Use part c )t to compute maximum double array. Run a min over every pair of u , v vertices, of value $w\left(u,v\right)-\max \left[u,v\right]$ . The weight is considered to be infinite in case no edge is found. After that, the pair that is found to be in min value of the difference, remove from min spanning tree and to the edge, an edge occurring in the path of u , v contains weight maximum u , v .