некоторой вершины и в некоторую вершину v может увеличить потенциал лишь за счёт появления новой переполненной вершины v (так будет, если v - не сток и не исток), то есть не более чем на 2\V\. Наконец, ненасыщающее проталкивание из и в v уменьшает Ф по крайней мере на единицу, так как вершина и перестаёт быть переполненной и слагаемое h[u] исчезает, а появиться может лишь слагаемое h[v] (если вершина v не сток, не исток и не была переполненной), которое на единицу меньше.

Таким образом, общая сумма, на которую увеличивается Ф во время работы программы, не превосходит (2У)(2У2) + (2У)(2УЯ) = 4У2(У + \Е\) (мы используем следствие 27.21 и лемму 27.22) Но Ф 0, поэтому общая сумма, на которую Ф уменьшится, и тем самым общее количество ненасыщающих проталкиванийю не превосходит 4У2(У + \Е\).

Теорема 27.24

Общее число операций подъёма и проталкивания при исполнении программы Generic-Preflow-Push на сети G = (V, Е) равно 0{V2E).

Доказательство

Применяем следствие 27.21 и леммы 27.22, 27.23. Следствие 27.25

Алгоритм, основанный на проталкивании предпотока, можно реализовать так, чтобы на сети G = (V, Е) время его работы было 0{V2E).

Доказательство

Легко видеть (упр. 27.4-1), что можно выполнить подъём за время О {V) и проталкивание за время 0(1), что и даёт требуемую оценку.

Упражнения

27.4-1

Как реализовать алгоритм проталкивания предпотока так, чтобы на подъём уходило время 0(V), и на проталкивание 0(1)? (При этом общее время будет 0(V2E).)

27.4-2

Докажите, что алгоритм проталкивания предпотока, на все 0(V2) подъёмов тратит 0(VE) времени. 27.4-3

Допустим, мы нашли максимальный поток в сети G методом проталкивания предпотока. Как теперь быстро найти минимальный разрез?

27.4-4

Как найти максимальное паросочетание в двудольном графе, используя метод проталкивания предпотока? Каково время работы вашего алгоритма?

27.4-5

Пусть все пропускные способности рёбер сети G = (V, Е) - це-

лые числа от 1 до к. Оцените в терминах \V\, \Е\ и к время работы алгоритма проталкивания предпотока. (Указание: сколько ненасыщающих проталкиваний можно применить к ненасыщенному ребру, прежде чем оно станет насыщенным?) 27.4-6

Докажите, что строку 7 процедуры Initialize-Preflow можно заменить строкой

h[s]\V[G]\-2,

не нарушая корректности и не меняя асимптотики времени работы алгоритма. 27.4-7

Обозначим через Sf(u,v) расстояние (количество рёбер) от вершины и до вершины v в остаточной сети Gf. Покажите, что во время выполнения программы Generic-Preflow-Push остаётся верными следующие утверждения: если h[u] < У,то/г[и] Sf(u,t); если h[u] V, то h[u] Sf(u,s).

27.4-8*

Как и в предыдущем упражнении, Sf (и, v) обозначает расстояние от вершины и до вершины v в остаточной сети Gf. Как изменить алгоритм проталкивания предпотока, чтобы во время его работы оставались верными такие утверждения: если h[u] < \V\, то h[u] = Sf (и, t); если h[u] V, то h[u] = Sf(u,s). (Дополнительные действия должны укладываться в 0(VE) операций.)

27.4-9

Покажите, что число ненасыщающих проталкиваний, выполненных программой Generic-Preflow-Push на сети G = (V,E), не превосходит 4У2£ (если \V\ 4).

27.5. Алгоритм поднять-и-в-начало

Пользуясь методом проталкивания предпотока, мы применяли операции подъёма и проталкивания в более или менее произвольном порядке. Более продуманный порядок выполнения этих операций позволяет уменьшить время работы алгоритм (по сравнению с оценкой 0(V2E) из следствия 27.25). В этом разделе мы рассмотрим алгоритм «поднять-и-в-начало» (lift-to-front algorithm), использующий эту идею; время его работы есть 0(V3), что асимптотически по крайней мере не хуже, чем 0(V2E).

Алгоритм «поднять-и-в-начало» хранит все вершины сети в виде списка. Алгоритм просматривает этот список, начиная с головы, и находит в нем переполненную вершину и. Затем алгоритм «обслуживает» эту вершину, применяя к ней операции подъёма и проталкивания до тех пор, пока избыток не станет равным нулю. Если для этого вершину пришлось поднять, её перемещают в на-

чало списка (отсюда и название алгоритма), и просмотр списка начинается вновь.

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

Допустимые рёбра

Пусть / - предпоток в сети G = (V, Е), a h - высотная функция. Назовем ребро (и, v) допустимым (admissible), если оно входит в остаточную сеть (с/(и, v) > 0) и h(u) = h(v) + 1 Остальные рёбра мы будем называть недопустимыми (inadmissible). Обозначим через Efth множество допустимых рёбер; сеть G/th = (V,Efth) назовём сетью допустимых рёбер (admissible network). Она состоит из рёбер, по которым возможно проталкивание. Поскольку вдоль допустимого ребра высота уменьшается, имеет место такая лемма: Лемма 27.26 (Допустимые рёбра образуют ациклический граф) Пусть / - предпоток в сети G = (V,E); пусть h - высотная функция. Тогда сеть допустимых рёбер G/th = (V,Efth) не содержит циклов.

Посмотрим, как изменяют сеть допустимых рёбер операции подъёма и проталкивания. Лемма 27.27

Пусть / - предпоток в сети G = (V, Е) и h - высотная функция. Пусть (и, v) - допустимое ребро и вершина и переполнена. Тогда по (и, v) возможно проталкивание. В результате выполнения этой операции новые допустимые рёбра не появляются, но ребро (и, v) может стать недопустимым.

Доказательство

В результате проталкивания в остаточной сети может появиться только ребро (v,u). Поскольку ребро (и, v) допустимо, то h(v) = h(u) - 1, и потому ребро (v, и) недопустимо. Если проталкивание оказывается насыщающим, то в результате Cf(u,v) = 0 и ребро (и, v) исчезает из остаточной сети (и становится недопустимым).

Лемма 27.28

Пусть / - предпоток в сети G = (V, Е) и h - высотная функция. Если вершина и переполнена и из нее не выходит допустимых рёбер, то возможен подъём вершины и. После подъёма появится по крайней мере одно допустимое ребро, выходящее из вершины и и не будет рёбер, входящих в и.

Доказательство

Как мы видели (лемма 27.14), в переполненной вершине и возможно либо проталкивание, либо подъём. Так как из и допустимые рёбра не выходят, то проталкивание в ней невозможно, и возможен подъём. При этом высота вершины увеличивается так, что проталкивание становится возможным, то есть появляется допустимое ребро.