Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 22
Текст из файла (страница 22)
Наконец, стоимость этого двойственного допустимого решения равна Х Т(х, у)Ь(х, у) = Х Ь(х, у)=-С((Р', Я~) ьз Ы, о1о е 1м чы Е: ко Ф, но К' Из теоремы 6.1 вытекает наш основной результат. Теорема 6.2. (теорема о максимальном потоке и минимальном разрезе). Вели шна потока из ь в ( не прыюсходит пропускной способноопи С(ИУ, (Р) любого жррозреза. Более того, негичина лшксимального потока равно пропускной способности минимального разреза, и поток 1, и разрез (У, )Ь') одновременно оптимальны в том и только том случае, если ~(х, у)=-О для дуг (х, у)ЕЕ, таких, что хЕ)о' и убей', ~(х, у)=Ь(х, у) для дуг (х, у) ЕЕ, таких, что хЕ(о' и уЕУ. (6.6) доказа~пельство.
То, что о не превосходит пропускной способности любого разреза, непосредственно следует из предыдущей теоремы. Из алгоритма пометок, рассматриваемого а следующем параграфе, будет следовать, что произвольный максимальный поток величины о всегда можно использовать для построения некоторого разреза с пропускной способностью С=о. Равенства (6.6) выражают условия дополняющей нежесткости, что вытекает из следующих рассуждений. Если хЕ Ю" и у Е Ю', то двойственное неравенство п(х) — л(у)1 у(х, у) .-! — ОтО)О 124 Гл.
б. Ллгориамы Форда — Фалкарсона и Дейкстры является строгим, что было отмечено выше, поэтому соответствующая переменная 1(х, у) должна равняться нулю. Аналогично, если х Е )е' и у б У, то из (6.5) следует у(х, у)=1, поэтому соответствующее неравенство в прямой задаче )(х, у) (Ь(х, у) должно обратиться в равенства Пример 6.1. На рис. 6.2 приведен пример задачи о максимальном потоке с оптимальным потоком величины 5 и соответствующим минимальным разрезом. Заметим, что все прямые дуги через разрез Рис.
6те Задача о максимальном потоке. Числа в кружкак — пропускные способности; числа без нружков — максимальный поток; множество Яу задает минимальный разрез. насыщены (1(х, у)=Ь(х, у)) и все обратные дуги пусты (1'(х, у)=0), что подтверждает равенства (6.6) и показывает, что этот поток и разрез оптимальны. 6.2 Алгоритм пометок Форда н Фалкерсона Рассмотрим теперь более подробно прямо-двойственный алгоритм для задачи о максимальном потоке, построенный в конце предыдущей главы. Напомним, что задача, двойственная к ограниченной прямой задаче (ДОП), была подзадачей поиска пути из а в й вдоль которого поток можно увеличить. Когда такого пути найти не удается, то выполняются условия дополняющей нежесткости, и прямо-двойственный алгоритм дает оптимальное решение. Следующее определение характеризует путь, который мы ищем.
Определение 6.2. Пусть дана сеть Аг=(в, 1, У, Е, Ь) и допустимый поток )' из з в й Тогда увеличивающим путе,и называется любой путь Р из з в (в неориентированном графе, полученном из графа 6 сети игнорированием направлений дуг, который обладает следующими свойствами. а) Для любой дуги (1, )) е Е, проходимой путем Р в прямом на. 6.2. Алгоритм наметок Форда и Фалкерсана 125 правлении (и называемой прямой дугой), )'(1, )) ..(з(1', 1). То есть прямые дуги пути Р ненасыщенны. б) Для любой дуги (1, 1)ЕЕ, проходимой путем Р в обратном направлении (и называемой обратной дугой), 7(), 1))0.
() На рис. 6.3 показан увеличиваюший путь в сети, представленной на рис. 6.2. Дуга (а, е) является обратной дугой в пути Р. О с 1 Рис. 6.3. Точечные линии указывают увеличи. вающий путь. Числами без кружков показан поток величины 1; числа в кружках — пропускные способности.
Очевидно, что можно увеличить поток из з в 1 без нарушения закона сохранения потока во всех вершинах, увеличивая поток на Рис. 6ли Результат увеличении потока в сети, приведенной на рис. 6.3, каждой прямой дуге пути Р и уменьшая поток вдоль каждой обратной дуги При этом поток можно увеличивать до тех пор, пока не нарушится ограничение пропускной способности на некоторой прямой дуге или некоторая обратная дуга не станет пустой.
Таким образом, максимально возможная величина увеличения потока вдоль Р определяется формулой 6 =- ш(п (Ь(1', 1) — ) 0, 1) для прямой дуги ~(), 1) для обратной дуги аз Р 126 Гл. 6. Алгоритмы Форда — Фалкерсона и Дейкстры В примере на рис. 6.3 получаем 6=1; результат увеличения потока на эту величину представлен на рис.
6.4, где величина потока из в в 1 возросла с 1 до 2. Нам осталось описать систематическую процедуру нахождения увеличивающего пути, если такой путь существует, Такая процедура будет состоять в продвижении пометок из в до того момента, когда либо будет достигнуто 6 либо процесс застопорится, Каждой вершине х будет приписываться пометка, состоящая из двух частей, пометка(х)=(Е!(х], Е2 [х)). Здесь ЕПх) — информация о том, [т, ш[п [ Г2 [к ), Ык, У)-1[К, У) ) ) У [-.т, пип [ Ь2[к],1[у,к)) ) У (в)[к),Ь2[ т, у) [1! [к), Ь2[ Рис. 6.5. Два возможных случая приписывания пометии вершине д при просмотре к откуда х помечалось, н Е2[х! — величина дополнительного потока, который можно провести из з в х.
Процесс распространения пометок из данной вершины х называется просмотром х, и мы будем хранить список, называемый СПИСОК, помеченных, но ие просмотренных вершин. Детали этого процесса просмотра вершины х приведены на рис 6.6 Возможны два случая Если вершина у ие помечена и имеется дуга из х в у, то у можно пометить тогда, когда 1(х, у)( Ь(х, у); в этом случае положим Е[[у[:= х, Е2[у~: — п1ш (12[х1, Ь(х, у) — ) (х, у)).
Это означает, что вершина у была помечена из х и что поток можно увеличить на меньшую из двух величин Е2 (х) и Ь(х, у) — 1(х, у). Если вершина у не помечена и имеется дуга из у в х, можно пометить у из х, если 1(у, х))0; в этом случае положим Е[[у~: = — х, Е2 [у~: = ш!п (Е2 [х~, ) (у, х)). Заметим, что в Е! использован знак минус, который говорит о том, что пометка получена вдоль обратной дуги. Алгоритм начинает работу с просмотра вершины э н включения в СПИСОК всех вершин, помечаемых из к Затем процесс повторяется: выбирается и просматривается некоторая вершина х, входящая в СПИСОК, и все вершины, помечаемые из х, добавля- 127 6.2. Алгоритм пометок Форда и Фолкерсоыо ются в СПИСОК.
Этот процесс останавливается в одном из двух случаев: либо 1 получает пометку, тогда можно восстановить увеличивающий путь обратным просмотром из (с использованием Е!, либо СПИСОК окажется пуст. В первом случае мы увеличиваем АЛГОРИТМ ФОРДА и ФАЛКЕРСОНА Вход. Сеть Ы=(з, 1, Ч, А, Ь). Выход.
Максимальный поток 1 в )Ч, Ьей!п 1: = О (сопппепг: задание начального потока) снова: положить все пометки раиными О, положить СПИСОК: =(з), (сошшеп!< выбрать начальные денные для поиска нового увеличиваю. щего пути) жь!!е СПИСОК Ф Я йо Ьед!п пусть х — любая вершина из СПИСОК', удалить х иэ СПИСОК; ПРОСМОТРЕТЬ х; !1 ! помечена Щеп Ьей!и увсличить поток 1 вдоль увеличивающего пути; ио !о снова епб епб епб ргосебиге ПРОСМОТРЕТЬ Ьед!п помоги гь все непомеченные вершины, в которые ведут ненасыщенные дуги из х, занося новые помеченные вершины в СПИСОК; пометить все нет<меченные вер пины, из которых в х идут дуги с положительным потоком, занося новые помеченные вершины в СПИСОК; епб Рис.
6.6. Алгоритм Форда и Фалкерсона для решения задачи о максимальном потоке. поток вдоль увеличивающего пути, во втором случае, как будет показано ниже, мы получаем оптимальный поток. Набросок этого алгоритма приведен на рис. 6.6. Покажем геперь, что этот алгоритм может остановиться только после достижения оптимальности (причем покажем это, не опираясь на тот факт, что алгоритм был получен как прямо-двойственный алгоритм). Теорема 6.3. Если алгоригпж пометок Форда и Фалкерсона останавливается, вто означаегп, что получен оптимальный поток. Доказательство. После остановки алгоритма некоторые вершины помечены и некоторые не помечеяы. Обозначим множество помеченных вершин через (Р и множество непомеченных вершин через ))г, как показано на рис.
6.7. Все дуги (х, у), ориентированные из 128 Гл. б. Ллгаригамм Форда — Фалкгрсона и Глейксгарм йл в й', должны быть насыщены, ибо в противном случае у должна была бы быть помечена во время просмотра х. Аналогично, все дуги (у, х), ориентированные из Т в (тт, должны быть пусты, ибо в противном случае у также должна была бы быть помечена во время просмотра х. Следовательно, (Ю', У) — минимальный разрез, и по теореме 6.2 поток должен быть оптимальным.
Пример 6.! (продолжение). На рис. 6.8 показан результат применения к потоку величины 2. представленному на рис. 6.4, трех ттассппе1пгмс гаго Рнс. 6.7, Множества Нг к 'кт а конке алгорнтма пометок Форда к Фалкерсопа. операций увеличения потока, приводящих к опгимальному потоку величины 5. Этот оптимальный поток отличен от оптимального по. тока, представленного на рис, 6.2, однако минимальный разрез оказался тем же. (В этом примере мы допустили любые промежуточ. ные увеличивающие пути, чтобы проиллюстрировать распространение пометок по обратным дугам. Алгоритм поме~ок не мог бы найти первый увеличивающий путь, показанный на рис. 6.8, а нашел бы некоторый другой.
Зто, однако, никак не влияет на утверждение теоремы 6.3.) ( ) Проблеме конечности алгоритма пометок Мы показали, что если алгоритм пометок Форда и Фалкерсона останавливается, то в результате он находи~ поток оптимальной величины. Но откуда известно, что этот алгоритм останавливается после конечного числа итерацийг Ответ может несколько удивить, поскольку все рассмотренные до снх пор алгоритмы были конечными. На самом деле если пропускные способности Ь иррациональны, то алгоритм пометок можа не остановиться Очевидно, что в том случае, когда пропускные способности Ь— целые числа, алгоритм конечен, поскольку при каждой операции увеличения потока величина потока возрастает по крайней мере на (, б.б. Проблема кокечкосапг алгорагпма пометок О' О' Заклкгчительпое множество помеченных- вершин Рис.
6.6. Три увеличения потока, изображенного на рис. 6.4, приводящие к оптимальному потоку величины 5. кг зозз <30 Гл. 6. Алгоритмы Форда — Фолкерооио и Дейкотры (6.6) Отсюда, а„+„— — а„— а,э, с начальными условиями а,=! и а,=о=(ргб — 1)12(! используя индукцию, нетрудно показать, что а,=а', < =О, 1, (6.7) На шаге О будет производиться только одно увеличение потока па величину а„поэтому величина суммарно<о по~ока будет стремиться к пределу а, + (а, + а,) + (а, + а,) +... = ах+ а, + а, +... =, = 5. (6.8) ! На рис.
6.9(а) приведена сеть со следующими вершинами: исток Ы с<он й 4 вершины к„, к, н 4 вершины у„..., ул. Дуги в сети двух типов: 4 особые дуги А,=-(к;, <й) и неособые дуги, имеющие вид (ы к,), (уь у,), (у„к,), (к„у,) или (у,, !), (~!. Для особых дуг пропускные способносги таковы: и„для А,, а, для А, и а, для Ал и А, Все неособые дуги имею< пропускные способности 5. Операции увеличения и<пока будут выполня1ься следующим образом. Шаг О.
Выберем увеличивающий путь (ь, к„у„!) и величину увеличения а„. Это приводит к упорядоченному множесзау (О, а„а„а.,) остаточных пропускных способностей особых дуг. Шаг п (и ) 11 В иочогтве базиса индукции допустим, что А„А<. А;, А; — п<комгуое УпоР>щочш<ьн особых д)г с ост <оч. и если величина максимального потока равна о, то возможно не более о увеличений потока Точно так же, если пропускные способности рациональны, можно привесгп их к общему знаменателю Р, изл<енить масшгаб в 0 раз и, используя ге же рассуждения, за. ключить, что возможно не более 0о увеличений потока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
