Do you think IIT Guwahati certified course can help you in your career?
Introduction🤔
Sometimes, when dealing with graph Data Structures, we come across a term called spanning trees. One might wonder what a spanning tree is and how to form it, calculate the number of spanning trees in a graph, and many other related things. Cool! Are you also wondering about spanning tree❓
So, let us learn about the spanning tree and calculate the total number of spanning trees in a graph.💫
Spanning Tree
Suppose you are given a connected and undirected graph G where graph G has V vertices and E edges. The tree which spans all the vertices of graph G is called the spanning tree. In contrast, the spanning tree is a subgraph of graph G. Given that a graph doesn't involve cycles, it is referred to as a tree. A tree is similar to a graph with N nodes and N-1 edges.
Now, how to calculate the total number of spanning trees?
Total Number of Spanning Trees in a Graph🎯
A spanning tree T is a sub-graph of an undirected graph G, which includes all the vertices of graph G with a minimum possible number of edges.
For example🪢 -
Below are a few possible spanning trees from the above graph.
3️⃣Replace all the diagonal entries with their respective degree.
4️⃣Replace all non-diagonal 1’s with -1.
5️⃣Calculate the cofactor of any one element.
6️⃣The calculated value of the cofactor is the total number of spanning trees for that graph.
Example
We have given an incomplete graph, something like the one below.
The adjacency matrix of the above matrix will look something like these:
1
2
3
4
1
2
0
-1
-1
2
0
2
-1
-1
3
-1
-1
3
-1
4
-1
-1
-1
3
After applying steps three to four, our adjacency matrix converts into:
1
2
3
4
1
2
0
-1
-1
2
0
2
-1
-1
3
-1
-1
3
-1
4
-1
-1
-1
3
Calculate the cofactor of any row and column. It will be the same according to Kirchhoff's theorem.
Implementation🦾
We will find the total number of spanning trees in the above graph.
Function Implementation in C++📄
#include <bits/stdc++.h>
int findDeterminant(vector<vector<int>> Matrix){
/* Variable to store the determinant value*/
int det = 0;
if (Matrix.size() == 1){
return Matrix[0][0];
}
else if (Matrix.size() == 2){
det = (Matrix[0][0] * Matrix[1][1] - Matrix[0][1] * Matrix[1][0]);
return det;
}
else{
for (int p = 0; p < Matrix[0].size(); p++){
vector<vector<int>> tempMatrix;
for (int i = 1; i < Matrix.size(); i++){
vector<int> row;
for (int j = 0; j < Matrix[i].size(); j++){
if (j != p){
row.push_back(Matrix[i][j]);
}
}
if (row.size() > 0){
tempMatrix.push_back(row);
}
}
det = det + Matrix[0][p] * pow(-1, p) * findDeterminant(tempMatrix);
}
return det;
}
}
int spanningTrees(vector<vector<int>> &adjMatrix, int n, int m){
/* Degree of each node will be stored in this*/
int degree[n] = {0};
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (adjMatrix[i][j] == 1){
/* Calculating the degree of each node*/
degree[i]++;
}
}
}
/* Updating the values of the primary diagonal with the degree of the node*/
for (int i = 0; i < n; i++){
adjMatrix[i][i] = degree[i];
}
/* Replacing all 1 in the matrix which is not present on the primary diagonal with -1*/
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if ((i != j) and adjMatrix[i][j] == 1){
adjMatrix[i][j] = -1;
}
}
}
/* Submatrix of size (n-1)*(n-1) in which 1st row and 1st column values will not be there*/
vector<vector<int>>submatrix(n - 1, vector<int>(n - 1));
for (int i = 1; i < n; i++){
for (int j = 1; j < n; j++){
submatrix[i - 1][j - 1] = adjMatrix[i][j];
}
}
/* This will be the answer as (-1)^(1+1) will be equal to 1 only*/
return findDeterminant(submatrix);
}
You can also try this code with Online C++ Compiler
These are three possible spanning trees, i.e., 0 → 1 → 2, 1 → 0 → 2, and 0 → 2 → 1.
Time Complexity🌐 - O(N^4), where N is the number of nodes.
Space Complexity🌐 - O(N^2), where N is the number of nodes.
When Graph is Complete
If the graph is complete, the total number of spanning trees is equivalent to the counting trees with a different label. We can use Cayley's formula to solve this problem. According to Cayley's formula, a graph with V vertices can have V^{(V-2)} different labeled trees.
Therefore, we can say that the total number of spanning trees in a complete graph would be equal to V^{(V-2)}.
Properties
📌In a spanning tree, the number of edges will always be '1' less than the number of vertices.
📌A spanning tree does not contain any cycles.
📌If we remove any one edge from the spanning tree will make it disconnected.
📌If we add one edge to a spanning tree, it will create a cycle in it.
Points to Remember 🔗
You should check if the given graph is a tree, a complete graph or neither a tree nor a complete graph.
Case1 ➼ If the given graph is a tree, there will be 1 spanning tree.
Case2 ➼ If the given graph is complete, there will be N^(N-2) number of spanning trees according to Cayley's theorem, where N is the number of nodes in the graph.
Case3 ➼ If the graph is neither a tree nor a complete graph, then we can use the "Kirchhoff Matrix-Tree Theorem" to find the total number of spanning trees in any graph.
We believe you have understood how to calculate the total number of spanning trees in a graph. Check out this problem - Largest BST In Binary Tree
Frequently Asked Questions
What is a graph data structure?
A non-linear data structure consisting of vertices and edges is called a graph.
What are the primary elements of a graph?
The primary elements of a graph are the vertices and the edges.
What is the difference between a directed graph and an undirected graph?
In a directed graph, the edges are assigned a specified direction. On the other hand, an undirected graph has no direction associated with its edges, allowing them to be traversed in any way.
How can we search elements in a graph?
In a graph, we can search elements using Breadth-First-Search(BFS) and Depth-First-Search(DFS).
Is a tree a graph?
The tree is an undirected graph in which two vertices are connected by exactly one path or a connected acyclic undirected graph.
Conclusion
In this article, we discussed spanning trees. We learned to calculate the total number of spanning trees in a graph using C++ code implementation.
We believe this article on the total number of spanning trees in a graph was helpful. You can refer to other similar articles as well -
84+ registered 