假设我们重新定义残差网络以禁止边缘进入
s。认为FORD-FULKERSON程序仍然正确地计算了最大流量。
我在想，当我们增加一条路径时，反向边缘的剩余容量会增加，如果需要，可以用来减少该边缘的流量（但总体上增加网络流量）。因此，如果我们不允许边缘进入s，这意味着我们不允许减少边缘s- x中的流量（x是s的相邻节点）。因此，在我们允许边缘进入s的情况下，我们可以有一个类似的循环
s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t
但是，如果我们再次不允许边进入s，我们可以找到与out循环相同的路径。以上都是直观的想法，但我想要一个正式的证明。
问题来自Cormen等人的算法简介。
我认为你的直观想法已经足够证明了。让我们考虑两个图：在图G1中，我们允许边进入s，而在图G2中，我们不允许。
现在，假设Ford-Fulkerson算法在G1中发现了比在G2中更大的流量。由于G2中的所有扩充路径在G1中也是有效的，我们可以在两个图上尽可能长时间地使用相同的扩充路径，然后获得残差网络的状态，其中在G1中有扩充路径，但在G2中没有。
然而，正如你所指出的，任何在G1中有效的扩充路径在G2中也是有效的，前提是我们去除了最后一次访问s之前的所有边。因此，我们的假设是错误的，这种情况不可能存在——Ford-Fulkerson将在G1和G2上产生相同的输出。