算法问题：转换非整数最大流量到整数最大流量

考虑，我们具有与整数弧容量有向网络中的非整数最大流量。算法问题：转换非整数最大流量到整数最大流量

是否有可能这个流量转换成整数的最大流量的算法？

它的运行时间是多少？

这不是一个家庭作业问题。

2011-04-18 user712882

弧，你的意思是边缘？我想我们假设一个来源和一个目的地？来吧，至少让我们看看你的努力。 – bdares 2011-04-18 06:43:41

我认为这是NP-Hard（只是猜测，应该想想或搜索它） – 2011-04-18 06:48:10

听起来像一个ILP问题，我通常是NP难。 – ChrisWue 2011-04-18 06:54:22

如果你正在寻找一个最大S-T流量（整数）与积分弧能力是不是NP完全问题。也许有一个算法为此目的。你会尝试的是找到一些不存在容量的圆弧。在所有需要此边缘的路径上必须是饱和的边缘。在这里，您将拥有多个具有非积分容量的s-t路径。尝试使积分增加一个，减少另一个没有违反能力。

此外，请看一下本页的算法： http://en.wikipedia.org/wiki/Maximum_flow_problem 所有提到的算法都应该产生积分流。

它还指出积分流量定理： 如果流量网络中的每条边都有积分容量，则存在积分最大流量。

2011-04-18 07:35:26 tgmath

林不知道您convert this flow into an integer maximum flow的意思。如果你有一个非整数最大流量，那当然不可能从一个整数问题得到同样的流量，因为整数图形的解也是整数。

（例如，如果你最大流量为3.5，有没有办法让从整体图形这个最大流量）。

如果你只想解决方案的四舍五入整数图。再解决它，然后你得到了相应的整数解。

PS：无论是整数，也没有非整数最大流量是NP完全问题。他们都在P.

2011-04-18 08:22:59 flolo

他/她提到了整体电弧能力。因此，最大流量不能像3.5。一个弧上的流量可以具有这样的价值。 – tgmath 2011-04-18 08:36:06

是的，这就是为什么我不真正喜欢这个问题。原始海报说他们有一个非整数最大流量。其中一个必须是假的。要么它们在边缘只有整数，那么最大流量也必须是整数，或者它们具有非整数最大流量，但是这些弧段也必须有非整数。 – flolo 2011-04-18 08:47:25

我认为海报会考虑具有整数流量值的流量，但某些弧段具有非整数流量。就像两个单位容量的s-t曲线一样，只有一个弧，两个路径上的流量都是0.5。 – tgmath 2011-04-18 09:29:59

这与AMO书中的练习9.42类似。我认为最好看一下“整数等流问题”。

2013-02-06 17:41:05 Phill

回答