node_connectivity

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

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

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

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

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

Parameters:

GNetworkX图

无向图

s节点

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

t节点

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

Returns:

K整数

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

See also

all_pairs_node_connectivity

local_node_connectivity

Notes

此算法[1]通过使用BFS计算最短路径，标记找到路径的节点为“已使用”，然后排除已标记节点搜索其他最短路径，直到不存在更多路径。它不是精确的，因为最短路径可能使用节点，如果路径更长，这些节点可能属于两条不同的节点独立路径。因此，它仅保证节点连通性的严格下界。

References

[1]

White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf

Examples

>>> # 柏拉图正八面体图是4节点连通的
>>> from networkx.algorithms import approximation as approx
>>> G = nx.octahedral_graph()
>>> approx.node_connectivity(G)
4