minimum_edge_cut

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

返回一组最小基数的边集，移除这些边会使图 G 断开连接。

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

参数:

GNetworkX 图

s节点

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

t节点

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

flow_func函数

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

返回:

cutset集合

如果移除会使 G 断开连接的边集。如果提供了源节点和目标节点，则该集合包含如果移除会破坏源节点和目标节点之间所有路径的边。

另请参阅

minimum_st_edge_cut()

minimum_node_cut()

stoer_wagner()

node_connectivity()

edge_connectivity()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

注意事项

这是基于流的最小边割实现。对于无向图，该算法通过找到图 G 的一个“小”支配集（参见 [1] 中的算法 7），并计算支配集中任意一个节点与支配集内其余节点之间的最大流来实现。这是 [1] 中算法 6 的实现。对于有向图，该算法调用最大流函数 n 次。如果该有向图不是弱连通的，则该函数会引发错误；如果是弱连通的，则返回一个空集。这是 [1] 中算法 8 的实现。

参考文献

[1] (1,2,3)

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

示例

>>> # Platonic icosahedral graph has edge connectivity 5
>>> G = nx.icosahedral_graph()
>>> len(nx.minimum_edge_cut(G))
5

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

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path))
5

如果您指定一对节点（源节点和目标节点）作为参数，此函数将返回局部边连通性的值。

>>> nx.edge_connectivity(G, 3, 7)
5

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