在搜索最小流量与履行流图的能力 [英] Searching for minimal flow with fulfill capacity in flow graphs

问题描述

我已经修改的最大流量问题的任务。我应该找到满足条件的最小流量（其中f是流量和c是容量）：

I have modified task of maximum flow problems. I should find minimum flow which satisfies condition (where f is flow and c is capacity):

f(u,v) >= c(u,v) 

所以，流动在每个边缘至少容量优势。 （我写能力，但它被重新命名，因为它不再是能力，它的数量必须由流动满足）

So flow at every edge is at least capacity of edge. (I am writing capacity but it was rename because it's no longer capacity, it's count which must be satisfied by flow)

一件事。我有功能MaxFlow这给了我极大的经典流程，我可以调用它一次。

One more thing. I have function MaxFlow which gives me classic maximal flow and I can call it once.

谁能帮我用伪算法？我想对矫正福特Fulkers算法，并改变它适合我的需要，但我不知道在哪里适合该MaxFlow？它如何能帮助我的算法，当我知道图中最大流量？谢谢

Can anyone help me with pseudo algorithm? I am thinking about modifing Ford-Fulkers algorithm and change it for my needs but I am not sure where to fit that MaxFlow? How it can help me with algorithm when I know maximum flow in graph? Thanks

推荐答案

有一个从最大流简单的还原下限，以最大流量：

There is a simple reduction from maximum flow with lower bounds to maximum flow:

的http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

我们的想法是，你所有的饱和边缘。然后，你留下了不平衡的节点。您可以使用最大流算法来解决不平衡。

The idea is that you saturate all edges. Then you are left with imbalanced nodes. You can use a max-flow algorithm to resolve the imbalance.

建设工作原理如下：对于每一个顶点v，定义M（V）：=在入边下界的总和 - 在出边的下界的总和。删除每个原始边缘上界的各个下限和集容量 - 下限（在你的情况，无穷大）

The construction works as follows: For every vertex v, define M(v) := sum of lower bounds on incoming edges - sum of lower bounds on outgoing edges. Remove all lower bounds and set capacity of each original edge to upper bound - lower bound (in your case, infinity).

介绍一种新的超级源S和一个新的超级汇T.添加边（S，V），具有高容量M（五）每个顶点v与M（V）> = 0添加边（V， T）与上部容量-M（ⅴ）为每个顶点v为M（V）其中; 0。

Introduce a new super source S and a new super sink T. Add an edge (S, v) with upper capacity M(v) for every vertex v with M(v) >= 0. Add an edge (v, T) with upper capacity -M(v) for every vertex v with M(v) < 0.

解决导致ST最大流问题。

Solve the resulting S-T maximum flow problem.

最后，除去S和T和原下界添加到流上的每个原边

Finally, remove S and T and add the original lower bound to the flow on every original edge.

这篇关于在搜索最小流量与履行流图的能力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！