DSA - Graphs and Hashing -Q11

Question

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

 

                                       

Answer 1

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

Answer 2

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