Last Updated: 21 Feb, 2021

Total Number Of Spanning Trees In A Graph

Hard

Asked in companies

Solve now

Problem statement

You’re given a connected undirected graph with N nodes and M edges. Your task is to find the total number of spanning trees of this graph.

Note :

A spanning tree T of an undirected graph G is a subgraph that is a tree that includes all of the vertices of G. A graph that is not connected will not contain a spanning tree.

Input Format :

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, the number of nodes, and the edges.
The next ‘M’ line of each test case contains two space-separated integers X and Y, denoting an edge between X and Y.

Output Format :

For every test case, the only output line should contain an integer X, the total number of spanning trees in a graph.

The output of each test case should be printed in a new line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 10
N-1 <= M <= N*(N-1)/2
0  <= 'X', 'Y' <= N - 1

Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of nodes and edges, respectively. And, 'X', 'Y' denotes the node in the graph.
Time limit : 1 sec

Solve now

Approaches

01 Approach

First, check if the given graph is a tree or a complete graph.

If the given graph is a tree, then the number of spanning-tree will be 1.
If the given graph is a complete graph, then the number of spanning trees will be equal to N^(N-2) (Cayley’s Theorem), where N is the number of nodes in the graph.

If the graph is neither a tree nor a complete graph, then we can use the Kirchhoff Matrix-Tree Theorem, through which we can find the number of spanning trees for any graph.

Algorithm :

Make an adjacency matrix ‘adj’ for the given graph.
Then, calculate the degree of each node by counting the number of non-zero entries in its row in the adjacency matrix.
Replace the diagonal entry(Primary Diagonal) of each row with its respective degree that we calculated in Step 2.
Replace all the non-diagonal values = 1 with -1 by traversing the adjacency matrix.
Then, calculate the cofactor of any one element since all the elements’ cofactors will be equal.
Cofactor = ((adj[i][j])^(i+j))* |D|,

where |D| is the determinant of the matrix we get by deleting ith row and jth column from the adjacency matrix.

For calculating the determinant of the N*N matrix, we can break this into subproblems of the determinant of submatrices ((N-1)*(N-1)). |D| will be equal to Summation of ((-1)^(i+j))) * (Determinant of the matrix we get by deleting 1st row and jth column from the adjacency matrix) where j goes from 1 to N.
Hence, we can make a recursive function for calculating the Determinant in which matrix[ ][ ] and N will be argument with base condition of N=2, in which the determinant is a[1][1]*a[2][2] - a[1][2]*a[2][1].
Return the cofactor, which will be equal to the number of spanning trees.

Solve now

Total Number Of Spanning Trees In A Graph

Problem statement

You’re given a connected undirected graph with N nodes and M edges. Your task is to find the total number of spanning trees of this graph.

Note :

Input Format :

Output Format :

Note :

Constraints :

Approaches

01 Approach

If the graph is neither a tree nor a complete graph, then we can use the Kirchhoff Matrix-Tree Theorem, through which we can find the number of spanning trees for any graph. Algorithm :

If the graph is neither a tree nor a complete graph, then we can use the Kirchhoff Matrix-Tree Theorem, through which we can find the number of spanning trees for any graph.

Algorithm :