最小割#

minimum_cut(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 约定的残差网络（参见说明）。如果 flow_func 为 None，则使用默认的最大流函数 (preflow_push())。请参见下方了解其他算法。默认函数的选择可能因版本而异，不应依赖于此。默认值：None。
kwargs传递给计算最大流函数的任何其他关键字参数。: 计算最大流。

返回:

cut_value整数, 浮点数: 最小割的值。
partition一对节点集: 定义最小割的节点划分。

引发:

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

另请参见

maximum_flow()
maximum_flow_value()
minimum_cut_value()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

说明

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

输入图 G 的残差网络 R 具有与 G 相同的节点。R 是一个 DiGraph，当且仅当 (u, v) 不是自环且 (u, v) 和 (v, u) 中至少有一个存在于 G 中时，它包含一对边 (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'] 的边 (u, v) 可达 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 计算最小割的值和节点划分
>>> cut_value, partition = nx.minimum_cut(G, "x", "y")
>>> reachable, non_reachable = partition


这里的 ‘partition’ 是一个元组，包含定义最小割的两个节点集。你可以按如下方式计算导致最小割的边割集：
>>> cutset = set()
>>> for u, nbrs in ((n, G[n]) for n in reachable):
...     cutset.update((u, v) for v in nbrs if v in non_reachable)
>>> print(sorted(cutset))
[('c', 'y'), ('x', 'b')]
>>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)
True


你还可以通过使用 flow_func 参数来使用其他算法计算最小割。
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True