Обоснование алгоритма Форда-Фалкерсона

Предварительно введем ряд понятий и докажем ряд утверждений.

Определение. Разрезом в сети называется пара множеств и , удовлетворяющих условиям:

1. , ;

2. ;

3. .

Через обозначим множество всех дуг, начала которых лежат в , а концы – в , а через - множество всех дуг, начала которых лежат в , а концы – в .

Определение. Положим . Число называется пропускной способность разреза .

Также для разреза введем числовые характеристики:

Пример 4. Для сети и потока в ней из примера 1, рассмотрим разрез , где и . Имеем: , , .

Лемма 1. Для любого потока и любого разреза справедливо равенство .

Доказательство. Согласно условию сохранения потока в вершинах для произвольной вершины имеем: , или . Следовательно,

. (1)

Кроме того

. (2)

Сложив почленно равенства (1) и (2), получим

Первое и третье слагаемые последнего равенства взаимно уничтожаются, следовательно,

. ■

Следствие 1. .

Доказательство. Пусть , . Тогда , и равенство из леммы 1 запишется следующим образом: . ■

Следствие 2. Для любого потока и любого разреза справедливо неравенство .

Доказательство. Из условия ограничения по пропускной способности , т.е.

Тогда с учетом равенства из леммы 1 имеем:

■

Определение. Разрез называется минимальным, если для любого разреза справедливо неравенство

Лемма 2. Если для некоторого потока и некоторого разреза выполняется равенство , то поток максимален, а разрез минимален.

Доказательство. Пусть - максимальный поток, а - минимальный разрез. Тогда справедлива следующая цепочка неравенств

Поскольку крайние члены в этой цепочке неравенств совпадают, то она превращается в цепочку равенств, что означает, что поток максимален, а разрез минимален. ■

Лемма 3. Пусть - поток в сети и – -дополняющая цепь из в . Тогда в сети существует поток такой, что

Доказательство. Определим в сети функцию по формуле

Докажем, что функция является потоком.

Вначале покажем, что функция неотрицательна и удовлетворяет условию 1) определения потока.

Пусть - прямая дуга цепи . Тогда

Пусть - обратная дуга цепи . Тогда

Таким образом, для любой дуги цепи выполнено . Если , то .

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

1. Пусть обе дуги и прямые. В этом случае,

и ,

так что

и .

Но для потока выполнено условие , следовательно, и для потока имеем .

2. Пусть дуга - прямая и - обратная, т.е. обе дуги входят в вершину . В этом случае,

и ,

так что

и .

Так как для потока выполнено условие , то и для потока имеем .

Аналогично рассматриваются случай 3 (обе дуги и - обратные) и случай 4 (дуга - обратная и - прямая).

Таким образом, мы показали, что функция - поток в цепи .

Определим теперь величину потока . Напомним, что . Из вершины дуги только выходят, поэтому та единственная дуга с началом в вершине , которая входит в цепь , является прямой дугой цепи . Следовательно, для нее выполнено равенство . На остальных дугах, выходящих из , поток не менялся, так что имеем:

. ■

Объединяет приведенные выше результаты следующая теорема.

Теорема (Форд, Флакерсон). Для потока в сети следующие условия эквивалентны:

1. поток максимален;

2. не существует - дополняющей цепи из в ;

3. существует разрез , для которого .

Доказательство. Доказательство проведем по следующей схеме: .

. Будем рассуждать от противного. Предположим, что для максимального потока найдется -дополняющая цепь из в . Тогда по лемме 3 существует поток такой, что , т.е. . Полученное неравенство противоречит тому, что поток максимален.

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

Покажем, что для любой дуги выполнено равенство . Будем рассуждать от противного. Предположим, найдется дуга , для которой . Пусть - начало, - конец этой дуги, , . Множество определено нами так, что можно говорить о существовании -цепи , для которой . Дополним эту цепь дугой и вершиной до -цепи . Будем иметь: (здесь учтено, что , поскольку - прямая дуга в цепи ). Но выполнение неравенства означает, что вершина . Пришли к противоречию. Таким образом, предположение было неверным и для любой дуги выполнено равенство . Следовательно, .

Аналогично показывается, что для всех дуг имеет место равенство и, следовательно, . Поскольку (в силу леммы 1) для любого разреза справедливо равенство , для построенного разреза получаем равенство .

. Это утверждение полностью совпадает с утверждением доказанной ранее леммы 2. ■

Следствие. Величина максимального потока в произвольной сети равна пропускной способности минимального разреза.

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

Пример 5. Для сети из примера 1, разрез , где и , минимален.