流网络等价性证明:边分解后的最大流保持不变-问题描述

时间:2024-12-11 07:16:33

在流网络中,证明将一条边分解为两条边所得到的是一个等价的网络。具体来说,假设流网络 $ 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 $ 中的一个最大流具有相同的值。

在这里插入图片描述