Ford-Fulkerson 方法的修改
Modification in the Ford-Fulkerson method
我想在流网络 G 的所有最小割中找到
积分容量，包含最少边数的容量。我们怎样才能
修改 G 的容量以创建一个新的流网络 G'，其中任何最小值
G'中的割是G中边数最少的最小割。
来源 - Cormen
假设图 G 有 n 个顶点。
我们定义G'中弧e'对应G中弧e的容量为c(e') = c(e) * n + 1.
因此 G' 中的切割值正好是 n 乘以 G 中的切割值 + 切割中的边数。
假设我们现在在 G' 中有一个最小切割，值为 n * x + a。这意味着 G 中的切割值是 x。如果 G 中存在具有较小值 y < x 的切割，则该切割的值为 n * y + b <= n * (y+1) <= n * x < n * x + a，这与值为 n * x + a 的切割相矛盾在 G' 中最小。我们刚刚证明了 G' 中的每个最小割也是 G 中的最小割。但随后得出 G' 中的最小割是 G 中的最小割，并且在 G.
中具有所有最小割的最小边数
我想在流网络 G 的所有最小割中找到 积分容量，包含最少边数的容量。我们怎样才能 修改 G 的容量以创建一个新的流网络 G'，其中任何最小值 G'中的割是G中边数最少的最小割。 来源 - Cormen
假设图 G 有 n 个顶点。
我们定义G'中弧e'对应G中弧e的容量为c(e') = c(e) * n + 1.
因此 G' 中的切割值正好是 n 乘以 G 中的切割值 + 切割中的边数。
假设我们现在在 G' 中有一个最小切割，值为 n * x + a。这意味着 G 中的切割值是 x。如果 G 中存在具有较小值 y < x 的切割，则该切割的值为 n * y + b <= n * (y+1) <= n * x < n * x + a，这与值为 n * x + a 的切割相矛盾在 G' 中最小。我们刚刚证明了 G' 中的每个最小割也是 G 中的最小割。但随后得出 G' 中的最小割是 G 中的最小割，并且在 G.