Тексты лекций / Текст лекции 14

§ 3.10. Задача о максимальном потоке в сети

Сеть. Поток в сети. Величина потока. Максимальный поток. Дополняющая цепь. Разрез в сети. Минимальный разрез. Алгоритм Форда - Фалкерсона.

Базовые понятия и утверждения

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

- пропускной способностью дуги .

Для удобства изложения введем следующие обозначения. Через +обозначим множество дуг, для которых вершина является началом, а через − обозначим множество дуг, для которых вершина является концом.

Определение. Потоком в сети = ( ,,) называется функция : → 0,∞), удовле-

Значение ( −) можно интерпретировать как поток, втекающий в вершину , а значение ( +) - как поток, вытекающий из вершины . Тогда второе условие можно переформулировать так: поток, втекающий в любую вершину, за исключением источника и стока, должен быть равен потоку, вытекающему из этой вершины.

Условие 1) называется условиемограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах.

cется величиной потока.

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

Задача омаксимальномпотоке формулируется следующим образом: в заданной сети

найти поток максимальной величины.

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

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

1

Тема 14. «Задача о максимальном потоке в сети» Олейник Т.А., 2020

Поскольку цепи других видов нас при этом интересовать не будут, то далее в этом параграфе неориентированные простые цепи будем называть просто цепями.

Если в цепи ... дуга выходит из вершины и заходит в вершину, то она называется прямой дугой цепи. Если же дуга выходит из вершины и заходит

вычислять остаточную пропускнуюспособность ( )при данномпотоке последующему правилу: если дуга прямая, то ( ) = ( ) − ( ), а если обратная, то ( ) = ( ). В своюочередьостаточнуюпропускнуюспособность ( )цепи приданномпотоке будем

определять по формуле ( ) = { ( )}.

Определение. Цепь из в называется дополняющей для , если ( ) > 0. Пример 2. В сети, изображенной на рис. 3.83, цепь, включающая последовательно

вершины ,,,, , является дополняющей для потока, рассмотренного в примере 1. Одним из алгоритмов, позволяющих построить максимальный поток, является алго-

ритм Форда - Фалкерсона.

Алгоритм Форда - Фалкерсона. 0-й шаг. Пускаем по сети нулевой поток , т.е. по-

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

Доказательство алгоритма Форда - Фалкерсона приведено во второй части параграфа. Пример 3. Построим максимальный поток для сети, изображенной на рис. 3.84,а.

◄ Шаг 0. Для любой дуги положим ( ) = 0 (на рисунке этот поток отмечать не будем, более того, договоримся и далее нулевой поток на дугах не отмечать), ‖ ‖ = 0.

Шаг 1. : → → → - дополняющая цепь для потока (стрелки заменяют

имена дуг, под каждой стрелкой записана остаточная пропускная способность ( ) соот-

ветствующей дуги ), ( ) = { ( )} = 4, поток указан на рис. 3.84,б, ‖ ‖ = ‖ ‖+

( ) = 4.

Шаг 2. : → → → → - дополняющая цепь для потока , ( ) = 2, поток

указан на рис. 3.84,в, ‖ ‖ = ‖ ‖ + ( ) = 6.

2

Рис. 3.84.

Для потока нет ни одной дополняющей цепи из в . Следовательно, поток является максимальным. ►

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

1), ;

2)= ;

3)∩ = .

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

Определение. Положим ( → ) = ∑ → ( ). Число ( → ) называется про-

пускной способностью разреза (, ).

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

(, ) справедливо неравенство ( → ) ≤ ( → ).

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

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

Если для сети найден максимальный поток, то минимальный разрез можно найти следующим образом: включить в множество вершину и все вершины , для каждой из

3

Тема 14. «Задача о максимальном потоке в сети» Олейник Т.А., 2020

которых существует цепь из в с остаточной пропускной способностью ( ) > 0; положить = \. Полученный таким образом разрез (, ) будет минимальным.

Пример 4. Вернемся к примеру 3. Используя найденный максимальный поток, несложно определить, что единственной вершиной, в которую можно добраться по цепи с положительной остаточной пропускной способностью, является вершина . Следовательно, пара множеств = { ,} и = { ,,,,} образует минимальный разрез.

Упражнение 3.37. Найтимаксимальныйпоток иминимальныйразрездлясети,изоб-

Теоретические обоснования

Перейдем к обоснованию алгоритма Форда - Фалкерсона. Для произвольных разреза

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

( → )− ( → ) = ‖ ‖.■ Следствие 1. ‖ ‖ = ( −).

4

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

‖ ‖ ≤ ( → ).

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

∑ → ( ) ≤ ∑ → ( ), т.е. ( → ) ≤ ( → ).

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

‖ ‖ = ( → )− ( → ) ≤ ( → ) ≤ ( → ). ■

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

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

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

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

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

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

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

0 ≤ ( ) = ( )+ ( ) ≤ ( )+ ( ) = ( )+ ( ( ) − ( )) = ( ).

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

( ) = ( ) − ( ) ≥ ( ) − ( ) = ( ) −( ) = 0 и( ) = ( ) − ( ) ≤ ( ) ≤ ( ).

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

0 ≤ ( ) = ( ) ≤ ( ).

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

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

( ) = ( )+ ( ) и ( ) = ( )+ ( ),

так что

( +) = ( +)+ ( ) и ( −) = ( −)+ ( ).

Но для потока выполнено условие ( +) = ( −), следовательно, и для потока

имеем ( +) = ( −).

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

5

( −) = ( −)+ ( ) − ( ) = ( −) и ( +) = ( +).

Так как для потока выполнено условие ( +) = ( −), то и для потока имеем

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

= ( +) = ‖ ‖+ ( ). ■

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

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

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

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

3)существует разрез (, ), для которого ‖ ‖ = ( → ).

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

1 2. Будем рассуждать от противного. Предположим, что для максимального потоканайдется дополняющая цепь из в . Тогда по лемме 3 существует поток такой, что= ‖ ‖ + ( ), т.е. > ‖ ‖. Полученное неравенство противоречит тому, что потокмаксимален.

2 3. Определим как множество всех вершин , для каждой из которых существует цепь из в такая, что ( ) > 0. Добавим в вершину и положим = \. Докажем, что для полученного разреза (, ) выполняется равенство

‖ ‖ = ( → ).

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

( ) = ( ), ( ) = ( ),( ) − ( ) > 0

(здесь учтено, что - прямая дуга в цепи и, значит, ( ) = ( )− ( )). Но выполнение неравенства ( ) > 0 означает, что вершина . Пришли к противоречию. Таким образом, предположение было неверным и для любой дуги → выполнено равенство

( ) = ( ). Следовательно, ( → ) = ( → ).

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

‖ ‖ = (, ).

6

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

2. ■

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

Замечание. В ходе доказательства теоремы при обосновании справедливости перехода 2 3 был, по существу, предложен алгоритм нахождения минимального разреза.

Ответы и указания к упражнениям

3.37. а) Один из максимальных потоков изображен на рис. 14. Этому потоку соответствует минимальныйразрез = { ,,,}, = { ,,,}.Величинамаксимальногопотокаипропускная способность минимального разреза равна 16; б) Один из максимальных потоков изображен на рис. 15. Этому потоку соответствует минимальный разрез = { ,,}, = { ,,,,}.Величинамаксимальногопотока ипропускная способностьминимальногоразреза равна 16.

Рис. 14. Рис. 15.

7