Лемма 27.14 (В переполненной вершине возможно либо проталкивание, либо подъём)

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

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

Поскольку h - высотная функция, то h(u) h(v) +1 для любого остаточного ребра (и, v). Если в и невозможно проталкивание, то для всех остаточных рёбер (и, v) выполнено неравенство h(u) < h(v) + 1, из чего следует, что h(u) h(v), и в вершине и возможен подъём.

Корректность метода

Корректность метода проталкивания предпотока мы докажем в два этапа. Сначала мы докажем, что если алгоритм остановится, то предпоток / в этот момент будет максимальным потоком. Затем мы докажем, что алгоритм действительно остановится. Начнём с такого замечания (очевидного следующего из описания процедуры подъёма).

Лемма 27.15 (Высота вершины не убывает)

При исполнении программы Generic-Preflow-Push высота h[u] любой вершины и £ V может только возрастать (при каждом подъёме этой вершины по меньшей мере на единицу).

Лемма 27.16

Во время выполнения программы Generic-Preflow-Push функция h остаётся высотной функцией. Доказательство

Посмотрим, что происходит при проталкивании и при подъёме.

При подъёме вершины и мы заботимся о том, чтобы выходящие из и остаточные рёбра не нарушали определение высотной функции. Что же касается входящих рёбер, то с ними не может быть проблем, так как высота вершины и только возрастает.

Рассмотрим теперь процедуру Push (и, v). Легко понять, что круто идущие внизх ненасыщенные рёбра появиться не могут. Более формально, эта процедура может добавить ребро (v, и) в Ef, а также удалить ребро (и, v) из Ef. В первом случае h[v] = h[u] - 1 и h остаётся высотной функцией. Во втором случае удалению ребра сопутствует отмена соответствующего ограничения и h снова остаётся высотной функцией.

Докажем одно важное свойство высотной функции.

Лемма 27.17

Пусть G = (V, Е) - сеть с истоком s и стоком t. Пусть / - предпоток в G, a h - высотная функция для /. Тогда в остаточной сети Gf не существует пути из истока в сток.

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

Пусть это не так и такой путь существует. Устраняя циклы, можно считать, что он простой и потому длина его меньше \V\.

При этом высота падает от \V\ до нуля. Следовательно, в пути есть ребро, где высота падает по крайней мере на 2 - а такое ребро не может входить в остаточную сеть.

Теорема 27.18 (Корректность метода проталкивания предпотока)

Если программа Generic-Preflow-Push, применённая к сети G = (V, Е) с истоком s и стоком t останавливается, то получающийся предпоток /, будет максимальным потоком для G.

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

Лемма 27.14 гарантирует, что в момент остановки переполненных вершин в сети нет (избыток в каждой равен нулю). Значит, в этот момент предпоток является потоком. По лемме 27.16 функция h будет высотной функцией, и потому (лемма 27.17) в остаточной сети Gf нет пути из s в t. По теореме о максимальном потоке и минимальном разрезе поток / максимален.

Анализ метода

Чтобы убедить, что алгоритм проталкивания предпотока останавливается, укажем верхние границы отдельно для числа подъёмов, насыщающих и ненасыщающих проталкиваний. После этого станет ясно, что время работы алгоритма есть 0(V2E).

Начнём с такой важной леммы:

Лемма 27.19

Пусть G = (V, Е) - сеть с истоком s и стоком t, а / - предпоток в G. Тогда для любой переполненной вершины и найдется простой путь из и в s в остаточной сети Gf.

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

Жидкость, сливаемая в вершине и, попадает туда из истока s по какому-то пути: существует путь из s в и, по рёбрам которого идёт положительный поток. (Формально можно рассуждать так: рассмотрим множество U тех вершин, из которых в и можно пройти по рёбрам с положительным потоком. Если среди них нет истока, то в U ни по каким рёбрам жидкость не входит. Отсюда следует, что e(U) (сумма всех избытков вершин в U), равная f(V, U) = f(V \U,U) + f(U, U) = f(V \U,U) 0, так что все изюытки равны 0.)

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

Следующая лемма ограничивает высоту вершины, и тем самым число возможных подъёмов.

Лемма 27.20

При исполнении программы Generic-Preflow-Push высота любой вершины v £ V никогда не превзойдёт 2\V\ - 1. Доказательство

По определению высоты h[s] = \V\ и h[t] = 0. Подъём применим

только к переполненным вершинам - посмотрим, на какой высоте они могут быть. Пусть и - переполненная вершина. По лемме 27.19, в Gf существует простой путь р из этой вершины в s. По определению высотной функции, высота не может убывать более чем на 1 вдоль рёбер сети Gf, а высота конечной вершины пути (т.е. s) равна \ V\. Путь (будучи простым) содержит не более \ V\ - 1 рёбер, так что высота его начала не превосходит 2\V\ - 1. Следствие 27.21 (Оценка числа подъёмов)

При исполнении программы Generic-Preflow-Push общее число операций подъёма не превосходит 2С2. Доказательство

Высота вершины при подъёме увеличивается, но не может стать больше 2\V\ - 1, поэтому любую вершину v £ V \ {s, t] можно поднять самое большее 2\V\ - 1 раз. Всего таких вершин \ V\ - 2, поэтому общее число подъёмов не превосходит (2\V\ - 1) (С - 2) < 2С2.

Лемма 27.22 (Оценка числа насыщающих проталкиваний) При исполнении программы Generic-Preflow-Push количество насыщающих проталкиваний не превосходит 2С£.

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

Рассмотрим насыщающие проталкивания между вершинами и, v £ V (в обе стороны). Если хотя бы одно проталкивание было, то хотя бы одно из рёбер (и, v) или (v, и) принадлежит Е. Пусть имело место насыщающее проталкивание из и в v. После него ребро (и, v) исчезло из остаточной сети Gf. Для того, чтобы это ребро появилось, необходимо протолкнуть поток из v в и, но этого нельзя сделать, пока не будет выполнено h[v] = h[u] + 1, т.е. h[v] необходимо увеличить по крайней мере на 2.

Посмотрим на значение суммы h[u] + h[v] в моменты насыщающих проталкивания между и и v. Заметим, что проталкивание возможно, только если высоты вершин и и v отличаются на единицу. Поэтому первая сумма не меньше 1, а последняя сумма не больше (2\V\ - 1) + 2(С - 2) = 4С - 3. Две соседние суммы отличаются по крайней мере на 2. Таким образом, всего имеется не более ((4С - 3) - 1)/2 + 1 = 2\V\ - 1 насыщающих проталкиваний. (Мы добавили единицу, чтобы учесть и первое, и последнее проталкивание.). Следовательно, общее число насыщающих проталкиваний (для всех рёбер) не превосходит (2\V\ - 1)\Е\ < 2С£.

Лемма 27.23 (Оценка числа ненасыщающих проталкиваний)

При исполнении программы Generic-Preflow-Push число ненасыщающих проталкиваний не превосходит 4С2(С + \Е\).

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

Назовём потенциалом сумму высот переполненных вершин, и будем смотреть, как меняется потенциал (обозначим его Ф) в ходе исполнения программы. Изначально Ф = 0. Подъем произвольной вершины и увеличивает Ф не более, чем на 2\V\ (высота вершины не превосходит 2\V\, лемма 27.20). Насыщающее проталкивание из