# Thread: Number of spanning trees

1. ## Number of spanning trees

Can anyone write a program on python which calculates the number of spanning trees of a graph, having as input the adjacency matrix of the graph?

spanningtrees.pdf

2. ## Re: Number of spanning trees

This is a (mini)-project rather than a problem to be answered.
In principle I could write a python program given the time, but that would take away from what you would learn andexperience through writing a program yourself.
I'll give you an outline I'd think of before starting to write the code.

First, understand how to solve the problem on paper

By Kirchoff's Theorem, you can directly calculate the number of spanning trees t(G) using the Laplacian matrix https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
The Laplacian matrix is the difference between the degree matrix and the adjacency matrix, L = D - A
Delete any row and column from the matrix for L* (first row and first column)
Calculate the determinant. det(L*) = t(G)

Next, write some psuedocode to mimic the process above.
I would suggest splitting between files so that the code can be managed effectively. At minimum, I would suggest creating at least three files under the project file.

One file should delegate UI and inputs only (command line interface can work, but if you want a graphical interface, I highly recommend pygame or tkinter.) Here you should consider maximum size of the square matrices, and if the input should be user entered, or through a file (I'd choose file).
One file should handle the definition of matricies and matrix algebra (importing the existing matrix module from numPy seems like a good idea here). ie. The meaty calculation logic.
The last file should be for Unit Tests, which would test separate definitions defined in the matrix algebra file. A definition per calculation step would be ideal in terms of best practice, as it's easier to debug. (Def to calculate Laplacian matrix, def to delete row and column, and one to calculate det(L*) or t(G) ).

Let me know if you have further question. I'm here to help. Trust me when I say I find it much more rewarding doing the coding myself, and I hope that you will find the same enjoyment yourself.