###### Computer-Organization

October 14, 2023###### Teaching Aptitude

October 14, 2023# Algorithms

Question 19 |

The number of minimum-weight spanning trees of the graph is _______

3 |

To find the number of spanning trees using 2 methods:

- If graph is complete, use n^n-2 formula
- If graph is not complete, then use kirchhoff theorem.

Steps in Kirchoff’s Approach:

(i) Make an Adjacency matrix.

(ii) Replace all non-diagonal is by – 1.

(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.

(iv) Co-factors of any element will give the number of spanning trees.

Using the Kirchhoff theorem will take lot of time because the number of vertices are 9.

So, we use brute force technique to solve the problem with the help of Kruskal’s algorithm.

To find the number of spanning trees using 2 methods:

- If graph is complete, use n^n-2 formula
- If graph is not complete, then use kirchhoff theorem.

Steps in Kirchoff’s Approach:

(i) Make an Adjacency matrix.

(ii) Replace all non-diagonal is by – 1.

(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.

(iv) Co-factors of any element will give the number of spanning trees.

Using the Kirchhoff theorem will take lot of time because the number of vertices are 9.

So, we use brute force technique to solve the problem with the help of Kruskal’s algorithm.