Register

Spanning Tree

• retagged by
415 views

1 Answer

1 votes
1 votes 
Number of Spanning Trees: 2911

This can be solved by Kirchoff's Matrix Tree Theorem :

  1. Make a matrix. (Rows = Columns = Total Vertices)
     
  2. For i != j , if i & j are adjacent vertices,
    then M[i][j] = -1,

    if not M[i][j] = 0

    For i == j, M[i][j] = degree of vertex
     
  3. Last, Calculate the co-factor for any element. The cofactor that you get is the total number of spanning trees for that graph.

 

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Ram Swaroop asked Jan 30, 2019
1,589 views
MadeEasy Test Series 2019: Algorithms - Spanning Tree
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the spanning tree of G_ 36
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...
User Avatar
7 votes
7 votes
2 answers
2
Lakshman Bhaiya asked Jan 15, 2018
6,074 views
number of spanning tree
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.
User Avatar
3 votes
3 votes
0 answers
3
smsubham asked Jan 6, 2018
543 views
Ace Test series: Algorithms - Spanning Tree
Am getting 7. The answer given is 10. A - B , A - D , D - E , E - C are the edges i have included.
Am getting 7. The answer given is 10.A - B , A - D , D - E , E - C are the edges i have included.
User Avatar
Link Copied!