total_spanning_tree_weight#

total_spanning_tree_weight(G, weight=None, root=None)[source]#

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

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

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

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

自版本 3.3 起已弃用: total_spanning_tree_weight 已弃用，并将在 v3.5 中移除。请改用 nx.number_of_spanning_trees(G)。

参数:
GNetworkX 图
weight字符串或 None，可选 (默认为 None)

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

root节点 (仅有向图需要)

有向图 G 中的一个节点。

返回:
total_weight浮点数
无向图

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

有向图

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

引发:
NetworkXPointlessConcept

如果 G 不包含任何节点。

NetworkXError

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

注意

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

参考

[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. “有向图的矩阵树定理” https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Margoliash.pdf

示例

>>> 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
在本页