total_spanning_tree_weight#
- total_spanning_tree_weight(G, weight=None, root=None)[source]#
Returns the total weight of all spanning trees of
G
.Kirchoff’s Tree Matrix Theorem [1], [2] states that the determinant of any cofactor of the Laplacian matrix of a graph is the number of spanning trees in the graph. For a weighted Laplacian matrix, it is the sum across all spanning trees of the multiplicative weight of each tree. That is, the weight of each tree is the product of its edge weights.
For unweighted graphs, the total weight equals the number of spanning trees in
G
.For directed graphs, the total weight follows by summing over all directed spanning trees in
G
that start in theroot
node [3].Deprecated since version 3.3:
total_spanning_tree_weight
is deprecated and will be removed in v3.5. Usenx.number_of_spanning_trees(G)
instead.- Parameters:
- GNetworkX Graph
- weightstring or None, optional (default=None)
The key for the edge attribute holding the edge weight. If None, then each edge has weight 1.
- rootnode (only required for directed graphs)
A node in the directed graph
G
.
- Returns:
- total_weightfloat
- Undirected graphs:
The sum of the total multiplicative weights for all spanning trees in
G
.- Directed graphs:
The sum of the total multiplicative weights for all spanning trees of
G
, rooted at noderoot
.
- Raises:
- NetworkXPointlessConcept
If
G
does not contain any nodes.- NetworkXError
If the graph
G
is not (weakly) connected, or ifG
is directed and the root node is not specified or not in G.
Notes
Self-loops are excluded. Multi-edges are contracted in one edge equal to the sum of the weights.
References
[1]Wikipedia “Kirchhoff’s theorem.” https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
[2]Kirchhoff, G. R. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung Galvanischer Ströme geführt wird Annalen der Physik und Chemie, vol. 72, pp. 497-508, 1847.
[3]Margoliash, J. “Matrix-Tree Theorem for Directed Graphs” https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Margoliash.pdf
Examples
>>> G = nx.complete_graph(5) >>> round(nx.total_spanning_tree_weight(G)) 125
>>> G = nx.Graph() >>> G.add_edge(1, 2, weight=2) >>> G.add_edge(1, 3, weight=1) >>> G.add_edge(2, 3, weight=1) >>> round(nx.total_spanning_tree_weight(G, "weight")) 5