number_of_spanning_trees

number_of_spanning_trees(G, *, root=None, weight=None)

返回图 G 中的生成树数量。

无向图的生成树是连接图中所有节点的树。对于有向图，生成树的类似概念称为（生成）树形图。树形图包含从 root 节点到每个其他节点的唯一有向路径。图必须是弱连通的，并且根节点必须包含所有节点作为后继节点 [3]。请注意，为了避免讨论汇根和反向树形图，我们反转了 [3] 中的边方向并使用入度拉普拉斯矩阵。

此函数（当 weight 为 None 时）返回无向图的生成树数量和有向图从单个根节点开始的树形图数量。当 weight 是包含每条边权重值的边属性的名称时，函数返回所有树的乘积权重之和。即，树的权重是其边权重的乘积。

基尔霍夫树矩阵定理指出，图的拉普拉斯矩阵的任何余子式都是图中的生成树数量。（这里我们使用对角线项的余子式，使得余子式成为去掉一行及其对应列的矩阵的行列式。）对于加权拉普拉斯矩阵，余子式是所有生成树的乘积权重之和。即，每棵树的权重是其边权重的乘积。该定理也称为基尔霍夫定理 [1] 和矩阵树定理 [2]。

对于有向图，类似的定理（图特定理）成立，余子式选择为与根对应的行和列被移除的余子式。余子式是以指定节点为根的树形图数量。加权版本给出以 root 为根的树形图权重的总和。树形图的权重是其边权重的乘积。

Parameters:

GNetworkX 图

root节点

有向图 G 中的一个节点，该节点将所有节点作为后代。 （对于无向图忽略此参数。）

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

包含边权重的边属性的名称。 如果为 None ，则每条边的权重假定为 1。

Returns:

Number

无向图：

图 G 的生成树数量。 或图 G 的所有生成树权重的总和，其中树的权重是其边权重的乘积。

有向图：

以节点 root 为根的 G 的树形图数量。 或图 G 的所有指定根的树形图权重的总和，其中树形图的权重是其边权重的乘积。

Raises:

NetworkXPointlessConcept

如果 G 不包含任何节点。

NetworkXError

如果图 G 是有向的且未指定根节点或根节点不在 G 中。

Notes

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

References

[1]

维基百科 “基尔霍夫定理” https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

[2]

基尔霍夫, 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]

马戈利亚什, J. “有向图的矩阵树定理” https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Margoliash.pdf

Examples

>>> G = nx.complete_graph(5)
>>> round(nx.number_of_spanning_trees(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.number_of_spanning_trees(G, weight="weight"))
5