Доказательство теоремы

Пусть – максимальный поток, а путь – ненасыщен потоком . Построим множество узлов , которые можно достичь из истока по пути, ненасыщенному максимальным потоком .

Возможны 2 случая:

а) Пусть . Построим множество . Пара – сечение по построению. Подсчитаем мощность потока из истока во все узлы:

Так как и – максимальный поток, будет выполняться равенство . Тогда по Лемме 2.1.2, – минимальное сечение.

б) Пусть , тогда существует путь , ненасыщенный потоком . Вычислим величину

Построим новый поток по следующему правилу:

Покажем, что – поток, для этого посчитаем его мощность:

получили противоречие тому, что – максимальный поток, следовательно, этот случай невозможен, тогда выполняется случай а).

Дата добавления: 2014-01-07