graph-algorithm - 使用福特-富尔克森的双向最大流量

Question

我认为这就像最大流问题的无向图版本。

所以对于每条边 a->b，b->a 也是有效的。它的双向。他们共享相同的容量。这意味着如果我在两个顶点 a、b 之间的容量为 10，并且我有从 a 到 b 的流量为 5，那么从 a 到 b 的剩余容量以及从 b 到 a 的剩余容量将是 5。

我对此的解决方案是有一个从 b 到 a 的有向边和另一个从 a 到 b 的有向边。问题是，如果我在残差图中从 a->b 减少残差，我是否仍会增加后向边 b->a 的残差？

Answer 1

是的。在每个具有可用容量的增广路径中，如果从残差图中的 a->b 减少残差，则必须增加后向边 b->a 的残差。它允许流可能在以后“返回”。