Kirchhoff’s Theorem for Calculating number of Spanning trees Of a Graph
source link: https://www.geeksforgeeks.org/videos/kirchhoffs-theorem-for-calculating-number-of-spanning-trees-of-a-graph/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Kirchhoff’s Theorem for Calculating number of Spanning trees Of a Graph
- 30/05/2022
If a graph is a complete graph with n vertices, then total number of spanning trees is n(n-2) where n is the number of nodes in the graph. In complete graph, the task is equal to counting different labeled trees with n nodes for which have Cayley’s formula.
What if graph is not complete? Follow the given procedure :- STEP 1: Create Adjacency Matrix for the given graph. STEP 2: Replace all the diagonal elements with the degree of nodes. For eg. element at (1,1) position of adjacency matrix will be replaced by the degree of node 1, element at (2,2) position of adjacency matrix will be replaced by the degree of node 2, and so on.
Kirchhoff’s Theorem for Calculating number of Spanning trees Of a Graph: https://www.geeksforgeeks.org/total-number-spanning-trees-graph/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK