节点连通性

node_connectivity(G, s=None, t=None, flow_func=None)

返回图 G 或有向图 G 的节点连通性。

节点连通性等于必须移除以使图 G 断开连接或变得平凡的最小节点数。如果提供了源节点和目标节点，此函数返回局部节点连通性：必须移除以断开图 G 中所有从源到目标的路径的最小节点数。

参数:

GNetworkX 图

无向图

s节点

源节点。可选。默认值: None。

t节点

目标节点。可选。默认值: None。

flow_func函数

用于计算一对节点之间最大流的函数。该函数必须接受至少三个参数：一个有向图、一个源节点和一个目标节点。并返回一个符合 NetworkX 约定的残差网络（详见maximum_flow()）。如果 flow_func 为 None，则使用默认的最大流函数（edmonds_karp()）。详见下文。默认函数的选择可能会在版本之间变化，不应依赖。默认值: None。

返回值:

K整数

G 的节点连通性，如果提供了源节点和目标节点，则为局部节点连通性。

另请参阅

local_node_connectivity()

edge_connectivity()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

注意

这是节点连通性的基于流的实现。该算法通过在辅助有向图上解决 \(O((n-\delta-1+\delta(\delta-1)/2))\) 个最大流问题来工作。其中 \(\delta\) 是 G 的最小度数。关于辅助有向图和局部节点连通性计算的详细信息，请参阅 local_node_connectivity()。此实现基于 [1] 中的算法 11。

参考文献

[1]

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

示例

>>> # Platonic icosahedral graph is 5-node-connected
>>> G = nx.icosahedral_graph()
>>> nx.node_connectivity(G)
5

您可以使用替代的最大流算法进行底层的最大流计算。在密集网络中，算法 shortest_augmenting_path() 通常比默认的 edmonds_karp() 表现更好，而 edmonds_karp() 对于具有高度偏斜度分布的稀疏网络更快。替代流函数必须从 flow 包中显式导入。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> nx.node_connectivity(G, flow_func=shortest_augmenting_path)
5

如果您将一对节点（源节点和目标节点）指定为参数，此函数将返回局部节点连通性的值。

>>> nx.node_connectivity(G, 3, 7)
5

如果您需要在同一图上对不同节点对执行多次局部计算，建议您复用最大流计算中使用的数据结构。详见 local_node_connectivity()。