• Register
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
  • Questions
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Unanswered
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Tags
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Categories
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Users
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exams Taken
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exam List
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

DSA - Graphs and Hashing -Q10


Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+2 votes

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 atmost 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 single spanning tree.

Which one of the following statements is true ?

(A)The algorithm computes minimum spanning trees for some graphs but not for all 

(B)The algorithm computes minimum spanning trees for all the graphs

(C)The algorithm fails in computing  minimum spanning trees for all the graphs. 

(D)The algorithm works correctly in computing  minimum spanning trees for all the graphs with distinct edge weights. 

asked Aug 3, 2020 by gbeditor-2 (72,840 points)
reshown Aug 6, 2020 by gbeditor-2

1 Answer

+1 vote
 
Best answer

We claim that the algorithm will fail. A simple counter example is shown in Figure 1. Graph G = (V, E) has four vertices: {v1, v2, v3, v4}, and is partitioned into subsets

image

G1 with V1 = {v1, v2} and G2 with V2 = {v3, v4}. The minimum spanning tree(MST) of G1 has weight 4, and the MST of G2 has weight 5, and the minimum-weight edge crossing thec cut(V1, V2) has weight 1, in sum the spanning tree forming by the proposed algorithm is v2 − v1 − v4 − v3 which has weight 10. On the contrary, it is obvious that the MST of G is v4 − v1 − v2 − v3 with weight 7. Hence the proposed algorithm fails to obtain an MST.


btw it is clrs question, check last question
https://github.com/gzc/CLRS/blob/master/C23-Minimum-Spanning-Trees/23.2.md

answered Aug 14, 2020 by deepak-gatebook (226,240 points)
Thanks Deepak
Answer:

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
...