6.10. Потоки в сетях

• Определение. Транспортной сетью называется связный ориентированный граф без петель с выделенной парой вершин х и z (рис. 6.22). Вершина — начало транспортной сети, из которой дуги только выходят. Вершина конец транспортной сети, в которую дуги только входят. На множестве дуг и задана целочисленная функция где пропускная способность дуги.

Рис. 6.22. Транспортная сеть

• Определение. Потоком по транспортной сети называется целочисленная функция заданная на множестве дуг и и обладающая следующими свойствами:

где внутренняя вершина графа, т.е. множество дуг, заходящих в вершину множество дуг, выходящих из вершины х (рис. 6.22).

На рис. 6.22 напротив каждой душ стоит дробь, числитель которой — пропускная способность дуги, знаменатель — поток по дуге. Свойство (6.10.1) утверждает, что поток, входящий в вершину, равен выходящему потоку (поток в вершинах не скапливается). Обозначим

где поток, входящий в вершину поток, выходящий из вершины

Утверждение

Действительно, сумма так как величина суммируется дважды — со знаками Здесь где первая часть выражения равна нулю вследствие 6.10.1.

• Определение разреза. Пусть множество вершин транспортной сети: Обозначим через множество дуг, входящих в А. Это множество дуг будем называть разрезом транспортной сети.

Рис. 6.23. Разрез транспортной сети

называется мощностью разреза. Это максимально возможный поток, входящий в А по дугам разреза. поток, входящий в А по дугам разреза. Ясно, что так как

Утверждение

Действительно, из рис. 6.23 видно, что не весь поток, входящий в А, скатывается в z. Часть потока может выходить из А. Значит, но тогда и

• Теорема 6.10.1 Форда и Фалкерсона. Максимальный поток по транспортной сети равен мощности минимального разреза, т.е.

Доказательство теоремы — это алгоритм определения максимального потока по сети. Алгоритм состоит из двух частей.

1. Насыщение потока. Поток называется насыщенным, если любой путь из содержит дугу и для которой Задача первой части алгоритм состоит в насыщении потока.

1.1. Зададим произвольный начальный поток. Например, нулевой на всех дугах:

1.2. Поиск пути из Если путь найден, то переход к пункту 1.3. Если путь не найден, то переход к пункту 1.5.

1.3. Увеличиваем поток по найденному пути таким образом, чтобы одна из дуг стала насыщенной.

1.4. Условно разрываем насыщенную дугу и переходим к пункту 1.2, на поиск пути из

1.5. Сеть насыщена и «разорвана».

2. Перераспределение потока. Итак, поток насыщен, как в примере на рис. 6.24. Пометим рекурсивным образом все возможные вершины х, сети.

Рис. 6.24. Насыщенная транспортная сеть и пометка вершин

2.1. Вершину пометим —0.

2.2. Пусть любая из уже помеченных вершин; у — произвольная непомеченная вершина, смежная Вершину у помечаем если данные вершины соединены ненасыщенным ребром и помечаем если соединены непустым ребром После пометки вершин возможны два случая: вершина z оказалась либо помеченной, либо непомеченной.

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

Рис. 6.25. Перераспределение потока на основе пометки вершин

Заметим, что поток можно увеличивать (уменьшать) на прямых (обратных) дугах настолько, пока одна из дуг не станет насыщенной (пустой). Далее вновь переходим к пометке вершин (пункт 2.1). Выполненное перераспределение потока сохраняет все его свойства и увеличивает на единицу поток в вершину z. Таким образом, пометка вершины z позволяет увеличить поток как минимум на единицу, а значит, алгоритм конечен, т.е. наступит момент, когда вершина z останется непомеченной.

2.4. Вершина z осталась непомеченной. В рассматриваемом примере это показано на рис. 6.26. Пусть А — множество всех непомеченных вершин. Тогда душ, входящие в эти вершины, насыщенные, а выходящие — пустые. В примере Множество А определяет разрез, так как Таким образом, мы нашли поток и разрез А, для которых выполняется Учитывая, что выходящие душ из А пустые, то весь поток скатывается в т. е.

Рис. 6.26. Максимальный поток

Покажем, что максимальный поток, а А определяет минимальный разрез. Так как для любого потока и любого разреза А справедливо то выполняется соотношение

Для найденного разреза и потока справедливо равенство Отсюда следует, что Рассмотренный алгоритм позволяет найти именно максимальный поток и множество А, определяющее минимальный разрез. В рассматриваемом примере

Для примера на рис. 6.22 найдем все разрезы рассмотренной транспортной сети.

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

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