node_connectivity

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

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

节点连接性等于断开G连接或使G变得微不足道时必须删除的最小节点数。根据Menger定理，这等于独立于节点的路径数（除了源和目标之外不共享任何节点的路径）。

如果提供了源节点和目标节点，则此函数返回本地节点连接：在g中，必须删除的节点的最小数目，才能中断从源到目标的所有路径。

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

参数

G网络X图表

无向图

s结点

源节点。可选的。默认值：无。

t结点

目标节点。可选的。默认值：无。

返回

K整数

G的节点连接，如果提供了源和目标，则为本地节点连接。

参见

all_pairs_node_connectivity

local_node_connectivity

笔记

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

工具书类

1(1,2)

怀特、道格拉斯·R.和马克·纽曼。2001年，一种快速的节点无关路径算法。圣达菲研究所工作文件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