'Is the computed number of spanning trees for this undirected graph reasonable/correct?
This is part of my Master thesis which is about designing hydrogen pipeline networks.
For a particular graph of 135 nodes and 157 edges and (see figure below), I need to compute the number of spanning trees (spanning all nodes). I used the Kirchhoff's theorem and implemented it (using scipy and networkx) this way:
import networkx as nx
from scipy import linalg
def nbr_spanning_trees(a_G):
L = nx.laplacian_matrix(a_G) # compute the laplacian matrix which is equal to degree matrix - adjacency matrix
L = L.toarray() # convert the sparse matrix output of the previous line to an array
L_cof = L[1:, 1:] # extract the submatrix associated with the (1,1)-entry's cofactor from the Laplacian matrix
# (any cofactor can be taken)
det = linalg.det(L_cof) # calculate the cofactor
return det
The returned result is: 1.879759212930661e+16 spanning trees.
This number seems gigantesque, is it reasonable/correct? Is my implementation correct?
As an addition, the graph has at least 23 cycles (but not much more I think). I know this since I have identified the minimum spanning tree and it has 23 edges less than the underlying graph.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|