GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
117 views

I am getting 128 as answer:

8 Spanning trees in first part(LHS) * 2 choice in middle Part * 8 Spanning trees in Second part(RHS), but given answer is 256:

asked in Algorithms by Veteran (14.6k points)   | 117 views
Actually its calculation is cumbersome..We have to ensure that double counting does not occur..For that proper enumeration of cases is necessary which will be a tedious process for this..

1 Answer

+1 vote
Hi, actually you can select e and f edges together also which will make more number of spanning trees.

128  ( either you select e or f )  +  extra spanning tree ( selecting e and f both ).

One  way to calculate total number of distinct spanning tree in an undirected unweighted graph having no simple loop and no multiple edges and connected using Laplacian matrix.

L(G) =  D - A

Where D is degree matrix  of N * N  and A adjacency matrix of N * N

if( i == j)  then D[i][j] =   total number of edges incident on ith node

else   if(i != j )  then D[i][j] = 0        ( Hence only diagonal elements have some value >= 0 ) rest all are zero

A :  adjacency matrix  ,   A[i][j] =  1  if  node i and node j have edge between them else A[i][j] = 0

Now Laplacian matrix L(G) =  D - A

Now total number of disctint spanning tree in the graph  is   =    (-1)^(i + j ) - cofactor after removing ith row and jth column

where you can take i and j , any values between 1 and N.

means calculating any one co-factor of matrix will give you the number of distinct spanning tree in the graph.

But helpfull only for small graph, because it's difficult for us to calculate determinant of large matrix by hands....
answered by Loyal (2.7k points)  
yes you're correct we can select both which will give more number of spanning trees but applying krrichof's theorem as you said is very difficult for such a huge graph :( :(
Then just fix e and f edges,  and select two edges from left side and make left portion connected , and check number of ways  to select from right part.

Then select another way for left part for selecting two edges and multiply it number of ways to select two edges from right part.

Add all ways.


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users