minimum_cut_value

minimum_cut_value(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)

计算最小 (s, t)-割的值。

使用最大流最小割定理，即最小容量割的容量等于最大流的流量值。

Parameters:

flowGNetworkX 图

图的边预期具有名为 ‘capacity’ 的属性。如果此属性不存在，则认为该边具有无限容量。

_s节点

流的源节点。

_t节点

流的汇节点。

capacity字符串

图 G 的边预期具有一个表示边支持流量的 capacity 属性。如果此属性不存在，则认为该边具有无限容量。默认值：’capacity’。

flow_func函数

用于计算容量图中一对节点之间最大流的函数。该函数至少需要接受三个参数：图或有向图、源节点和目标节点。并返回遵循 NetworkX 约定的残余网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（preflow_push() ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。

kwargs任何其他关键字参数将传递给计算最大流的函数。

Returns:

cut_value整数, 浮点数

最小割的值。

Raises:

NetworkXUnbounded

如果图具有无限容量的路径，所有割都具有无限容量，函数将引发 NetworkXError。

See also

maximum_flow()

maximum_flow_value()

minimum_cut()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

Notes

flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残余网络：

输入图 G 的残余网络 R 具有与 G 相同的节点。R 是一个有向图，如果 (u, v) 不是自环，并且 (u, v) 和 (v, u) 中至少有一个存在于 G 中，则包含一对边 (u, v) 和 (v, u) 。

对于 R 中的每条边 (u, v) ，R[u][v]['capacity'] 等于 G 中 (u, v) 的容量（如果存在）或零。如果容量是无限的，R[u][v]['capacity'] 将具有一个不影响问题解决方案的高任意有限值。该值存储在 R.graph['inf'] 中。对于 R 中的每条边 (u, v) ，R[u][v]['flow'] 表示 (u, v) 的流函数，并满足 R[u][v]['flow'] == -R[v][u]['flow'] 。

定义为流入汇 t 的总流量的流值存储在 R.graph['flow_value'] 中。仅使用边 (u, v) 且 R[u][v]['flow'] < R[u][v]['capacity'] 可达 t 的可达性诱导出一个最小 s -t 割。

特定算法可能会在 R 中存储额外数据。

该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，它可以选择性地终止算法。

Examples

>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)

minimum_cut_value 仅计算最小割的值：

>>> cut_value = nx.minimum_cut_value(G, "x", "y")
>>> cut_value
3.0

您还可以使用 flow_func 参数使用替代算法计算最小割。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut_value(
...     G, "x", "y", flow_func=shortest_augmenting_path
... )
True