Поиск минимального потока с полной производительностью в потоковых графиках

Question

Я изменил задачу о максимальных проблемах потока. Я должен найти минимальный поток, который удовлетворяет условию (где f - поток, а c - емкость):

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

Таким образом, поток на каждом ребре - это, по крайней мере, емкость ребра. (Я пишу емкость, но это было переименовано, потому что это больше не емкость, это количество, которое должно быть удовлетворено потоком)

Еще кое-что. У меня есть функция MaxFlow, которая дает мне классический максимальный поток, и я могу вызвать его один раз.

Может кто-нибудь помочь мне с псевдо-алгоритмом? Я думаю о том, чтобы модифицировать алгоритм Форда-Фулкерса и изменить его под свои нужды, но я не уверен, куда подойдет этот MaxFlow? Как это может помочь мне с алгоритмом, когда я знаю максимальный поток в графе? Спасибо

Answer 1

Существует простое сокращение от максимального потока с нижними границами до максимального потока:

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

Идея в том, что вы насыщаете все края. Тогда вы остаетесь с несбалансированными узлами. Вы можете использовать алгоритм максимального потока для устранения дисбаланса.

Конструкция работает следующим образом: Для каждой вершины v определите M(v):= сумма нижних границ на входящих ребрах - сумма нижних границ на исходящих ребрах. Удалите все нижние границы и установите емкость каждого исходного ребра в верхнюю границу - нижнюю границу (в вашем случае, бесконечность).

Введем новый суперисточник S и новый супертонок T. Добавьте ребро (S, v) с максимальной емкостью M (v) для каждой вершины v с M(v) >= 0. Добавьте ребро (v, T) с верхняя емкость -M(v) для каждой вершины v с M(v) < 0.

Решите полученную проблему с максимальным расходом ST.

Наконец, удалите S и T и добавьте исходную нижнюю границу к потоку на каждом исходном ребре.