min - 有向图中的最小割/最大流

Question

我有一个有向图

首先，我使用了 Ford-Fulkerson 算法来增加网络的流量。当我标记顶点时，我看到路径上的流：s->a->b->d->t可以增加一个，因此图形更改为：

我知道在搜索最大流量时，您需要将连接最小切割和图形外部部分的边的所有容量相加。我的最小切割包含 vertices: s, a, c，所以当我将所有边加起来时c(G, !G) = 3 + 2 +2 + 1，这比 flow to t5 要大得多。

我做错了什么，我搞砸了FF还是最小化了？

Answer 1

你的最小削减不是s, a, c，而是s, a, b, c。它的容量是5您计算的最大流量。

您可以使用残差网络的定义找到最小割。s回想一下，当残差网络之间和t残差网络中没有路径时，Ford-Fulkerson 终止。

最小割(S,T)定义为

S = { v | there exists a path from s to v in the residual network }

在您的图中，由于带有权重的流，该节点b可以从c残差网络中到达。b->c3