solutions-clrs

  Page 1 of 1 PSU CMPSC 465 Spring 2013 Homework Solutions – Unit 4: Chapter 23 CMPSC 465 Disclaimer: This is a draft of solutions that has been prepared by the TAs and the instructor makes no guarantees that solutions presented here contain the level of detail that would be expected on an exam Any errors or explanations you find unclear should be reported to either of the TAs for corrections first Exercise 231-2 Professor Sabatier conjectures the following converse of Theorem 231 Let G  = ( V  ,  E  ) be a connected, undirected graph with a real-valued weight function w  defined on  E  Let  A  be a subset of  E   that is included in some minimum spanning tree for G , let ( S  , V   – S  ) be any cut of G  that respects  A , and let ( u , v ) be a safe edge for  A  crossing ( S  , V   – S  ) Then, ( u , v ) is a light edge for the cut Show that the professor’s conjecture is incorrect by giving a counterexample Solution : That is false A safe edge (with respect to the set of edges  A ) is defined to be any edge such that when we add it to  A , we still have a subset of some minimum spanning tree This definition does not reference light edges in any way In the situation from a counterexample, there may be multiple safe edges from S   to V   – S  , not all of them have to be light A counterexample is shown below Let S   = { a , b , c },  A  = {( a , b ), ( b , c }, we can see that ( a , d  ), ( b , e ), ( c ,  f  ) are all safe edges for  A  crossing ( S  , V   – S  ), but only ( b , e ) is a light edge for the cut Exercise 231-3 Show that if an edge ( u , v ) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph Solution : Suppose ( u , v ) T  , a minimal spanning tree Let  A  = { T   – ( u , v )}  A  contains two trees:  A  = T  u  T  v T  u  is the tree in which vertex u  appears, and T  v  is the tree in which vertex v  appears Moreover, V  u  V  v  = V  , where V  u  contains the vertices of T  u  and V  v  contains the vertices of T  v That is, ( V  u , V  v ) is a cut, which is crossed by ( u , v ) and which respects  A Any edge crossing the cut rejoins the two trees If there is a crossing edge (  x ,  y ) with w (  x ,  y ) < w ( u , v ), then T’   = T  u  T  v  (  x ,  y ) is a spanning tree with weight: w ( T’  ) = w ( T  u  T  v ) + w (  x ,  y ) as T’   = T  u  T  v  (  x ,  y ) = w ( T  u  T  v ) + w ( u , v ) + [ w (  x ,  y ) – w ( u , v )] by adding 0, that is w ( u , v ) – w ( u , v ) = w ( T  ) – [ w ( u , v ) – w (  x ,  y )] as T   = T  u  T  v  ( u , v ) < w ( T  ) This contradicts with that ( u , v ) is contained in some minimum spanning tree So, w ( u , v ) < w (  x ,  y ) for all (  x ,  y ) crossing the cut ( V  u , V  v ) That is, ( u , v ) is a light edge crossing the cut Exercise 232-1 Kruskal’s algorithm can return different spanning trees for the same input graph G , depending on how it breaks ties when the edges are sorted into order Show that for each minimum spanning tree T of G , there is a way to sort the edges of G  in Kruskal’s algorithm so that the algorithm returns  T  a e d  f b c 1 1 3 1 5 5 4  Page 2 of 2 PSU CMPSC 465 Spring 2013 Solution : We would start by sorting the edges in of G  in non-descending order In addition, we would want that among the edges of same weight, the edges which are contained in T   are placed in first positions Exercise 232-8 Professor Borden proposes a new divide-and-conquer algorithm for computing minimum spanning trees, which goes as follows Given a graph G  = ( V  ,  E  ), partition the set V   of vertices into two sets V  1  and V  2  such that | V  1 | and | V  2 | differ by at most 1 Let  E  1  be the set of edges that are incident only on vertices in V  1 , and let  E  2  be the set of edges that are incident only on vertices in V  2 Recursively solve a minimum-spanning-tree problem on each of the two subgraphs G 1  = ( V  1 ,  E  1 ) and G 2  = ( V  2 ,  E  2 ) Finally, select the minimum-weight edge in  E that crosses the cut ( V  1 , V  2 ), and use this edge to unite the resulting two minimum spanning trees into a single spanning tree Either argue that the algorithm correctly computes a minimum spanning tree of G , or provide an example for which the algorithm fails Solution : We argue that the algorithm fails Consider the graph G  below We partition G  into V  1  and V  2  as follows: V  1  = {  A ,  B }, V  2  = { C  ,  D }  E  1  = {(  A ,  B )}  E  2  = {( C  ,  D )} The set of edges that cross the cut is  E  c  = {(  A , C  ), (  B ,  D )}  Now, we must recursively find the minimum spanning trees of G 1  and G 2 We can see that in this case, MST( G 1 ) = G 1  and MST( G 2 ) = G 2 The minimum spanning trees of G 1  and G 2  are shown below on the left The minimum weighted edge of the two edges across the cut is edge (  A , C  ) So (  A , C  ) is used to connect G 1  and G 2 This is the minimum spanning tree returned by Professor Borden’s algorithm It is shown below and to the right We can see that the minimum-spanning tree returned by Professor Borden’s algorithm is not the minimum spanning tree of G , therefore, this algorithm fails  A  D C  B 1 G 1  2 3 8 G 2    A  D C  B 1 G 1  2 3 8 G 2    A  D C  B 1 2 3 8