all_node_cuts

all_node_cuts(G, k=None, flow_func=None)

返回无向图 G 的所有最小 k 割集。

此实现基于 Kanevsky 的算法 [1]，用于找到无向图 G 的所有最小尺寸节点割集；即基数等于 G 的节点连通性的节点集合（或集合）。因此，如果移除这些节点，将使 G 分成两个或更多个连通分量。

Parameters:

GNetworkX 图

无向图

k整数

输入图的节点连通性。如果 k 为 None，则进行计算。默认值：None。

flow_func函数

执行底层流计算的函数。默认值为 edmonds_karp() 。该函数在具有右尾度分布的稀疏图中表现更好。shortest_augmenting_path() 将在更密集的图中表现更好。

Returns:

cuts节点割集生成器

每个节点割集的基数等于输入图的节点连通性。

See also

node_connectivity

edmonds_karp

shortest_augmenting_path

Notes

此实现基于在图中找到所有最小尺寸分离顶点集的顺序算法 [1]。主要思想是通过在一组最高度节点和图中所有其他非相邻节点之间进行局部最大流计算来计算最小割。一旦找到最小割，我们就在高度节点和局部最大流计算的目标节点之间添加一条边，以确保我们不会再次找到该最小割。

References

[1] (1,2)

Kanevsky, A. (1993). Finding all minimum-size separating vertex sets in a graph. Networks 23(6), 533–541. http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract

Examples

>>> # 二维网格图有 4 个基数为 2 的割集
>>> G = nx.grid_2d_graph(5, 5)
>>> cutsets = list(nx.all_node_cuts(G))
>>> len(cutsets)
4
>>> all(2 == len(cutset) for cutset in cutsets)
True
>>> nx.node_connectivity(G)
2