Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 154
Текст из файла (страница 154)
(Это определение аналогично определению разреза, которое использовалось применительно к минимальным связующим деревьям в главе 23, однако здесь речь идет о разрезе в ориентированном графе, а не в неориеитированном, и мы требуем, чтобы вЕ 5, а МТ.) Если г" — поток, то чистый ломок (пе1 йои ) через разрез (Я, Т) по определению равен У (Я, Т). Пропускной способностью (сарасйу) разреза (Б, Т) является с(Я, Т). Минимальным разрезом (пппппшп сщ) сети является разрез, пропускная способность которого среди всех разрезов сети минимальна.
На рис. 26.4 показан разрез ((в, пы пг), (пз, п4, 1)) транспортной сети„представленной на рис. 26.1б. Чистый поток через данный разрез равен У (пг, пз) + У (сг, пз) + г (пг, п4) = 12 + (-4) + 11 = 19, а пропускная способность этого разреза равна с (пм пз) + с(пг, п4) = 12+ 14 = 26. Обратите внимание, что чистый поток через разрез может включать в себя отрицательные потоки между вершинами, но пропускная способность разреза слагается исключительно из неотрицательных значений.
Иными словами, чистый поток через разрез (Я, Т) составляется из положительных потоков в обоих направлениях; положительный поток из Я в Т прибавляется, а положительный поток из -з~т- Рис. 26.4. Разрез (Я, Т) транспортной сети, представленной на рис. 26.16, Я = (в,с1 сг), Т = (сз,с4 Ф). Вершины, принадлежащие Я, отмечены черным цветом, а вершины Т вЂ” белым Часть Ч1. Алгоритмы для работы с графами 748 Т в $ вычитается. С другой стороны, пропускная способность разреза ($,Т) вычисляется толью по ребрам, идущим из $ в Т. Ребра, ведущие из Т в $, ие участвуют в вычислении с ($, Т).
Следующая лемма показывает, что чистый поток через любой разрез одинаков и равен величине потока. Лемма 26.5. Пусть г" — некоторый поток в транспортной сети С с источником з и стоком 1, и пусть ($, Т) — разрез С. Тогда чистый поток через ($, Т) равен ,г($,Т) = (Д. Доказательсюизо. Заметим, что согласно свойству сохранения потока Г" ($ — з, У) = О, так что Непосредственным следствием леммы 26.5 является доказанный ранее результат — уравнение (26.3) — что величина потока равна суммарному потоку, входящему в сток. Другое следствие леммы 26.5 показывает, как пропускные способности разрезов можно использовать для определения границы величины потока. Следствие 26.6.
Величина любого потока Г в транспортной сети С не превышает пропускную способность произвольного разреза С. Доказаюиельстзо. Пусть ($, Т) — произвольный разрез С, а Г" — некоторый поток. Согласно лемме 26.5 и ограничениям пропускной способности, ~Д = г($,Т) = ~ ~ )'(и,е) < ~~) ~ с(и,о) = с($,Т). ~аз иет вез иет Непосредственно из следствия 26.6 вытекает, что максимальный поток в сети не превышает пропускной способности минимального разреза. Сейчас мы сформулируем и докажем важную теорему о максимальном потоке и минимальном разрезе, в которой утверждается, что значение максимального потока равно пропускной способности минимального разреза.
Теорема 26.7 (О максимальном потоке и минимальном разрезе). Если Г' — не- который поток в транспортной сети С = (У, Е) с источником з и стоюм т, то следующие утверждения эквивалентны. Я$, Т) = ~ ($, У) — ~ ($, $) = =У($1') = =У(з,)г)+У($ — з,У) = =У(з,1') = =й. (согласно лемме 26.1, часть (3)) (согласно лемме 26.1, часть (1)) (согласно лемме 26.1, часть (3)) (поскольку )'($ — з, У) = 0) Глава 26. Задача о максимальном потоке 749 1.
г" — максимальный поток в С. 2. Остаточная сеть Су не содержит увеличивающих путей. 3. Щ = с(Б, Т) для некоторого разреза (Б, Т) сети С. Доказангниьслгво. (1) ~ (2): Предположим противное: пусть Г" является максимальным потоком в С, но Су содержит увеличивающий путь р.
Согласно следствию 26.4, сумма потоков Г" + Гр, где Гр задается уравнением (26.6), является потоком в С, величина которого строго больше, чем [Я, что противоречит предположению, что Г" — максимальный поток. (2) =ь (3): Предположим, что Су не содержит увеличивающего пути, т.е. Су не содержит пути из и в г. Определим Б = (и е У: в Су существует путь из а в и) и Т = У вЂ” Б. Разбиение (Б, Т) является разрезом: очевидно, что а е Б, а г ф Б, поскольку в Су не существует пути из а в 1. Для каждой пары вершин и е е Б, и е Т справедливо соотношение у (и, и) = с(и, и), поскольку в противном случае (и, и) е Е~ и и следует поместить во множество Б.
Следовательно, согласно лемме 26.5, Щ = у (Б,Т) = с(Б,Т). (3) ~ (1): Согласно следствию 26.6, [Г"[ < с(Б, Т) для всех разрезов (Б, Т), поэтому из условия [у [ = с (Б, Т) следует, что г — максимальный поток. ° Базовый алгоритм Форда-Фалкерсоиа При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток у вдоль каждого ребра данного пути увеличивается на величину остаточной пропускной способности су (р). Приведенная далее реализация данного метода вычисляет максимальный поток в графе С = (К Е) путем обновления потока у [и,п] между каждой парой вершин и и и, соединенных ребром'.
Если вершины и и и не связаны ребром ни в одном направлении, неявно предполагается, что Г" [и, и] = О. Предполагается, что значения пропускных способностей задаются вместе с графом и с(и, и) = О, если (и, н) ф Е. Остаточная пропускная способность су (и, и) вычисляется по формуле (26.5). В коде процедуры су (р) в действительности является просто временной переменной, в которой хранится остаточная пропускная способность пути р. 'Квадратные скобки используются, когда идентификатор (в данном случае г) трактуется как изменяемое поле, а когда зто функпня — используются круглые скобки.
Часть Ч1. Алгоритмы для работы с графами 750 РО80 Вл.кензо(С> я, т) 1 1ог (для) каждого ребра (и, и) Е Е1С] 2 По Ди, и] +- О У[о, и] О 4 и'И!е существует путь р из и в 1 в остаточной сети Су 5 я1о су(р) +- пйп (су(и, и): (и, и) принадлежит р) б 1ог (для) каждого ребра (и, и) ш р 7 Йо 7" '1и, и] - Ди, и] + су(р) 8 Л.л] --Лъ,.] Приведенный псевдокод алгоритма Рокп Рзл.кбкбом является расширением приведенного ранее псевдокода Ропп Рпькекзон Мнтноп. На рис. 26.5 показаны результаты каждой итерации при тестовом выполнении. Строки 1-3 инициализируют поток 7" значением О.
В цикле зчЬПе в строках 4-8 выполняется неоднократный поиск увеличивающего пути р в Су„и поток 7" вдоль пути р увеличивается на остаточную пропускную способность су (р). Когда увеличивающих путей больше нет, поток 7" является максимальным. Остаточная сеть на рис. 26.5а — это исходная сеть С; поток 1', показанный на рис. 26.5д, является максимальным потоком. Анализ метода Форда-Фалкерсона Время выполнения процедуры РОкп РтзькбкзОи зависит от того, как именно выполняется поиск увеличивающего пути р в строке 4.
При неудачном методе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно сходится к максимальному значению потоказ. Если увеличивающий путь выбирается с использованием поиска в ширину (который мы рассматривали в разделе 22.2), алгоритм выполняется за полиномиальное время. Прежде чем доказать этот результат, получим простую границу времени выполнения для случая, когда увеличивающий пуп выбирается произвольным образом, а все значения пропускных способностей являются целыми числами. На практике задача поиска максимального потока чаще всего возникает в целочисленной постановке.
Если пропускные способности — рациональные числа, можно использовать соответствующее масштабирование, которое сделает их целыми. В таком предположении непосредственная реализация процедуры РОкп РОз кинзой имеет время работы О (е ] г" ]), где 7"* — максимальный поток, найденный данным алгоритмом. Анализ проводится следующим образом. Выполнение строк 1-3 занимает время 9 (Е). Цикл ткйае в строках 4-8 выполняется не бо- Метод Форда-Фалкерсона может работать бесконечно, только если значения пропускной способности ребер яаляются иррациональными числами. Глава 26.
Задача о максимальном потоке 751 т 1// ( /// (,,~ и Рис. 26.5. Работа базового алгоритма Форда-Фалкерсона (послеловательные итерации цикла чгвйе). В левой части кажлого рисунка показана остаточная сеть Су с выделенным увеличивающим путем р; в правой части показан новый поток у, который получается в результате прибавления ~р к ~ лес ~~'~ раз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу. Работа внутри цикла зтЫ1е зависит от того, насколько эффективно организовано управление структурой данных, используемой для реализации сети С = (У, Е).
Предположим, что мы поддерживаем структуру данных, соответствующую ориентированному графу С/' = (К, Е"), где Е' = ((и, о): (и, о) б Е или (о, и) б Е). Часть Ч1. Алгоритмы для работы с графами 752 б) а) в) Рис. 26.6. Транспортная сеть, лля которой выполнение процедуры Ровп Р~л.кнкзом может занимать время тт(Е (~'(), (,1'*) = 2000000 Ребра сети С являются также ребрами графа С', поэтому в этой структуре данных можно довольно легко хранить пропускные способности и потоки. Для данного потока г" в С, ребра остаточной сети Сг состоят из всех ребер (и, ц) графа С', таких что с (и, о) — г" 1и, и1 ф О. Таким образом, время поиска пути в остаточной сети составляет 0 (У+ Е') = 0 (Е), если используется только поиск в глубину или поиск в ширину.
Каждая итерация цикла ттп11е занимает время О (Е), так что в результате общее время выполнения процедуры Рокп Ри.кнкзглч составляет О (Е 1,г"' ~). Когда значения пропускных способностей являются целыми числами и оптимальное значение потока ~~" ~ невелико, время выполнения алгоритма ФордаФалкерсона достаточно неплохое.
Но на рис. 26.6а показан пример того, что может произойти в простой транспортной сети, с большим значением ~ Г" 1 Величина максимального потока в данной сети равна 2 000 000: 1 000 000 единиц потока идет по пути з -+ и -+ 1, а другие 1 000 000 единиц идут по пути з -~ ц -+ т. Если первым увеличивающим путем, найденным процедурой Роищ Ргл.кнкзом, является путь з и с -> 1, как показано на рис. 26.6а, поток после первой итерации имеет значение 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
