3

假设我们重新定义残差网络以禁止边缘进入s。认为程序 FORD-FULKESON 仍然正确地计算了最大流量。

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

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

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

问题来自Cormen 等人的《算法导论》。

4

1 回答 1

0

我认为您的直观想法已经足以证明。让我们考虑两个图：在图 G1 中，我们允许边进入 s，而在图 G2 中，我们不允许。

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

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

于 2012-10-04T16:17:46.827 回答