b) Цикл внутри этапа по шагам: проталкиваем из вершины k = argmin ПСВ(i) поток ƒ = ПСВ(k) в разные стороны со слоя на слой, пока слева поток не дойдет до s, а справа - до t. Проталкивание из k в s называют протягиванием из s в k. На пройденных ребрах величину потока вычитаем из вх и выхПСВ. Вершину k удаляем и проводим очистку S ¢(x). При этом поток по удаляемым ребрам заносим в основную сеть, а их остаточные ПС вычитаем из соответствующих ПСВ.
Этап 2: f=1, F=15
Слоистая сеть является цепью Þ min ПСВ = d алгоритма Форда-Фалкерсона, вычислять ПСВ не надо. У нас цепь, d = 1 Þ сразу переносим поток в сеть S.
Этап 3: W = {s,1,2,4}. Больше включить ни-чего нельзя. Величина текущего потока равна сумме пропускных способностей ребер разреза R(W): 15 = 4+3+1+3+4 Þ поток – максимален, а разрез – минимален.
Трудоемкость: Докажем сначала, что любой этап имеет трудоемкость N 2.
a) построение слоистой сети и вычисление пропускных способностей всех ребер и вершин (ПСВ) ~ числу ребер ~ O(N 2)
b) на каждом шаге основного цикла:
1). Находим вершину с min ПСВ ~ N
2). Протянуть и протолкнуть ~ О(числа ребер) ~ O(N 2)
3). Удаляем вершину ~ O(N) вместе с очисткой. Результаты шага переносим в основной граф при удалении ребра из слоистой сети.
При пропускании любого потока по любой дуге слоистой сети мы вешаем на ней один флаг: если дугу насытили, то – красный, иначе – зеленый. На каждом шаге мы тянем-толкаем поток из вершины kволновым алгоритмом, т.е. со слоя на слой. При этом прийти в промежуточную вершину можно по многим дугам с разными флагами на них, а при выходе мы вешаем красные флаги до тех пор, пока нам не удастся вытолкнуть весь остаток потока, и тогда вешаем зеленый флаг. Т.к. на шаге поток из любой вершины выталкивается 1 раз, а число шагов на этапе £ N (на каждом шаге удаляется вершина), Þ число зеленых флагов за этап = N´N = N 2. Число красных флагов за этап £ числа дуг (по красной дуге поток не пускаем).
Трудоемкость этапа определяется общим числом красных и зеленых флагов ~ O(N 2), а число этапов < N (т.к. номер слоя, содержащий вершину t, строго возрастает от этапа к этапу). Þ Общая трудоемкость алгоритма = O(N 3).
Иллюстрацию такой работы алгоритма дает в примере шаг 1 этапа 1: при выталкивании потока величины 6 из вершины 2 мы вешаем один красный флаг на ребре (2,3) и один зеленый на ребре (2,4). При обработке вершины 5 на этом же шаге поток суммируется по всем входящим в нее ребрам и выталкивается из вершины 5 с одним!!! зеленым флагом.
№24. Минимальный разрез в графе за O(n·|E|): алгоритм Поддерюгина.
Найти минимальный разрез в графе можно с трудоемкостью O(n5), выполнив алгоритм Диница-Карзанова для всех пар вершин Sи T. Алгоритм Поддерюгина решает эту же задачу за O(n | E |): на i-том этапе ищется по шагам максимальный поток в вершину с номером i+1 из объединения Uвсех вершин с номерами j £ i.
Шаг А) Пускаем поток по всем прямым ребрам из U в вершину с номером i+1.
Шаг Б) Пускаем поток по всем путям длины 2 из U в вершину с номером i+1. Для этого строим пересечение списков соседей объединения и в-ны i+1.
Шаг В) Пускаем поток по всем путям длины ³ 3 из U в вершину с номером i+1, удалив сначала насыщенные ребра. Строим слоистую сеть, используя обычный поиск сначала вширь (как в алгоритмах Прима и Дейкстры).
Пример.
Этап 1. А) Есть 1 прямой путь из U = {1} в 2. fА = 1.
Б) SU = {2,3,4}; S2 = {1,3,5}; S1 Ç S2 = {3}; fБ = 1.
В) W ={1 | 4 | 3,8 | 6,7 | 5 | 2}; fВ = 1.
W1 ={1}. F1 = 3.
Этап 2. А) Есть 2 прямых пути из U = {1,2} в 3. fА = 2.
Б) SU = {3,4,5}; S3 = {1,2,4}; SU Ç S3 = {3}; fБ = 1.
В) W2 ={1,2 | 5 | 6,7 | 8 | 4}; fВ = 0. F2 = 3.
Этап 3. А) Есть 2 прямых пути из U = {1,2,3} в 4. fА = 2.
Б) SU = {4,5}; S4 = {1,3,8}; SU Ç S4 = {}; fБ = 0.
В) W ={1,2,3 | 5 | 6,7 | 8 | 4}; fВ = 1.
W3 ={1,2,3}. F3 = 3.
Этап 4. А) Есть прямой путь из U = {1,2,3,4} в 5. fА = 1.
Б) SU = {5,8}; S5 = {2,6,7}; SU Ç S5 = {}; fБ = 0.
В) W ={1,2,3,4 | 8 | 6,7 | 5}; fВ = 1.
W4 ={1,2,3,4}. F4 = 2.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.