minimum_cut_value#

minimum_cut_value(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]#

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

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

参数：
flowGNetworkX 图

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

_s节点

流的源节点。

_t节点

流的汇节点。

capacity字符串

图 G 的边应具有一个 capacity 属性，用于指示该边可以支持多少流量。如果此属性不存在，则认为该边具有无限容量。默认值：'capacity'。

flow_func函数

一个用于计算有容量图中一对节点之间的最大流的函数。该函数必须接受至少三个参数：一个 Graph 或 Digraph、一个源节点和一个目标节点。并返回一个遵循 NetworkX 约定的残差网络（见 Notes）。如果 flow_func 为 None，则使用默认的最大流函数（preflow_push()）。有关其他算法，请参阅下文。默认函数的选择可能会因版本而异，不应依赖。默认值：None。

kwargs传递给计算最大流函数的

任何其他关键字参数。

返回值：
cut_value整数, 浮点数

最小割的值。

引发：
NetworkXUnbounded

如果图中存在无限容量的路径，则所有割都具有无限容量，函数会引发 NetworkXError。

另请参阅

maximum_flow()
maximum_flow_value()
minimum_cut()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

备注

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

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

对于 R 中的每条边 (u, v)，如果 (u, v) 存在于 G 中，则 R[u][v]['capacity'] 等于它在 G 中的容量，否则为零。如果容量是无限的，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'] 中。仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边到达 t 的可达性诱导了一个最小 s-t 割。

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

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

示例

>>> 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
在本页