Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 167
Текст из файла (страница 167)
На рис. 26.4, (а) воспроизведены транспортная сеть С и поток Г", представленные на рис. 26.1,(б), а на рис. 26.4, (б) показана соответствующая остаточная сеть С г. Ребра в Ег являются либо ребрами нз Е, либо обратные им, и, таким образом, ')ЕГ~ < 2 (Е) Заметим, что остаточная сеть Су подобна транспортной сети с пропускными способностями, задаваемыми с). Она не удовлетворяет нашему определению транспортной сети, так как может содержать одновременно и ребро (и, и), и обратное ему ребро (и, и). Помимо этого различия, остаточная сеть обладает всеми свойствами транспортной сети, и мы можем определить поток в остаточной се- 12)12 «.~,:з',=,.:Ф 11Л4 Г,.=«11)!" Г.«з з)г - --~(,' У):* «~::) 11)14 «.-'» 12 г) в„ 1! Часть !7. Алгоритмы дла рабаты с графами 75б ти как удовлетворяющий определению потока, но по отношению к пропускным способностям с1 сети С1.
Поток в остаточной сети предоставляет указания по добавлению потока к исходной транспортной сети. Если ( представляет собой поток в С, а (' представляет собой поток в соответствующей остаточной сети С1, определим увеличение (аиязпеп!аГ)оп) (Т Г' потока Г' на (' как функцию, отображающую 1' х )7 на К, определенную следующим образом: ( ((и, и) + ('(и, и) — ('(и,и), если (и, и) Е Е , '(О в противном случае . Интуитивно понятно, что это определение следует из определения остаточной сети. Мы увеличиваем поток в ребре (и,и) на ~'(и,и), но уменьшаем его на У'(и, и), поскольку пропускание потока по обратным ребрам в остаточной сети означает уменьшение потока в исходной сети. Пропускание потока по обратному ребру в остаточной сети известно также как еокраа4еиае (сапсе!)абоп).
Например, если мы пересылаем б ящиков с хоккейными шайбами из и в и, а 2 ящика — из и в и, то это эквивалентно (конечно, с точки зрения окончательного результата, а не оплаты перевозок) пересылке 3 ящиков из и в и, и ничего — из и в и. Сокращения такого вида являются ключевым моментом любого алгоритма максимального потока. Лемма 26.1 Пусть С = ((7, Е) является транспортной сетью с истоком в и стоком ! и пусть ,( представляет собой поток в С. Пусть С1 — остаточная сеть С, порожденная 1, и пусть 1' — поток в С1.
Тогда функция 1 '! г', определенная в уравнении (26.4), представляет собой поток в С с величиной ~У 1 У! = ~У! + ~У! Доказаагельсагво. Сначала убедимся, что г'Т (' подчиняется ограничению пропускной способности для каждого ребра в Е и сохранению потока в каждой вершине в $" — (а, !).
В случае ограничения пропускной способности сначала заметим, что если (и,и) Е Е, то с1(и,и) = ((и,и). Таким образом, мы имеем г'(и,и) ( с1(и, и) = 1(и, и), а следовательно ( 1 Т г') (и, и) = ((и, и) + ('(и, и) — 1'(и, и) (согласно уравнению (26.4)) > ((и,и) + ('(и,и) — 1(и,и) (поскольку ~'(и,и) (1(и,и)) = 1 (и,и) >О. Глава 76. Задача о макоамальлом ломаке 757 Кроме того, (п~'и., ) = Пи,е) < 5(и,е) < 5(и,е) = З(и,е) = с(и,е) . + 5'(и, е) — 7"'(е, и) (согласно уравнению (26.4)) + г (и,е) (так как потоки неотрицательны) + с7(и,е) (ограничение пропускной способности) + с(и, е) — 5(и, е) (определение с7) В случае сохранения потока, поскольку и З, и ~' подчиняются свойству сохранения потока, для всех и Е $' — (з,е) имеем ЯЦ Т ~ )(и, е) = ~~> (5 (и, е) + 7 '(и, е) — З (е,и)) оЕУ оЕУ = ~~> З(и,е)+~~~ З (и,е) — ~» 5 (е,и) оЕУ оЕУ оЕУ = ~~) 5(е,и)+ ~~) ~'(е,и) — » ~'(и,е) эЕУ оЕУ оЕУ = ~~> ()(е, и) + З (е,и) — 5 (и,е)) оЕУ =ч,ОТ~'И .), ~ХТХ'~ =',»".
(ПХ')(, ) - ~(ХТХ') (, ) оЕУ оЕУ =,». (ПТ~')(, )- »:иТ~')(, ), (26.5) оЕ Уь оЕУл где вторая строка следует из того, что (7" З Г')(ле,х) равно О, если (ле, х) ф Е. Теперь применим к уравнению (26.5) определение з Т з', а затем переупорядочим где третья строка следует из второй согласно сохранению потока. Наконец вычислим величину 7"З 7"'. Вспомним, что антипараллельные ребра в С (но не в СЗ) запрещены, а следовательно, для каждой вершины е е $' мы знаем, что может иметься либо ребро (д,е), либо ребро (е, л), но не оба одновременно.
Определим Ъ~ = (е: (л,е) е Е) как множество вершин с ребрами из л, а $7з = (е: (е, л) Е Е) как множество вершин с ребрами в ж Мы имеем Ъ~ 0 Ъ~ С у' и, поскольку антипараллельные ребра запрещены, Ъ'1 П уз = И. Теперь вычислим Часть И. Алгоритмы для рабаты с графами 758 и сгруппируем члены, чтобы получить ~ХТГ~ = ~,(У( )+У'(а с) — У'(с,а)) — ~ У(у, )+У'(у, ) — Х'(ь,у)) иЕУ| иЕУа =,>, У( У) + ~, У'(з, ) — ~, 5'(си в) иЕУь иЕ Ь'ь иЕУ1 -,').Пс, )-~Г'(с,з)+~.у'(а, ) иЕЪа иЕУа иЕУа =, 'Па,с)-, 'У(сил) иЕУ1 иЕЪа + ,').
Г(а,.) + ~', У'(а, ) — ~; У'(у, а) — ~; Г(у, а) иЕЪ'ь иЕУа иЕУ1 иЕУ2 5'(в, у) — ~~ь 5(у, а) + ~ !и(а, у) — ~ 5'(у, а) . (26.6) иЕЬ1ОУа иЕУ1ОУг иЕУ1 ~~7~'~ = ~~> 5(а, У) — ~~> 5"(с, з) + ~~> !и(з, У) — ~,)и(сил) иЕУ иЕУ иЕУ иЕУ =й+Ф (26.7) Увеличивающие пути Для заданных транспортной сети С = (К Е) и потока 5 увеличивающим пуюем (апйшепг!пй ра1п) р является простой путь из з в ! в остаточной сети С5.
Согласно определению остаточной сети мы можем увеличить поток в ребре (и, у) увеличивающего пути до с5(и, у) без нарушения ограничения пропускной способности соответствующего ребра в исходной сети. Выделенный путь на рис,26.4,(б) является увеличиваюгдим путем. Рассматривая представленную на рисунке остаточную сеть С5 как некоторую транспортную сеть, можно увеличивать поток вдоль каждого ребра данного пути вплоть до четырех единиц, не нарушая ограничений пропускной способности, поскольку наименьшая остаточная пропускная способность на данном пути составляет су(уз, сз) = 4. Максимальная величина, на которую можно увеличить поток в каждом ребре увеличивающего пути р, называется остаточной пропускной способностью (гезЫпа! сарасйу) пути р и задается формулой су (р) = ппп (с5 (и, у): (и, у) принадлежит р) Следующая лемма„доказательство которой предлагается провести в качестве упр.
26.2.7, более строго формулирует приведенные выше рассуждения. В уравнении (26.6) можно распространить все четыре суммы на суммирование по всему множеству !', поскольку все дополнительные члены в зтом случае имеют значения О (в упр. 26.2.! это требуется строго доказать). Таким образом, мы имеем Глава Зб. Задача о таке«мал«кам потоке 759 Лемма 26.2 Пусть С = (Ъ", Е) является транспортной сетью, а 5 представляет собой поток в С, и пусть р является увеличивающим путем в С7.
Определим функцию (р: 17 х Ъ' -+ К как ( с5(р), если (и,и) принадлежит р, (р(и,и) = ~ ( О в противном случае . (26.8) Тогда ( ЯвлЯетсЯ потоком в С7 с величиной ((р! = с5(Р) ) О. Следствие 26.3 Пусть С = (Ъ; Е) представляет собой транспортную сеть, а ( является потоком в С, и пусть р представляет собой увеличивающий путь в С7. Пусть также Зр определен, как в уравнении (26.8), и предположим, что мы увеличиваем ( на (р. Тогда функция (? Ур является потоком в С с величиной ( (? (р! = ( (~ + )~р( > ф.
Доказательство. Непосредственно вытекает из лемм 26.1 и 26.2. Разрезы транспортных сетей В методе Форда-Фалкерсона проводится многократное увеличение потока вдоль увеличивающих путей до тех пор, пока не будет найден максимальный поток. Откуда нам известно, что по завершении алгоритма мы действительно найдем максимальный поток? В теореме о максимальном потоке и минимальном разрезе, которую мы вскоре докажем, утверждается, что поток является максимальным тогда и только тогда, когда его остаточная сеть не содержит увеличивающих путей. Однако для доказательства данной теоремы необходимо ввести понятие разреза транспортной сети. Разрезам (сщ) (Я,Т) транспортной сети С = (17,Е) называется разбиение множества вершин 17 на множества Я и Т = 17 — Я, такие, что в Е Я, а 1 Е Т. (Это определение аналогично определению разреза, которое использовалось применительно к минимальным остовным деревьям в главе 23, однако здесь речь идет о разрезе в ориентированном графе, а не в неориентированном, и мы требуем, чтобы в Е Я, а С Е Т.) Если ( — поток, то частмй поток (пег Вот) ((Я, Т) через разрез (Я, Т) определяется как ,((Я,Т) = ~~ ~~> 1(и,и) — ~~~,((и,и) .
(26.9) ««Я«ет «ез гг Вытекающее из данной леммы следствие показывает, что если увеличить ( на (р, то можно получить новый поток в С, величина которого ближе к максимальной. На рис. 26.4, (в) показан результат увеличения потока 5, представленного на рис. 26.4,(а), на поток Гр, показанный на рис.26.4,(б), а на рис.26.4,(г) показана полученная остаточная сеть. Чесма Рй Алгоритмы для работы с графами тбо -б:Т— Рнс. гб.б. Разрез (Б,Т) в транспортной сети, показанной на рис.гбл,(б), тле Я = (а,ем из), а Т = (оз, пы т). Вершины в б показаны черными, а вершины в Т вЂ” белыми. Чистый поток через разрез (Я,Т) равен т"ф,Т) = 19, а пропускная способносп составляет с(Б, Т) = гб.
Пропускной способностью (сарасйу) разреза (Б, Т) является с(Б,Т) = ~~~ ~~~ с(и,е) . (26.10) иЕБ ьЕТ Минимальным розреюм (пппппщп опт) сети является разрез, пропускная способность которого среди всех разрезов сети минимальна. Асимметрия между определениями потока и пропускной способности разреза является преднамеренной и существенной. В случае пропускной способности мы учитываем только пропускные способности ребер, идущих из Я в Т, игнорируя ребра, идущие в обратном направлении. Что касается потока, то мы рассматриваем поток из Я в Т минус поток, идущий в обратном направлении„из Т в Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
