Докажем обратное. Пусть / - целочисленный поток в G; его значения могут быть равны 0 или 1, так как пропускная способность рёбер ограничена единицей. Определим

М = {(и, v)\u е L, v е R, f(u, v) = 1}.

Докажем, что М - паросочетание. В самом деле, из одной вершины и не могут выходить два ребра (u,v) и (u,v"), по которым поток равен 1, так как входящий в и поток не превосходит 1. По аналогичным причинам в любую вершину v входит не более одного ребра с единичным потоком.

Чтобы убедиться, что \М\ = /, заметим, что \М\ есть поток через разрез (L U {s},RU {t} (по каждому ребру идёт потом 1, а число рёбер есть М).

Лемма сводит задачу о максимальном паросочетании к задаче о максимальном целочисленном потоке. Требования целочислен-ности у нас раньше не было, но оказывается, что метод Форда-Фалкерсона всегда даёт целочисленный максимальный поток, если только пропускные способности всех рёбер целые, так что специально заботится о целочисленности не надо.

Теорема 27.11 (Теорема о целочисленном потоке)

Если пропускные способности всех рёбер - целые числа, то максимальный поток, найденный алгоритмом Форда-Фалкерсона, будет целочисленным.

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

На каждом шаге (при каждом добавлении потока по дополняющему пути) поток остаётся целочисленным. (Подробное доказательство мы оставляем читателю в качестве упр.27.3-2.)

Следствие 27.12

Число рёбер в максимальном паросочетания М в двудольном графе G равно значению максимального потока в сети G. Доказательство

По теореме 27.11 можно заменить слова «максимального потока» на «максимального целочисленного потока», после чего сослаться на лемму 27.10.

Таким образом, чтобы найти максимальное паросочетание в двудольном графе G, нам достаточно применить метод Форда-Фалкерсона и найти максимальный поток в соотвествующей сети G. Оценим время работы такого алгоритма. Никакое паросочетание в двудольном графе не может содержать более min(L,i?) = 0(V) рёбер, поэтому значение максимального потока в G равно 0(V). Следовательно, время работы алгоритма Форда-Фалкерсона равно 0(VE) (см. анализ алгоритма Форда-Фалкерсона в разделе 27.2).

Упражнения

27.3-1

Примените алгоритм Форда-Фалкерсона к сети рисунка 27.9(b). Как будут выглядеть остаточные сети после каждого шага? (Пронумеруйте вершины сверху вниз отдельно в L и в R; на каждом шаге выбирайте наименьший в смысле лексикографического порядка дополняющий путь.)

27.3-2

Докажите теорему 27.11.

27.3-3 Пусть G = (V, Е) - двудольный граф и G - сответству-ющая сеть. Оценить сверху длину любого дополняющего пути в G1, найденного при работе процедуры Ford-Fulkerson.

27.3-4*

Полным (совершенным) паросочетанием (perfect matching) называется паросочетание, в которое входят все вершины. Пусть G = (V, Е) - неориентированный двудольный граф, в котором доли L и R имеют поровну элементов. Для каждого X С V определим множество соседей (neighborhood of) X формулой

N(X) = {у G V\(x,y) G Е для некоторого х G X,

(соседями являются вершины, соединённые ребром с некоторым элементом множества X). Докажите теорему Холла (Halls theorem): полное паросочетание существует тогда и только тогда, когда для любого А С L выполнено А ./V(A). 27.3-5*

Назовем двудольный граф G = (V, Е) с долями L и R d-регулярным (rf-regular), если степень каждой вершины v G V равна d. (Заметим, что в таком случае \L\ = \R\.) Докажите, что для d-регулярного графа всегда существует полное паросочетание.

27.4. Алгоритм проталкивания предпотока

В этом разделе мы излагаем метод «проталкивания предпотока». Наиболее быстрые из известных алгоритмов для задачи о максимальном потоке используют именно его. Он применим и к другим задачам, например к задаче о потока наименьшей стоимости. В этом разделе, следуя Гольдбергу, мы опишем «общий» метод проталкивания предпотока. Уже простейшая его реализация требует всего лишь 0(V2E) шагов и опережает алгоритм Эдмондса-Карпа (0(VE2)). В разделе 27.5 мы покажем, как улучшить оценку до 0(V3).

В отличие от алгоритма Эдмондса-Карпа, мы не просматриваем всю всю остаточную сеть на каждом шаге, а действуем локально в окрестности одной вершины. Кроме того, мы не требуем, выполнения закона сохранения потока в процессе работы алгоритма, довольствуясь выполнением свойств предпотока. Мы будем назы-

вать предпотоком (preflow) функцию / : V X V -> Ж, которая кососимметрична, удовлетворяет ограничениям, связанным с пропускными способностями, а также такому и ослабленному закону сохранения: f(V, и) 0 для всех вершин и £ C\{s}. Таким образом, в каждой вершине и (кроме истока) есть некоторый неотрицательный избыток (excess flow)

Вершину (отличную от истока и стока) с положительным избытком назовём переполненной (overflowing). (Пользуясь метафорой нефтепровода, можно сказать, что приходящую нефть не успевают откачивать, и избыток нефти сливается.)

В этом разделе мы объясним идею метода и опишем две основные операции: «проталкивание» предпотока и «подъём» вершины. После этого докажем правильность общего алгоритма проталкивания предпотока и оценим время его работы.

Мотивировка

В методе Форда-Фалкерсона мы в каждый момент имеем дело с потоком жидкости по трубам от истока к стоку; на каждом шаге мы увеличиваем этот поток, находя дополняющий путь. Жидкость никуда не проливается по дороге.

В алгоритмах проталкивания предпотока избыток жидкости в каждой вершине (месте соединения труб) сливается. Кроме того, важную роль играет целочисленный параметр, который будет называться высотой вершины - мы будем воображать, что в процессе работы алгоритма вершина может подниматься вверх. Высота вершины определяет, куда мы стараемся направить избыток жидкости: хотя (положительный) поток жидкости может идти и снизу вверх, увеличивать его в такой ситуации нельзя. (Подробности см. ниже.)

Высота истока всегда равна \V\, а стока - нулю. Все остальные вершины изначально находятся на высоте 0, и со временем поднимаются. Для начала мы отправляем из истока вниз столько жидкости, сколько нам позволяют пропускные способности выходящих из истока труб (это количество равно пропускной способности разреза (s,V \s)). Возникающий (в соседних с истоком вершинах) избыток жидкости сперва просто выливается, но затем он будет направлен дальше.

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