minimum_node_cut

minimum_node_cut(G, s=None, t=None, flow_func=None)

返回 G 的最小基数节点集，该节点集断开了 G。

如果提供了源节点和目标节点，此函数返回最小基数的节点集，移除这些节点将破坏 G 中源节点和目标节点之间的所有路径。如果未提供，则返回断开 G 的最小基数节点集。

参数:

GNetworkX 图

s节点

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

t节点

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

flow_func函数

一个用于计算一对节点之间最大流的函数。该函数必须至少接受三个参数：一个有向图、一个源节点和一个目标节点。并返回一个遵循 NetworkX 约定的残量网络（详见 maximum_flow()）。如果 flow_func 为 None，则使用默认的最大流函数 (edmonds_karp())。详见下方说明。默认函数的选择可能因版本而异，不应依赖于此。默认值：None。

返回:

cutset集合

一个节点集合，如果移除这些节点，将断开 G。如果提供了源节点和目标节点，则该集合包含移除后将破坏源节点和目标节点之间所有路径的节点。

另请参阅

minimum_st_node_cut()

minimum_cut()

minimum_edge_cut()

stoer_wagner()

node_connectivity()

edge_connectivity()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

说明

这是基于流的最小节点割实现。该算法通过求解一系列最大流计算来确定辅助有向网络上最小割的容量，该容量对应于 G 的最小节点割。它处理有向图和无向图。此实现基于 [1] 中的算法 11。

参考文献

[1]

Abdol-Hossein Esfahanian. 连通性算法. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

示例

>>> # Platonic icosahedral graph has node connectivity 5
>>> G = nx.icosahedral_graph()
>>> node_cut = nx.minimum_node_cut(G)
>>> len(node_cut)
5

您可以使用替代的流算法来进行底层最大流计算。在稠密网络中，算法 shortest_augmenting_path() 通常比默认的 edmonds_karp() 表现更好，后者对于具有高度偏斜度分布的稀疏网络更快。必须从 flow 包中显式导入替代的流函数。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> node_cut == nx.minimum_node_cut(G, flow_func=shortest_augmenting_path)
True

如果您指定一对节点（源节点和目标节点）作为参数，此函数将返回一个局部 st 节点割。

>>> len(nx.minimum_node_cut(G, 3, 7))
5

如果您需要在同一图上对不同节点对执行多次局部 st 割计算，建议您重用最大流计算中使用的数据结构。详见 minimum_st_node_cut()。