number_of_spanning_trees#

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

返回 G 中生成树的数量。

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

此函数 (当 weight 为 None 时) 返回无向图的生成树数量以及有向图从单个根节点出发的树形图数量。当 weight 是一个边属性的名称，该属性保存了每条边的权重值时，函数返回所有树的乘积权重的总和。也就是说，树的权重是其边权重的乘积。

基尔霍夫的树矩阵定理 (Kirchoff’s Tree Matrix Theorem) 表明，图的拉普拉斯矩阵的任何余子式都是图中生成树的数量。(这里我们使用对角线元素的余子式，这样余子式就变成了去掉一行及其对应列后的矩阵的行列式。) 对于加权的拉普拉斯矩阵，余子式是所有生成树的乘积权重的总和。也就是说，每棵树的权重是其边权重的乘积。该定理也称为基尔霍夫定理 [1] 和矩阵树定理 [2]。

对于有向图，一个类似的定理 (Tutte 定理) 成立，其中余子式是选择与根节点对应的那一行和那一列移除后的余子式。该余子式是以指定节点为根的树形图数量。加权版本则给出以 root 为根的树形图权重的总和。树形图的权重是其边权重的乘积。

参数:

GNetworkX 图
root节点: 有向图 G 中的一个节点，该节点的所有节点都是其后代。(对于无向图则忽略此参数。)
weight字符串或 None，可选 (默认为 None): 保存边权重的边属性名称。如果为 None，则假定每条边的权重为 1。

返回:

数值

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

引发:

NetworkXPointlessConcept: 如果 G 不包含任何节点。
NetworkXError: 如果图 G 是有向图，且未指定根节点或根节点不在 G 中。

注意

排除自环。多条边会被合并为一条权重等于它们权重之和的边。

参考文献

[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] (1,2)

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

示例

>>> 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