Results 1 to 2 of 2

Thread: Number of spanning trees

  1. #1
    Newbie
    Joined
    May 2018
    From
    greece
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    397
    Thanks
    68

    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.
    Last edited by MacstersUndead; Jul 20th 2018 at 11:33 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 9th 2011, 01:10 PM
  2. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: Nov 5th 2010, 07:02 AM
  3. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 27th 2010, 05:07 PM
  4. Spanning trees
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 27th 2010, 08:06 PM
  5. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 2nd 2009, 11:17 PM

Search Tags


/mathhelpforum @mathhelpforum