all_node_cuts

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

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

此实现基于 Kanevsky 的算法 [1]，用于查找无向图 G 的所有最小尺寸节点割集；即与 G 的节点连通性具有相同基数的节点集合。移除这些节点将使 G 分裂成两个或更多连通分量。

参数:

GNetworkX 图

无向图

k整数

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

flow_func函数

用于执行底层流计算的函数。默认值是 edmonds_karp()。此函数在具有右偏度分布的稀疏图中表现更好。shortest_augmenting_path() 在更密集的图中表现更好。

返回:

cuts节点割集的生成器

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

另请参阅

node_connectivity

edmonds_karp

shortest_augmenting_path

注意

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

参考文献

[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

示例

>>> # A two-dimensional grid graph has 4 cutsets of cardinality 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