[Solved]Following Question S Answer Taken Clrs Third Eddition D Like Know Lemma Refer Answer Q37200462
The Following question, and it’s answer, is taken from CLRS,third eddition.
I’d like to know which lemma they refer to in their answer.
23.2-7 * Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G? Official answer We use this lemma as follows. Let G’ = (V’, E’) be the graph G (V, E) with the one new vertex and its incident edges added. spanning tree T for G. We compute a minimum spanning tree for G by creating the graph G” = (V’, E”), where E’, consists of the edges of T and the edges in E’ E ie, the edges added to G that made G), and then finding a minimum spanning tree T for G”. By the lemma, there is a minimum spanning tree for G that includes no edges of E T. In other words, G has a minimum spanning tree that includes only edges in T and E – E these edges comprise exactly the set E” Thus, the the mini of G’ Suppose that we have a minimum mum spanning tree T of G” is also a minimum spanning tree Even though the proof of the lemma uses Kruskal’s algorithm, we are not required to use this algorithm to find T. We can find a minimum spanning tree by any means we choose. Let us use Prim’s algorithm with a Fibonacci-heap priority queue. Since l V’l IVI + 1 and IE” 2lVl-1 (E” contains the l VI-1 edges of T and at most |VI edges in E – E), it takes O(V) time to construct G” and the run of Prim’s algorithm with a Fibonacci-heap priority queue takes time O(E” V’lgV)-O(V1g V). Thus, if we are given a minimum spanning tree of G, we can compute a minimum spanning tree of G in O(V 1g V) time Show transcribed image text 23.2-7 * Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G? Official answer We use this lemma as follows. Let G’ = (V’, E’) be the graph G (V, E) with the one new vertex and its incident edges added. spanning tree T for G. We compute a minimum spanning tree for G by creating the graph G” = (V’, E”), where E’, consists of the edges of T and the edges in E’ E ie, the edges added to G that made G), and then finding a minimum spanning tree T for G”. By the lemma, there is a minimum spanning tree for G that includes no edges of E T. In other words, G has a minimum spanning tree that includes only edges in T and E – E these edges comprise exactly the set E” Thus, the the mini of G’ Suppose that we have a minimum mum spanning tree T of G” is also a minimum spanning tree Even though the proof of the lemma uses Kruskal’s algorithm, we are not required to use this algorithm to find T. We can find a minimum spanning tree by any means we choose. Let us use Prim’s algorithm with a Fibonacci-heap priority queue. Since l V’l IVI + 1 and IE” 2lVl-1 (E” contains the l VI-1 edges of T and at most |VI edges in E – E), it takes O(V) time to construct G” and the run of Prim’s algorithm with a Fibonacci-heap priority queue takes time O(E” V’lgV)-O(V1g V). Thus, if we are given a minimum spanning tree of G, we can compute a minimum spanning tree of G in O(V 1g V) time
Expert Answer
Answer to The Following question, and it’s answer, is taken from CLRS, third eddition. I’d like to know which lemma they refer to … . . .
OR
