Ford-Fulkerson算法的一种改进

Question

假设我们重新定义剩余网络，不允许边进入s。认为福特-富尔克森的程序仍然正确地计算了最大流量。

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

s到x_1导线到y导线到x_2到s到x_3导线到t

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

问题来自Cormen等人对算法的介绍。

Answer 1

我认为你的直觉已经足够证明了。让我们考虑两个图：在图G1中，我们允许边变成s，在图G2中我们不允许。

现在，假设Ford Fulkerson算法在G1中找到一个更大的流，那么它在G2中找到了。由于G2中的所有增广路径在G1中也是有效的，我们可以在两个图上尽可能长地使用相同的增广路径，然后获得剩余网络的状态，其中G1中有一条增广路径，但G2中没有。

然而，正如你所指出的，任何在G1中有效的增广路径在G2中也是有效的，前提是我们删除最后一次访问s之前的所有边。因此，我们的假设是错误的，这种情况不可能存在——福特·富尔克森将在G1和G2上产生相同的输出。