Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 153
Текст из файла (страница 153)
У профессора есть карта города. Покажите, как сформулировать задачу о возможности отправить детей в одну и ту же школу в виде задачи о максимальном потоке. 26.2 Метод Форда-Фалкерсона В данном разделе представлен метод Форда-Фалкерсона для решения задачи о максимальном потоке. Мы называем его методом, а не алгоритмом, поскольку он допускает несколько реализаций с различным временем выполнения. Метод Форда-Фалкерсона базируется на трех важных концепциях, которые выходят за рамки данного метода и применяются во многих потоковых алгоритмах и задачах.
Это — остаточные сети, увеличивающие пути и разрезы. Данные концепции лежат в основе важной теоремы о максимальном потоке и минимальном разрезе (теорема 26.7), которая определяет значение максимального потока с помощью разрезов транспортной сети. В заключение данного раздела мы предложим одну Глава 26. Задача о максимальном потоке 743 юнкретную реализацию метода Форда-Фалкерсона и проанализируем время ее выполнения. Метод Форда-Фалкерсона является итеративным. Вначале величине потока присваивается значение 0: Г' (и,и) = 0 для всех и, и 6 У. На каждой итерации величина потока увеличивается посредством поиска "увеличивающего пути" (т.е.
некого пути от источника а к стоку г, вдоль юторого можно послать больший поток) и последующего увеличения потока. Зтот процесс повторяется до тех пор, пока уже невозможно отыскать увеличивающий путь. В теореме о максимальном потоке и минимальном разрезе будет показано, что по завершении данного процесса получается максимальный поток. РОкп Р~л.кекзОх МетнОО(С, в,1) 1 Задаем начальное значение потока у равным 0 2 иЫ!е (Пока) существует увеличивающий путь р 3 йо увеличиваем поток у вдоль пути р 4 геГигп Г' Остаточные сети Интуитивно понятно, что если заданы некоторая транспортная сеть и поток, то остаточная сеть — это сеть, состоящая из ребер, допускающих увеличение потока.
Более строго, пусть задана транспортная сеть С = (Ъ; Е) с источником а и стоком 1. Пусть 1' — неюторый поток в С. Рассмотрим пару вершин и, и Е Е Ъ'. Величина дополнительного потока, который мы можем направить из и в и, не превысив пропускную способность с (и, и), является остаточной пропускной способностью (гезЫна! сарасйу) ребра (и, и), и задается формулой су (и, и) = с (и, и) — г (и, и) . (26.5) Еу = ((и, и) 6 У х Ъ": сГ (и, и) ) 0). Например, если с(и,и) = 16 и у (и,и) = 11, то у (и,и) можно увеличить на су (и, и) = 6, не нарушив ограничение пропускной способности для ребра (и, и).
Когда поток у (и, и) отрицателен, остаточная пропускная способность су (и, и) больше, чем пропускная способность с(и, и). Так, если с(и, и) = 16 н,г" (и, и) = = — 4, то остаточная пропускная способность су (и, и) = 20. Зту ситуацию можно интерпретировать следующим образом: существует поток величиной 4 единицы из и в и, юторый можно аннулировать, направив 4 единицы потока из и в и. Затем можно направить еще 16 единиц из и в и, не нарушив ограничение пропускной способности для ребра (и, и). Таким образом, начиная с потока у (и, и) = — 4, мы направили дополнительные 20 единиц потока, прежде чем достигли ограничения пропускной способности. Для заданной транспортной сети С = (1г, Е) и потока у, остаточной сетью (гез16па1 пепчог1с) в С, порожденной потоюм г", является сеть Су = (г', Еу), где Часть Ч1.
Алгоритмы для работы с графами 744 а) Рис. 26.3. а) Транспортная сеть С и поток 1', представленные на рис. 26.1б. 6) Остаточная сеть Сг с выделенным увеличивающим путем; его остаточная пропускная способность равна 4. в) Поток в сети С, полученный в результате увеличения потока вдоль луги р на величину его остаточной пропускной способности 4. г) Остаточная сеть, порожденная потоком, показанным в части в) Таким образом, как и отмечалось выше, по каждому ребру остаточной сети, или остаточному ребру (гезкЬи! едйе), можно направить поток, больший О. На рис. 26.3а воспроизведены транспортная сеть С и поток )', представленные на рис.
26.1б, а на рис. 26.3б показана соответствующая остаточная сеть Су. Ребрами Еу являются или ребра Е, или обратные нм. Если у (и, и) < с(и,и) для некоторого ребра (и, и) Е Е, то су (и, и) = с (и, и) — Г" (и, о) > О и (и, и) Е Е1. Если Г'(и,и) > О для некоторого ребра (и, и) е Е, то у (и,и) < О. В таком случае су (и,и) = с(и,и) — г"(и,и) > О и, следовательно, (и,и) е Еу.
Если в исходной сети нет ни ребра (и, и), ни (и,и), то с (и, и) = с (и,и) = О, г"(и, и) = г"(и,и) = = О (согласно результатам упражнения 26.1-1), и су (и, и) = су (и,и) = О. Таким образом, можно сделать вывод, что ребро (и, и) может оказаться в остаточной сети только в том случае, если хотя бы одно из ребер (и, и) или (и, и) присутствует в исходной транспортной сети, поэтому (Еу! < 2 )Е~.
Обратите внимание, что остаточная сеть Су является транспортной сетью со значениями пропускных способностей, заданными су. Следующая лемма показывает, как поток в остаточной сети связан с потоком в исходной транспортной сети. Лемма 26.2. Пусть С = (К Е) — транспортная сеть с источником з и стоком 1, а г — поток в С. Пусть Су — остаточная сеть в С, порожденная потоком у, а г"'— Глава 26. Задача о максимальном потоке 745 поток в С т. Тогда сумма потоков у + у', определяемая уравнением (26.4), является потоком в С, и величина этого потока равна (~+ У'! = !Д + ~У'~ Доказалзельсзлво. Необходимо проверить, выполняются ли ограничения антисимыетриччости, пропускной способности и сохранения потока. Для подтверждения антисимметричности заметим, что для всех и, о Е '«', справедливо ( г" + г ) (и, о) = у (и, о) + у (и, о) = = — у(о,и) — у'(о,и) = = — (у (о, и) + г"' (о, и) ) = = — (Г+ ~') (о,и) .
Покажем соблюдение ограничений пропускной способности. Заметим, что г"' (и, о) < су (и, о) для всех и, о Е У. Поэтому, согласно уравнению (2б.5), (,Г + У') (и, о) = Г (и, о) + г (и, о) < < Г (и, о) + (с (и, о) — г (и, о)) = = с(и,о). Что касается сохранения потока, заметим, что для всех и Е У вЂ” (в, т) справедливо равенство ~> (~+ Г') (и,о) = ~ (г(и,о)+ у (и,о)) = «аи «ни ,1(и,о)+ ,'~ ~'(и,о) = «е«' =0+0=0. И наконец, У+Г'~=',» У+~')( ) = «И" = ~(У(в, )+У'(в,о)) = «еЪ' = ~~> Г(в,о)+ ~~> ~'(в,о) = «е « «е« = ~л+ И.
Увеличивающие пути Для заданных транспортной сети С = (К Е) и потока у увеличивающим лузием (апятпепппя рабз) р является простой путь из в в т в остаточной сети Су. Часть Ч!. Алгоритмы для работы с графами 746 Согласно определению остаточной сети, каждое ребро (и,и) увеличивающего пути допускает некоторый дополнительный положительный поток из и в и без нарушения ограничения пропускной способности для данного ребра. Выделенный путь на рис. 26.3б является увеличивающим путем.
Рассматривая представленную на рисунке остаточную сеть Су как некоторую транспортную сеть, можно увеличивать поток вдоль каждого ребра данного пути вплоть до 4 единиц, не нарушая ограничений пропускной способности, поскольку наименьшая остаточная пропускная способность на данном пути составляет сг (из, из) = 4. Максимальная величина, на которую можно увеличить поток вдоль каждою ребра увеличивающего пути р, называется остаточной пропускной способностью (гез)бва! сарасйу) р и задается формулой су (р) = пцп(су (и,и): (и,и) принадлежит р) . Следующая лемма, доказательство которой предлагается провести в качестве упражнения 26.2-7, более строго формулирует приведенные выше рассуждения.
Лемма 26.3. Пусть С = (К Е) — транспортная сеть, а Г" — некоторый поток в С, и пусть р — некоторый увеличивающий путь в Сг. Определим функцию )р . )г х Ъ' — К следующим образом: су (р) если (и, и) принадлежит р, ~р(и,и) = — су(р) если (и,и) принадлежит р, О в противном случае. (26.6) Тогда )р является потоком в С и его величина составляет ~Ур~ = су (р) > О.
а Вытекающее из данной леммы следствие показывает, что если добавить ~р к г", то мы получим новый поток в С, величина которого ближе к максимальной. На рис. 26.3в показан результат добавления )р, представленного на рис. 26.3б, к г', показанному на рис. 26.3а. Доказательство. Непосредственно вытекает из лемм 26.2 и 26.3. Разрезы транспортных сетей В методе Форда-Фалкерсона производится неоднократное увеличение потока вдоль увеличивающих путей до тех пор, пока не будет найден максимальный Следствие 26.4. Пусть С = (1', Е) — транспортная сеть, а Г' — некоторый поток в С, и пусть р — некоторый увеличивающий путь в Су. Пусть Д определен в соответствии с уравнением (26.6). Определим функцию г': $г х Ъ' — К как г"' = ~+~р.
Тогда г' является потоком в С и имеет величину ! г"'! = !,г!+)~р~ > (Д. Глава 26. Задача о максимальном потоке 747 поток. В теореме о максимальном потоке и минимальном разрезе, которую мы вскоре докажем, утверждается, что поток является максимальным тогда и только тогда, когда его остаточная сеть не содержит увеличивающих путей. Однако для доказательства данной теоремы нам понадобится ввести понятие разреза транспортной сети. Разрезом (сш) (Я,Т) транспортной сети С = (У Е) называется разбиение множества вершин на множества Я и Т = У вЂ” Я, такие что в е 5, а ~ е Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
