так: мы просматриваем все элементы списка L, начиная с начала (строка 5). Всякий раз мы разряжаем текущую вершину и (строка 8). Если при этом высота вершины и увеличилась (что определяется сравнением с сохранённым в строке 7 прежним значением), то мы перемещаем её в начало списка (строка 10). После этого мы переходим к следующему элементу списка L. Заметим, что если мы переместили и в начало списка, то очередным будет элемент, следующий за и в её новой позиции.

Докажем, что алгоритм Lift-To-Front находит максимальный поток. Для этого убедимся, что его можно рассматривать как реализацию общей схемы проталкивания предпотока. Сначала заметим, что программа применяет подъёмы и проталкивания только там, где они возможны (согласно лемме 29.29). Осталось доказать, что после завершения алгоритма никакие подъёмы или проталкивания невозможны, останавливается, возможных подъёмов и проталкиваний нет.

Когда мы в последний раз в программе просмотрели список L, мы разрядили каждую вершину и, не подняв её. Как мы вскоре увидим (лемма 27.30), список L во время выполнения программы остаётся корректно упорядоченным, то есть конец любого допустимого ребра идёт после его начала. Поэтому процедура Discharge(m), проталкивая поток по допустимым рёбрам, создаёт избыток в вершинах, идущих в списке после и, и не трогает вершины, предшествующие и, в которых избыток остаётся равным нулю. Таким образом, по завершинию работы избыток в каждой вершине равен нулю (и ни проталкивание, ни подъём невозможны).

Лемма 27.30

При исполнении алгоритма Lift-To-Front список L остаётся корректно упорядоченным относительно (текущего) графа допустимых рёбер G/th = (V,Efth после любого числа итераций цикла в строках 6-11.

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

Перед первым выполнением цикла допустимых рёбер нет, так как высота истока h[s] равна \V\ 2 (множество V содержит по крайней мере исток s и сток t), а высота остальных вершина равна 0 (и единичного перепада высот быть не может).

Докажем, что свойство топологической упорядоченности сохраняется после каждого выполнения тела цикла. Сеть допустимых рёбер меняют только подъёмы и проталкивания. По лемме 27.27, проталкивания не создают допустимых рёбер. После подъёма произвольной вершины и все рёбра, входящие в эту вершину - недопустимые (лемма 27.28). Поэтому после перемещения и в начало списка порядок элементов в списке становится корректным.

Анализ алгоритма

Покажем, что время работы алгоритма «поднять-и-в-начало» на сети G = (V, Е) равно 0(V3). Сначала напомним некоторые уже

27.11 Работа алгоритма Lift-To-Front, (а) Начальный поток перед первым выполнением цикла. Из истока s выходит 26 единиц. Справа изображён список L (серым показано текущее значение и). Под каждой вершиной выписан список её соседей (серым выделен сосед current[u]). Сначала мы разряжаем вершину ж. Она поднимается на высоту 1. Из 12 единиц избытка отправляем 5 в вершину у, а затем оставшиеся 7 в сток t. Высота вершины х увеличилась, так что х помещаем в начало списка L (впрочем, она там и была). (Ь) На следующем шаге разряжаем вершину у, следующую за х. (На рис. 27.10 этот процесс показан подробно.) Высота вершины у увеличилась, и мы перемещаем её в начало списка L. (с) Теперь в списке за у следует х и мы разряжаем вершину ж, протолкнув 5 единиц потока в сток t. Подъёма не происходит, так что список L не меняется, (d) Следующую за ж в списке вершину z мы разряжаем, поднимая её до высоты 1 и проталкивая 8 единиц в сток t. Поскольку вершина поднята, она перемещается в начало списка L. (е) Переполненных вершин больше нет, поэтому процедура Discharge, последовательно применённая к вершинам у и ж, ничего не меняет. Программа LlFT-to-front достигает конца списка L и останавливается. Максимальный поток найден.

известные нам факты. Этот алгоритм является реализацией метода проталкивания предпотока, поэтому действует верхняя оценка О (V) на число подъёмов каждой вершины (следствие 27.21), а общее число подъёмов есть 0(V2). В соответствии с упр. 27.4-2, на все подъёмы уходит время 0(VE). Общее число насыщающих проталкиваний есть 0(VE) (лемма 27.22). Теорема 27.31

Время работы программы Lift-To-Front на сети G = (V, Е) равно 0(V3). Доказательство

Разобьём время работы программы Lift-To-Front на периоды между двумя подъёмами. Тогда всего периодов будет (как и подъёмов) 0(V2). Покажем, что за каждый период мы вызываем процедуру Discharge 0(V) раз. Действительно, за один период число вызовов процедуры Discharge (поскольку внутри периода мы не поднимаем вершину, список остаётся неизменным) не превосходит длины списка, и тем самым \V\.

Следовательно, процедура Discharge вызывается 0(V3) раз (строка 8), и время работы программы Lift-To-Front равно 0(V3) плюс суммарное время, уходящее на выполнение вызовов Discharge. Оценим второе слагаемое.

При каждом повторении цикла в процедуре Discharge совершается ровно одно из трёх действий: подъём вершины, перемещение указателя и проталкивание предпотока. Оценим количество one-

рации каждого из этих типов.

Начнём с подъёмов (строки 4-5). На все 0(V2) подъёмов требуется время 0(VE) (упр. 27.4-2).

Оценим количество перемещений указателя current[u] (строка 8). Обозначим через degree (и) степень вершины и. На каждый подъём вершины и приходятся 0(degree(u)) перемещений указателя, поэтому всего производится 0(V degree(u)) перемещений для каждой вершины. Таким образом, общее число перемещений указателей равно 0(VE) (по лемме о рукопожатиях, упр. 5.4-1).

Оценим число проталкиваний (строка 7). Мы уже знаем, что количество насыщающих проталкиваний равно 0(VE). Заметим, что сразу после выполнения ненасыщающего проталкивания процедура Discharge прекращает работу, так как избыток потока обращается в ноль. Таким образом, при каждом вызове процедуры выполняется не более одного ненасыщающего проталкивания; всего вызовов 0(V3), поэтому ненасыщающих проталкиваний не более 0(V3).

Таким образом, время работы программы Lift-To-Front есть 0(V3 + VE) = 0(V3). Упражнения 27.5-1

Следуя образцу рис. 27.11, покажите работу программы Lift-To-Front на сети рис.27.1 (а). Считать, что изначально список L имеет вид (1,2,3,4)1 а списки соседей таковы:

N[Vl] = (S) V2, V3) NiV2] = (S, Vi, V3, V4)

N[v3] = {vl,v2,v4,t) N[v4] = (v2,v3,t).

27.5-2*

Рассмотрим реализацию алгоритма проталкивания предпотока, при которой все переполненные вершины хранятся в виде очереди. Алгоритм разряжает первую вершину из очереди и удаляет её, а если в результате этого появились новые переполненные вершины, они добавляются в конец очереди. Алгоритм останавливается, когда очередь пуста. Покажите, что время работы этого алгоритма равно 0(V3).

27.5-3

Заменим в процедуре Lift строку 3 строкой: h[u] <- h[u] + 1. Покажите, что общий алгоритм проталкивания предпотока останется корректным. Как это изменение скажется на работе программы Lift-To-Front?

27.5-4*

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