Доказательство. Пусть по сети течет поток X. Поток из i в j можно увеличить на величину d ij = xji +(αij - xij), погасив поток по обратной дуге (j,i) и послав дополнительный поток по прямой дуге (i,j). Ориентированную дугу назовем аугментальной (допускающей увеличение потока), если d ij > 0. По крайней мере одна из дуг (i,j) и (j,i) будет аугментальной при любом потоке X. Построим ориентированную A‑сеть из аугментальных дуг и найдем в ней аугментальную цепь L дуг из s в t, решив задачу на достижимость. Сначала включим вершину S. Из включенной вершины i можно включить любую соседнюю вершину j. Алгоритм Форда-Фалкерсона включает вершины в произвольном порядке до тех пор, пока что-либо можно включить. Процесс заканчивается, когда включена вершина t. Обратным ходом находим цепь из s в t.
В основной сети пошлем по цепи L дополнительный поток величины d =. Суммарный поток – допустимый, т.к. 0 £ x ij £ a ij и выполнены уравнения баланса. Затем все включения отменяем и повторяем все сначала. Алгоритм останавливается, когда для разреза R(W) все d ij = 0, т.е. все обратные дуги нулевые, а все прямые - насыщены Þ пропускные способности дуг равны потокам. Þ По теореме 1 имеем F (X) = a (R (W )) Þ . ■
Замечание. Если a ij для всех дуг – целые числа, то d- целое и на каждой итерации поток увеличивается как минимум на 1 Þ через конечное число шагов алгоритм остановится. Но он может не остановиться, если a ij иррациональны.
Пример 1. При плохом выборе аугментальных цепочек АФФ может сделать 2000 итераций, т.е. трудоемкость зависит от ПС, а не от числа вершин. Эдмондсон и Карп насыщали аугментальные цепи с минимальным числом ребер.
Пример 2. Этап 1: ОЧИСТКА. Осталась цепочка.
Зависшие вершины – удаляем сразу. d = F =1.
Этап 2:
d 65 = x56 +(α65 - x65) =1+1=2
d = 2, F =3.
Этап 3:
Fmax = 3. Мин. разрез показан волнистой линией.
Отличия АФФ от АДК. 1) АФФ недетерминирован и АДК уточняет его.
2) Итерации АДК разделены на 2 типа: этапы и шаги. 3) АДК насыщает не цепь, а слоистую сеть Þ на след.итерации отключено не ребро (одно из n·n), а вершина (одна из n на весь этап). 4) Умное проталкивание потока со слоя на слой с однократным за шаг выталкиванием потока из любой вершины.
№23. Алгоритм Диница – Карзанова (АДК).
Описание алгоритма дадим на примере.На ребрахсети S до запятой стоят пропускные способности, после запятой – сумма потоков на этапах.
а) Основной цикл идет по этапам:
строим слоистую сеть всех кратчайших путей и насыщаем ее за O(n2) операций. Максимальный поток строится за n этапов с общей трудоемкостью O(n3).
Этап №1: Для текущего потока x строим слоистую сеть S ¢(x). Поиск «сначала вширь», структура – очередь вершинs / 1, 2 / 3, 4 / 5, 6 / t, разбитых на слои. На слой 1 помещаем вершину s, на следующий слой - вершины, достижимые из вершин предыдущего слоя с помощью одного ребра, для которого a¢ij = (aij - xij) + xji > 0. Только такие ориентированные! ребра, идущие с предыдущего слоя на следующий, включаются в сеть S ¢(x) с пропускными способностями a¢ij .
Шаг1. k=2, ƒ=F=6. Для всех вершин i ≠ s, t найдем характеристики:
ОЧИСТКА: Если ƒ = 0, то вершина k – зависшая, пускать нечего и можно сразу удалить вершину k. Þ На последнем слое останется только одна вершина - t.
Принцип ТЯНИ-ТОЛКАЯ: если из вершины k = argmin ПСВ(i) толкать в разные стороны поток ƒ = ПСВ(k) со слоя на слой, то все придет слева в s (на слое 0 одна вершина s), а справа – в t (после ОЧИСТКИ там осталась одна вершина t).
Принцип НАКОПЛЕНИЯ: за счет послойной обработки дуг в процессе протягивания-проталкивания потока все входящие в вершину потоки сначала суммируются, а затем выталкиваются из вершины 1 раз.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.