total_spanning_tree_weight

total_spanning_tree_weight(G, weight=None, root=None)

返回图 G 中所有生成树的总权重。

基尔霍夫的树矩阵定理 [1], [2] 指出，图的拉普拉斯矩阵的任何余子式的行列式是图中的生成树数量。对于加权拉普拉斯矩阵，它是所有生成树的乘积权重的总和。也就是说，每个树的权重是其边权重的乘积。

对于无权图，总权重等于 G 中的生成树数量。

对于有向图，总权重通过对 G 中以 root 节点开始的所有的有向生成树求和得到 [3]。

Deprecated since version 3.3: total_spanning_tree_weight 已弃用，将在 v3.5 中移除。请改用 nx.number_of_spanning_trees(G) 。

Parameters:

GNetworkX 图

weight字符串或 None, 可选 (默认=None)

边属性的键，用于保存边权重。 如果为 None，则每条边的权重为 1。

root节点 (仅对有向图必需)

有向图 G 中的一个节点。

Returns:

total_weight浮点数

无向图:

图 G 中所有生成树的总乘积权重之和。

有向图:

图 G 中所有以节点 root 为根的生成树的总乘积权重之和。

Raises:

NetworkXPointlessConcept

如果 G 不包含任何节点。

NetworkXError

如果图 G 不是（弱）连通的， 或者如果 G 是有向图且未指定根节点或根节点不在 G 中。

Notes

自环被排除。多重边被合并为一条边，其权重等于各边权重的总和。

References

[1]

维基百科 “基尔霍夫定理” 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. “有向图的矩阵树定理” 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