minimum_node_cut

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

返回一个最小基数的节点集合，该集合可以断开图G。

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

Parameters:

GNetworkX图

s节点

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

t节点

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

flow_func函数

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

Returns:

cutset集合

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

See also

minimum_st_node_cut()

minimum_cut()

minimum_edge_cut()

stoer_wagner()

node_connectivity()

edge_connectivity()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

Notes

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

References

[1]

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Examples

>>> # 柏拉图正二十面体图的节点连通度为5
>>> G = nx.icosahedral_graph()
>>> node_cut = nx.minimum_node_cut(G)
>>> len(node_cut)
5

您可以使用替代流算法进行底层最大流计算。在密集网络中，算法：meth： shortest_augmenting_path 通常比默认的：meth： edmonds_karp 表现更好，后者在稀疏网络和高度倾斜的度分布中速度更快。替代流函数需要从流包中显式导入。

>>> 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割集，建议您重用最大流计算中使用的数据结构。详见：meth： minimum_st_node_cut 。