Проверим второе утверждение леммы. Предположим, что после подъёма имеется допустимое ребро (v,u). Тогда h(v) = h(u) + 1

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

Списки соседей

Алгоритм «поднять-и-в-начало» использует специальный способ хранения рёбер сети G = (V,E). Именно, для каждой вершины и £ V имеется односторонне связвнный список соседей (neighbor list) А[и]. Вершина v фигурирует в этом списке, если (и, v) £ Е или если (v, и) £ Е. Таким образом, список N[u] содержит все вершины v, для которых (и, v) имеет шанс появиться в остаточной сети. Первый элемент этого списка обозначается /leadfA-w]]; следующий за вершиной v сосед - next - neighbor[v]. Если вершина v

-последняя в списке, то next - neighbor[v] =nil.

Порядок в списке соседей может быть произвольным; он не меняется в ходе работы (всякий раз алгоритм просматривает список соседей в одном и том же порядке). Для каждой вершины и хранится указатель current[u] на очередной элемент списка А[и]. Изначально current[u] установлен на /leadfA-w]].

Обработка переполненной вершины

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

\textsc{Discharge}($u$)

1while $e[u]>0$

2do $v\leftarrow current[u]$

3if $v=$\textsc{nil}

4then \textsc{Lift($u$)}

5$current[u]\leftarrow head[I[u]]$

6elseif $c f(u,v)>0$ and $h[u]=h[v]+1$

7then \textsc{Push($u,v$)}

8else $current[u]\leftarrow next-neighbor[v]$

На рис. 27.10 показаны несколько итераций цикла while (строки

Каждая итерация цикла while производит одно из трёх действий:

1.Если мы дошли до конца списка (v =nil), то мы поднимаем вершину и (строка 4) и переходим к началу списка N[u] (строка 5). Мы увидим (лемма 27.29), что подъём возможен.

2.Если мы не дошли до конца списка и ребро (и, v) - допустимое (проверка в строке 6), то проталкиваем поток из и в v (строка 7).

27.10 Разрядка вершины. Требуется 15 повторений цикла while в процедуре Discharge, чтобы протолкнуть весь избыток из вершины у. Показаны только соседи вершины у и рёбра, соединяющие их с у. Внутри каждой вершины указан избыток в ней перед соответствующей итерацией; слева указана высота вершины. Справа показан список N [у]; выделен сосед current[y]. (а) Изначально избыток в у равен 19 и current[y] = s. Из у не выходят допустимые рёбра, поэтому первые три итерации сдвигают указатель current[y]. На четвертом шаге мы дошли до конца списка. Поднимаем вершину у и переходим к началу списка. (Ь) Высота вершины у стала равной 1. Рёбра (y,s) и (у,х) - недопустимые (шаги 5-6), а ребро (y,z) - допустимое, и мы проталкиваем 8 единиц в z (шаг 7; заметим, что указатель current[y] мы при этом не сдвинули), (с) Проталкивание на шаге 7 оказалось насыщающим, и на шаге 8 ребро (у, z) становится недопустимым. На шаге 9 мы дошли до конца списка (current[y] = NIL)) поднимаем у, переходим к началу, (d) Ребро (y,s) недопустимо (шаг 10), но ребро (у,х) допустимо - по нему мы проталкиваем 5 единиц, (е) Больше допустимых рёбер нет (шаги 12-13), поэтому ещё раз поднимаем у и возвращаемся к началу списка (шаг 14). (f) Проталкиваем 6 единиц в s (шаг 15). (g) Избытка в вершине у больше нет, и процедура завершает работу. Заметим, что в этом примере в начале и в конце работы процедуры Discharge указатель current[y] установлен на начало списка, но в общем случае это не так.

3. Если мы не дошли до конца списка, но ребро (и, v) - недопустимое, то сдвигаем указатель current[u] на одну позицию в списке (строка 8).

Заметим, что при вызове процедуры Discharge указатель current[u] находится в позиции, «унаследованной» от предыдущего вызова. Последним действием этой процедуры может быть лишь проталкивание: процедура останавливается, если избыток е[и] обращается в нуль, но ни подъём вершины, ни сдвиг указателя не меняют эту величину.

Надо проверить, что процедура Discharge выполняет подъём и проталкивание тогда, когда это действительно можно сделать по нашим правилам.

Лемма 27.29

При вызове операции Push (и, v) в процедуре Discharge (строка 7) по ребру (и, v) возможно проталкивание. При вызове операции Lift (и) в процедуре Discharge (строка 4) возможен подъём вершины и.

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

Возможность проталкивания гарантируется проверками в строках 1 и 6, так что первое утверждение очевидно.

Докажем второе утверждение. Для этого (по лемме 27.28) достаточно доказать, что все выходящие из и рёбра недопустимы. Заметим, что при вызовах процедуры Discharge указатель current[u] перемещается по списку N[u] от его начала /leadfA-w]] до конца.

В конце вершину и поднимают и начинается новый проход. Каждый раз, прежде чем сдвинуть указатель с произвольной позиции v мы убеждаемся (строка 6), что ребро (и, v) недопустимо. Таким образом, в конце прохода все выходящие из и рёбра были просмотрены и оказались недопустимыми. Могли ли они затем стать допустимыми (до конца прохода)? По лемме 27.27, проталкивания вообще не создают допустимых рёбер. Их могут породить только операции подъёма. Но вершина и не поднималась (в течение прохода по списку), а подъёмы других вершин создают лишь выходящие из них допустимые рёбра. Поэтому в конце прохода все выходящие из вершины и рёбра недопустимы, поэтому её можно поднять.

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

Алгоритм «поднять-и-в-начало» хранит множество V \ {s, t] вершин (отличных от истока и стока) в виде списка. При этом существенно то, что список этот оказывается «корректно упорядоченным» в следующем смысле: конец любого допустимого ребра находится дальше в списке, чем начало этого ребра (напомним, что допустимые рёбра образуют ациклический граф, лемма 27.26). (Задачу о поиске корректрого упорядочения для произвольного ациклического графа мы называли задачей топологической сортировки, см. раздел 23.4.)

Следующую в этом списке за и вершину обозначим next[u]; если вершина и - последняя в списке, то next[u] =nil.

\textsc{Lift-To-Front}($G,s,t$)

1\textsc{Initialize-Preflow}($G,s$)

2$L\leftarrow V[G]-\{s,t\}$ (в любом порядке)

3for (для) каждой вершины $u\in V[G]\setminus \{s,t\}$

4do $current[u]\leftarrow head[N[u]]$

5$u\leftarrow head[L]$

6while $u\ne$\textsc{nil}

7do $old-height\leftarrow h[u]$

8\textsc{Discharge}($u$)

9if $h[u]>old-height$

10then переместить $u$ в начало списка $L$

11$u\leftarrow next[u]$

Алгоритм формирует начальный предпоток (строка 1), список L (строка 2) (точно так же, как это делалось раньше). Затем (строки 3-4) он устанавливает указатели current[u] в начало списка соседей каждой вершины и (считаем, что для всех вершин и списки соседей N[u] уже созданы.)

Работа цикла (строки 6-11, см. также рис. 27.11) происходит