节点连通性#

node_connectivity(G, s=None, t=None)[source]#

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

节点连通性等于必须移除以断开 G 或使其变为平凡图的最小节点数。根据 Menger 定理，这等于节点独立路径的数量（除了源节点和目标节点外不共享任何节点的路径）。

如果提供了源节点和目标节点，此函数返回局部节点连通性：即必须移除以断开 G 中从源节点到目标节点的所有路径的最小节点数。

该算法基于一种快速近似方法，该方法为两个节点之间节点独立路径的实际数量提供了严格的下限 [1]。它适用于有向图和无向图。

参数:
GNetworkX 图

无向图

s节点

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

t节点

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

返回:
K整数

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

另请参阅

all_pairs_node_connectivity
local_node_connectivity

注释

该算法 [1] 通过使用 BFS 计算两个节点之间的最短路径来查找节点独立路径，将找到的路径中的节点标记为“已使用”，然后搜索排除已标记为已使用的节点的其他最短路径，直到不再存在路径。它不精确，因为最短路径可能会使用一些节点，如果路径更长，这些节点可能属于两条不同的节点独立路径。因此，它只保证节点连通性的严格下限。

参考文献

[1] (1,2)

White, Douglas R., and Mark Newman. 2001 一种快速的节点独立路径算法. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf

示例

>>> # Platonic octahedral graph is 4-node-connected
>>> from networkx.algorithms import approximation as approx
>>> G = nx.octahedral_graph()
>>> approx.node_connectivity(G)
4
在本页