Теорема о максимальных разрезах

Лекция 8. Метод нахождения максимального потока.

Величина максимального потока в любой сети определяется единственным образом, и может существовать несколько потоков, дающих наибольшую величину потока. Также в сети может существовать и несколько минимальных разрезов. Например, рассмотрим сеть на рис.21.

Пусть пропускная способность каждой дуги равна единице. Тогда обе дуги е₂₃и e_5n являются минимальными разрезами. Величина максимального потока в точности равна 1, однако максимальным потоком может быть как x₀₁ =x₁₂ = x₂₃= x₃₄ = x₄₅ = x_5n = 1, так и x₀₆ = x₆₂ = x₂₃ = x₃₇= x₇₅ = x_5n = 1.

Рис. 21.

Метод обнаружения максимального потока. Он основан на доказательстве теоремы Форда и Фалкерсона. Основная идея состоит в том, чтобы начать с некоторого потока и, если этот поток уже не является максимальным, улучшить его. Относительно нетрудно найти некоторый поток.

Пример. 8.1. Рассмотрим сеть, показанную на рис. 22,а и предположим, что мы начинаем с потока, показанного на рис. 22, б, который имеет цену 15 и очевидно не является максимальным.

Чтобы улучшить поток, нам следует заменить его новым потоком, имеющим большую цену. Чтобы сделать это, прежде всего, посмотрим на направленный путь, идущий от источника к стоку и обладающий тем свойством, что поток в каждой дуге пути строго меньше его пропускной способности. Пример такого пути приведен на рис. 22,а (хотя имеются и другие возможности выбора пути с такими свойствами). Для данного пути вычислим минимальную цену для совокупности его дуг. Оказывается возможным увеличить поток в каждом ребре пути на вычисленное значения, задавая новый поток с ценой, превышающей первоначальную. Минимальная цена для дуг пути, представленного на рис. 22, б, равна 2. Когда поток в каждой дуге этого пути будет увеличен на 2, мы получим поток с ценой 17.

а)

б)

Рис. 22.

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

Рассмотрите путь, показанный на рис.24,а. Это не направленный путь от источника к стоку; строго говоря, мы должны расценить его как путь в основном ненаправленном графе. Поток в каждой из трех ребер, направленных «вперед» строго меньше их емкости, и поток в ребре направленном «назад» положителен. Если мы увеличиваем поток в каждой из дуг с потоком «вперед» на 1 (на минимальную цену из совокупности цен для дуг, направленных «вперед») и уменьшим на 1 поток в дуге направленном «назад», то в результате поток все еще останется консервативным и при этом его цена будет увеличена на 1. Результирующий поток, с ценой 25, показан на рис.24, б. Других ненаправленных путей рассмотренного типа от источника к стоку в данном примере нет. (То есть, нет больше таких путей, у которых поток через все дуги, направленные вперед может быть увеличен без превышения их емкости, а поток через все дуги направленные назад может быть уменьшен, не становясь отрицательным.) Это означает, что поток, показанный на рис. 23, б является действительно максимальным.

а)

б)

в)

Рис. 23.

В рассмотренном примере довольно легко видеть, что действительно никаких других путей от источника к стоку, которые позволяют дополнительно увеличить поток не существует. Однако в случае более большой или более сложной сети может быть очень трудно определить наверняка, что таких путей, допускающих больший поток нет. Это как раз именно тот случай, когда теорема о максимальном потоке и минимальном срезе оказывается очень полезной. Так как срез — это множество таких дуг, что их блокировка полностью останавливает поток, то цена любого потока не может превысить емкость любого среза. Следовательно, цена потока может равняться емкости среза только в том случае, когда поток максимален, а срез минимален.

а)

б)

Рис. 24

Если мы можем найти срез со значением емкости равным 25 — значению, совпадающему со ценой потока, то мы из этого факта может сделать заключение, что такой поток действительно является максимальным (и конечно, срез является минимальным). Такие разрезы показаны на рис. 24. Таким образом, теорема максимального потока и минимального разреза гарантирует, что поток представленный на рис. 23,б является максимальным. При этом данный поток не является единственно возможным.

Для определения разреза, удобно воспользоваться рекурсивными правилами, рассмотренными при доказательстве теоремы Форда и Фалкерсона. Так, для потока примера 7.1 получим:

0. .

1. .

2.

1. –

2.

Получаем .

а)

б)

Рис. 24. Минимальные разрезы

Пусть () и () — два разреза. Будем говорить, что эти два разреза скрещиваются, если каждое из множеств , , , не пусто.

Теорема 2. Пусть () и () -- минимальные разрезы. Тогда () и () также являются минимальными разрезами.

Доказательство. Если , то , , следовательно,

, .

Рассмотрим случай, когда и , как показано на рис. 25. Т.е., данные два разреза скрещиваются. Введем четыре различных множества следующим образом: , , , , где , а .

Заметим, что , , , .

Пусть c(P, Q) = по всем , и аналогично для остальных множеств.

Т.к. () и () – минимальные разрезы, а и - разрезы, разделяющие и , то должно выполняться:

c() + c(), (7.1)

или

(7.2)

или

(7.3)

Рис. 25. Условное представление скрещивания разрезов

Поскольку величина должна быть неотрицательной, то видно, что (7.1) должно обращаться в равенство, т. е.

c() + c(),

или

c() + c(). (7.4)

Так как ни одно из слагаемых правой части (7.4) не может быть строго меньше пропускной способности минимального разреза, то каждое из них должно ей равняться.

Теорема доказана.

В общем случае , но обе величины неотрицательны. Теорема 2 устанавливает, что если имеются два скрещивающихся минимальных разреза, разделяющих V₀и V_n , то существуют два других не скрещивающихся минимальных разреза.