使用ford-fulkerson的双向最大流量

Question

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

因此，对于每条边a-> b，b-> a也是有效的。它的双向性。他们拥有同样的能力。 这意味着如果我有两个顶点a，b和a之间的容量10，并且我有一个从a到b的流量，其成本为5，那么从a到b的剩余容量将是5以及从b到a的剩余容量。

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

Answer 1

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