Задачи о максимальном потоке

Рассмотрим сеть из (n + 1) вершины. Пусть каждой дуге поставлено в соответствие число , называемое пропускной способностью дуги (i; j).

Потоком x в сети называется совокупность чисел { }, где - поток по дуге (i; j), удовлетворяющих условиям , ,

Величиной потока x называется

Задача о максимальном потоке заключается в определении потока максимальной величины.

Разрезом W в сети называется любое множество вершин, обязательно содержащее выход и не содержащее вход. Пропускной способностью C (W) разреза W называется сумма пропускных способностей дуг, заходящих в разрез.

Известно, что величина любого потока не превышает пропускной способности любого разреза (теорема Форда-Фалкерсона).

Следовательно, если удастся найти поток, величина которого равна пропускной способности некоторого разреза, то этот поток максимален, а разрез минимален.

Алгоритм 7 (алгоритм Форда-Фалкерсона). Применение алгоритма проиллюстрируем примером сети, приведенной на рисунке 1, в которой пропускные способности всех дуг равны единице.

Шаг 0. Берем произвольный поток (например, поток ). Помечаем начальную вершину индексом «0». Обозначим Z – множество помеченных вершин.

Общий шаг.Первое действие. Помечаем вершину j индексом + i, если, во-первых, существует дуга (i; j), и, во-вторых,

Если в результате этого типа пометок мы пометили выход, то поток можно увеличить хотя бы на единицу (если – целые числа). Двигаясь обратно, можно найти путь, поток по которому можно увеличить. Однако, как видно из примера, этого недостаточно для нахождения максимального потока.

рис. 1 Поиск максимального потока

Второе действие. Помечаем вершину i индексом -j, если, во-первых, существует дуга (j; i), и, во-вторых

(легко видеть, что пометки первого типа увеличивают поток по дуге, а пометки второго типа – уменьшают).

Если в результате этого типа пометок мы пометили выход, то поток можно увеличить. Двигаясь обратно, можно найти цепь, в которой каждая вершина помечена номером предыдущей (знак пометки не важен).

Рассмотрим цепь , приведенную на рисунке 1. Полученные в результате второго действия потоки обозначены жирным шрифтом.

Критерий остановки алгоритма следующий: если, применяя пометки обоих типов, вершину n пометить не удалось, то полученный поток имеет максимальную величину.