证明了无向图的最大流程和等效的指示图是相等的

Question

有一个无向图 $ g $ 。通过更改每个边缘 $（a，b）$ 在 $ h $ 。=“Math-Container”> $ G $ 到一对定向边缘 $（a，b）$ 和 $（b，a）$ 。如何证明 $ h $ 中的最大流量等于 $ g $ 中的最大流量？

我真的没有想到如何启动它。我只知道我可以在 $ h $ 上使用ford-fulkerson，并更新反向边缘，使得 $ f（a，b）+ f（b，a）= c（a，b）$ 但这是它。

Answer 1

如果 $ f_g $ 是 $ g $ 的有效流程，那么存在有效的流量 $ f_h $ for $ h $ 这样 $ | f_g |= | f_h | $ 。这是真的，因为总是一个流 $ f'_g $ $ g $ 这样的 $ | f'_g |= | F_G | $ 且没有边缘在 $ f'_g $ 的流分解中的两个方向上都遍历。如果某些边缘 $（u，v）$ 由 $ x $ 从 $ u $ 到 $ v $ 和 $ y \ le x $ 流量单位 $ v $ 到 $ u $ 然后您可以重新定义流量只发送 $ xy $ 流量从 $ u $ 到 $ V $ 。如果 $（u，v）$ 从 $ u $ 到 $ V $ 然后您可以定义 $ f_h（u，v）= f'_g（u，v）$ 和 $ f_h（v，u）= 0 $ 。 （如果 $（u，v）$ 未使用，则 $ f_h（u，v）= f_h（v，u）= 0 $ ）。

如果 $ f_h $ 是 $ h $ 的有效流程，那么存在有效的流量 $ f_g $ for $ g $ 这样 $ | f_h |= | f_g | $ 。 请注意，如果 $ f_h $ 使用两个 $（u，v）$ 和 $（v，u）$ （假设wlog，那个 $ f_h（u，v）\ ge f_h（v，u）$ ）然后流 $ f'_h $ 由 $ f'_h（u，v）= f_h（u，v ） - f_h（v，u）$ ， $ f'_h（v，u）= 0 $ ，和 $ f'_h（x，y）= f_h（x，y）$ for $（x，y）\ not \ in \ {（u，v ），（v，u）\} $ 也是 $ h $ 和 $ |的有效流f'_h |= | f_h | $ 。这表明您可以定义 $ f_g（u，v）= f'_h（u，v）$ 。