在流网络中,证明将一条边分解为两条边所得到的是一个等价的网络。具体来说,假设流网络 $ G $ 包含边 $ (u, v) $,我们以如下方式创建一个新的流网络 $ G’ $:
- 创建一个新结点 $ x $。
- 用新的边 $ (u, x) $ 和 $ (x, v) $ 来替换原来的边 $ (u, v) $。
- 设置容量 $ c(u, x) = c(x, v) = c(u, v) $。
证明 $ G’ $ 中的一个最大流与 $ G $ 中的一个最大流具有相同的值。
在流网络中,证明将一条边分解为两条边所得到的是一个等价的网络。具体来说,假设流网络 $ G $ 包含边 $ (u, v) $,我们以如下方式创建一个新的流网络 $ G’ $:
证明 $ G’ $ 中的一个最大流与 $ G $ 中的一个最大流具有相同的值。