问题描述

在流网络中，证明将一条边分解为两条边所得到的是一个等价的网络。具体来说，假设流网络 $ G $ 包含边 $ (u, v) $，我们以如下方式创建一个新的流网络 $ G’ $：

1. 创建一个新结点 $ x $。
2. 用新的边 $ (u, x) $ 和 $ (x, v) $ 来替换原来的边 $ (u, v) $。
3. 设置容量 $ c(u, x) = c(x, v) = c(u, v) $。

证明 $ G’ $ 中的一个最大流与 $ G $ 中的一个最大流具有相同的值。

证明思路

1. 构造流守恒：我们需要证明在任何流量分配下，通过边 $ (u, v) $ 的流量在 $ G’ $ 中可以等价地通过边 $ (u, x) $ 和 $ (x, v) $。
2. 最大流-最小割定理：利用最大流-最小割定理，证明两个网络的最小割相同，从而证明最大流相同。

伪代码

以下是伪代码来描述如何转换网络并证明最大流相等：