Метод Форда-Фалкерсона

Теорема Форда и Фалкерсона о связи минимального потока и максимального разреза позволяет обосновать следующий общий метод решения задачи о максимальном потоке. Идея состоит в том, что произвольный поток в сети можно дополнить до максимального. По произвольному потоку f рассмотрим «остаточную сеть» этого потока. Ребрами сети будут исходные ребра графа с пропускной способностью cf(uv) = c(uv) – f(uv), а также обратные ребра с пропускной способностью cf(uv) = f(vu). Метод Форда и Фалкерсона состоит в нахождении в остаточной сети произвольного пути из источника в сток, и дополнении существующего потока (изначально нулевого) вдоль этого пути. Теорема о максимальном потоке и минимальном разрезе позволяет обосновать тот факт, что в случае если такого пути не существует, то поток является максимальным.

В оригинале этот метод был сформулирован в 1956 без использования «остаточной сети», однако его описание в терминах обычной сети очень громоздко, поэтому мы его здесь не приводим. Термин «остаточная сеть» появился позднее, и в настоящее время является одним из основных инструментов исследователей в области потоков.

Алгоритм Эдмондса-Карпа

Однако, в общем случае метод Форда и Фалкерсона не является корректным. Существует пример сети с иррациональными пропускными способностями, для которой алгоритм Форда и Фалкерсона не остановится (будет работать «бесконечное время»). Для сетей с целочисленными пропускными способностями время работы составляется O(UVE), где U – максимальная пропускная способность, V – количество вершин и E количество ребер в сети. Сети с рациональными пропускными способностями могут быть сведены к целочисленному случаю путем домножения на наибольший общий делитель знаменателей всех дробей.

В 1969 году Эдмондсом и Карпом была предложена модификация этого алгоритма, позволяющая получить гарантированное время O(VE^2) работы алгоритма следующим способом: на каждом шаге путь из источника в сток нужно выбирать не произвольный, а кратчайший. В этом случае удается доказать оценку O(VE) на число фаз работы алгоритма. Искомая оценка следует из того, что в неориентированном графе возможно найти расстояние между двумя вершинами за время O(E).

Дальнейшие улучшения алгоритма построения максимального потока

В 1970 году Дициц опубликовал принципиально новый алгоритм нахождения максимального потока, основанный на поиске псевдомаксимального ("блокирующего") потока во вспомогательной сети.

Блокирующий поток – это поток, величину которого невозможно улучшить путем лишь увеличения потока вдоль отдельных ребер. Строить такой поток Диниц предлагал при помощи классического алгоритма поиска «в ширину».

Другое направление исследований – улучшенные алгоритмы для нахождения максимального потока в сети с целочисленными пропускными способностями. Метод, предложенный Эдмондсом и Карпом в 1972 году (и независимо Диницом в 1973) получил название метода масштабирования пропускных способностей (capacity scaling). Идея метода проста: поток в сети с пропускными способностями, равными половине пропускных способностей исходной сети, мы легко можем получить поток в исходной сети путем умножения его значения на 2. Отдельно нужно обрабатывать ребра с нечетными пропускными способностями. Полученный алгоритм имеет время работы O(nm log U), где n – число вершин сети, m – число ребер, U – максимальная пропускная способность.

Карзанову в 1974г удалось, с помощью модификации алгоритма Диница, добиться оценки быстродействия O(n^3). Им также впервые было введено понятие “предпотока”. В 1978г Малхотри, Кумару м Махешвари (Malhotra, Kumar, Maheshwari) удалось повторить этот результат, однако их алгоритм отличался от алгоритма Карзанова.

Лучший из известных на сегодняшний день алгоритмов был предложен в 1997 году Гольдбергом и Рао (Goldberg, Rao). В качестве вспомогательной процедуры алгоритм использует структуру данных, полученную Гольдбергом и Тарьяном (Tarjan).
В заключение приведем сводную хронологическую таблицу результатов, полученных для задачи о максимальном потоке (везде далее n – число вершин сети, m – число ребер, U – максимальная пропускная способность ребер сети)

Глава 2. Теория паросочетаний