算法問題：轉換非整數最大流量到整數最大流量

考慮，我們具有與整數弧容量有向網絡中的非整數最大流量。算法問題：轉換非整數最大流量到整數最大流量

是否有可能這個流量轉換成整數的最大流量的算法？

它的運行時間是多少？

這不是一個家庭作業問題。

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

回答