Алгоритмы - построение и анализ (1021735), страница 153
Текст из файла (страница 153)
Покажем соблюдение ограничений пропускной способности. Заметим, что г"' (и, о) < су (и, о) для всех и, о Е У. Поэтому, согласно уравнению (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.4. Пусть С = (1', Е) — транспортная сеть, а Г' — некоторый поток в С, и пусть р — некоторый увеличивающий путь в Су. Пусть Д определен в соответствии с уравнением (26.6). Определим функцию г': $г х Ъ' — К как г"' = ~+~р. Тогда г' является потоком в С и имеет величину ! г"'! = !,г!+)~р~ > (Д. Доказательство. Непосредственно вытекает из лемм 26.2 и 26.3.
Разрезы транспортных сетей В методе Форда-Фалкерсона производится неоднократное увеличение потока вдоль увеличивающих путей до тех пор, пока не будет найден максимальный Глава 26. Задача о максимальном потоке 747 поток. В теореме о максимальном потоке и минимальном разрезе, которую мы вскоре докажем, утверждается, что поток является максимальным тогда и только тогда, когда его остаточная сеть не содержит увеличивающих путей. Однако для доказательства данной теоремы нам понадобится ввести понятие разреза транспортной сети. Разрезом (сш) (Я,Т) транспортной сети С = (У Е) называется разбиение множества вершин на множества Я и Т = У вЂ” Я, такие что в е 5, а ~ е Т.
(Это определение аналогично определению разреза, которое использовалось применительно к минимальным связующим деревьям в главе 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, [Г"[ < с(Б, Т) для всех разрезов (Б, Т), поэтому из условия [у [ = с (Б, Т) следует, что г — максимальный поток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
