algorithm - Ford Fulkerson 算法的变体

Question

Suppose that we redefine the residual network to disallow edges into s. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.

我在想，当我们增加一条路径时，反向边缘的剩余容量会增加，并且可以在需要时用于减少该边缘的流量(但总体上会增加网络流量)。因此，如果我们不允许边缘进入 s，这意味着我们不允许边缘 s-x 中的流量减少(x 是到的相邻节点s)。所以在我们允许边进入 s 的情况下，我们可以有一个类似

的循环

s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t

但是如果我们再次禁止边进入s，我们可以在没有循环的情况下找到相同的路径。以上都是直观的想法，但我想要一个正式的证明。

问题来自 Cormen 等人的Introduction to Algorithms。

Answer 1

我认为你的直觉想法已经足够证明了。让我们考虑两个图:在图 G1 中我们允许边进入 s，而在图 G2 中我们不允许。

现在，假设 Ford-Fulkerson 算法在 G1 中发现了比在 G2 中更大的流。由于 G2 中的所有增广路径在 G1 中也有效，我们可以尽可能长时间地在两个图上使用相同的增广路径，然后为残差网络获得一个状态，其中 G1 中有增广路径，但在 G1 中没有G2.

但是，正如您所指出的，任何在 G1 中有效的增广路径在 G2 中也同样有效，前提是我们删除了最后一次访问 s 之前出现的每条边。因此我们的假设是错误的，这种情况不可能存在——Ford-Fulkerson 将在 G1 和 G2 上产生相同的输出。