Проблема алгоритма: преобразование нецелого максимального потока в целочисленный максимальный поток

Question

Рассмотрим, у нас есть нецелочисленный максимальный поток в направленной сети с емкостью целочисленной дуги.

Существует ли алгоритм, который может преобразовать этот поток в целочисленный максимальный поток?

А каково его время работы?

Это не домашнее задание.

Answer 1

Я не уверен, что вы подразумеваете под convert this flow into an integer maximum flow. Если у вас неинтегальный максимальный поток, то, конечно, невозможно получить тот же поток из интегральной задачи, так как решение целочисленного графа также является интегральным.

(например, если максимальный поток равен 3,5, получить этот максимальный поток из интегрального графика невозможно).

Если вы хотите просто решение, округленный целочисленный граф. Просто решите это снова, и тогда вы получите соответствующее целочисленное решение.

PS: ни целочисленный, ни нецелочисленный максимальный поток не является NP-полным. Они оба в П.

Answer 2

Это похоже на упражнение 9.42 из книги AMO. Я думаю, что лучше взглянуть на "проблему целочисленного равного потока".

Answer 3

Если вы ищете максимальный поток s-t (целое число) с интегральной емкостью дуги, он не является NP-полным. И, может быть, есть алгоритмы для этой цели. Что вы пытаетесь найти, так это найти дуги, которые не насыщены имеющейся емкостью. На всем пути, который принимает это ребро, должно быть ребро, которое насыщено. Здесь у вас будет несколько s-t-путей с нецелой емкостью. Попробуйте сделать интеграл, увеличивая одно, а уменьшая другое без нарушая способности.

Кроме того, взгляните на алгоритмы на этой странице: http://en.wikipedia.org/wiki/Maximum_flow_problem Все упомянутые алгоритмы должны создавать интегральные потоки.

В нем также указана Теорема об интегральном потоке: Если каждое ребро в сети потоков имеет интегральную емкость, то существует интегральный максимальный поток.