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

Потоком х в сети называется совокупность чисел {xij}, где xij - поток по дуге (i; j), удовлетворяющих условиям 0 i, j = 0,n, Z х^ = Z хш , i Ф 0, n.

jk

F(x) = Z x0i = Z Xin .

ii

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

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

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

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

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

Шаг 0. Берем произвольный поток (например, поток xo1 = x12 = x25 = 1). Помечаем начальную вершину индексом «0».

Обозначим Z - множество помеченных вершин.

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

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

Рис. 3. Поиск максимального потока

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

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

Рассмотрим цепь / = (0; 3; 2; 1; 4; 5), приведенную на рисун-ке 3. Полученные в результате второго действия потоки обозначены жирным шрифтом.

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