• 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 -Q11


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

How many spanning trees are possible for the graph given below ?

 

                                        image

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

2 Answers

+1 vote
 
Best answer
edge b-g must be included

from both left and right components  out of 5 ,3 edges must be selected  which is possible in C(5,3) =10 ways .

now from left portion  out of these 10 combinations 2 combinations (ab, bc,ac  and   cd,db,cb ) must be excluded as they form a cycle and also do not  cover  remaiining vertex  so total 8 choices are possible.

Similarly from right portion  out of  10 combinations 2 combinations (ef ,fg ,eg   and gh hf gf )   must be excluded as they form a cycle and also do not  cover  remaiining vertex  so again total 8 choices are possible.

so by product rule 8x8 =64 choices are possible
answered Aug 8, 2020 by (18,750 points)
selected Aug 10, 2020 by deepak-gatebook
+1 vote

The edge bg has to be in the MST

This problem reduces to multiplying subproblem A and B

subproblem A is identical to B

so it is A^2

Subproblem A: 

Number of Spanning tree of abcd subgraph

Using Kirchoff's Matrix tree theorem,

make adjacency matrix out of this

replace diagonal by degree of vertices

and non diagonal elements just put their additive inversive in their place.

now find Minor of any element.

it is given by formula

When you solve it you will get this matrix

 

Now A= 8

A^2 is 8*8 = 64

 

Reference

https://ocw.mit.edu/courses/mathematics/18-314-combinatorial-analysis-fall-2014/readings/MIT18_314F14_mt.pdf

answered Sep 26, 2020 by tsshashankrustagi (11,240 points)
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
...