Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 22
Текст из файла (страница 22)
8. МА11СИМАЛЬНЫИ' ПОТОК !36 числа удовлетворяют следующим линейным ограничениям: — о, если ) =в, ~~,х11 — ~~~~хо«= О, если )~в, г, 1 А о, если )=О о)О, О ( хм ~» ЬЫ ДлЯ всех 1, ). (2) Здесь первая сумма берется по дугам, ведущим е узел У1, а вторая сумма — по дугам, ведущим из узла 1«1. Неотрицательное число о, фигурирующее в (1), называется величиной потока. Число хы Называется потоком по дуге А11, нли дуговым потоком. Заметим, что ограничения (1) выражают тот факт, что в каждый узел (кроме источника и стока) приходит столько потока, сколько нз него выходит (условие сохранения). Ограничение (2) означает, что поток х;, по дуге ограничен пропускаой способностью дуги Ь1п Ограничения (1) — (2) напоминают законы, согласно которым поток воды движется в водопроводе.
!1о в дойствнтельпостн не существует такого потока воды, который бы подчинялся условиям (1) — (2). Чтобы это уяснить, рассмотрим сеть на рис. 8.1 с источником У1 и стоком 1««. Предположим, что все дуги нме1от пропускную способпость, равную единице. Рассмотрим следующее множество неотрицательных целых чисел: х,г — — 1, хм =- 1, остальные хм =- О. Эти числа удовлетворя«от ограничениям (1) н (2). Но для любой жидкости в трубопроводе, соответствующем рис. 8А, будет выполняться условие: х«г ФО, если х,г -— — 1. Чтобы сеть соответствовала трубопроводу, будем считать, что трубопроводная система имеет множество клапанов в ка кдом узле, которые не позволяют жидкости распространяться из узла одновременно по всем дугам, которые инцидентпы (примыкают к) данному узлу.
Очевидно, что задача нахождения величины максимального потока в любой сети является задачей линейного программирования с целевой функцией о .= ~~ хм и ограничениями (1) — (2). Но поскольку это весьма специальный случай задачи линейного программирования, здесь мы получим более эффективные алгоритмы, чен симплекс-метод для общей задачи линейного программирования.
В том случае, когда сеть является цепью У„А11, Ум А «3,... ..., Х«с источником 1111 И СтОкОм 1«ю максимальная величина потока, который может быть пропущен через сеть, ограничивается ыипил«альпой из пропускных способностей дуг этой цепи. Здесь дуга с минимальной пропускной способностью является «узким место«1«в сети. Теперь мы дадим общее определение «узкого местаъ в произвольной сети. 8 1. Ввкдвнив (Зт Введем понятие разреза (Х, Х), где Х вЂ” некоторое подмножество узлов сети, а Х вЂ” дополнение подмножества Х.
Разрезом (Х, Х) называется множество всех дуг Аы, для которых либо №с Х, Л'ус Х, либо ЖтЕ Х, №с Х'). Таким образом, разрез представляет собой множество дуг, удаление которых из сети превращает сеть в несвязную. Разрез (Х, Х) называется раздоляющнм узлы № и № (или отделякицим узел № от Л'е), если №ЕХ, а №ЕХ. Пропускной способностью, или величиной, разреза (Х, Х) называется с(Х, Х).=-~ Ьы, где сумма берется по всем ориентировань 3 пым дугам, ведущим из №Е Х в Хвс Х, н по всем пеорнентированным дугам, соединяющим №ЕХ н Л'ус Х.
Заметим, что при определении разреза мы учитываем все дуги между мпо;ьеством Х и мповкеством Х, а при определении пропускной способности разреза мы учитываем только пропускные способности дуг из Х в Х и не учитываем ориентированные дуги нз Х в Х. 11оэтоыу, вообще говоря, с(Х, Х) чьс(Х, Х), Разрез (Х, Х), разделяющий ту, и й о является аналогом «узкого места» в произвольной сети. Ясно, что благодаря ограничениям (1) — (2) величина о максимального потока меныпе нли равна пропускной способности любого разреза, разделяющего Р»', и № «). 11о вот что удивительно: величина максимального потока всегда равна минимальной пропускной способности всех разрезов, разделяющих 1(т, и Дсь Разрез, разделяющий« 1»', и № и обладающий минимальной пропускной способностью, называется льняималычыле разрезом.
(Впредь для простоты будем иногда опускать слова «разделяющий узлы тв', и №ю) Теорема о равенстве величины максимального потока пропускной способности минимального разреза впервые была доказана «1«ордом и Фалкерсоном [бй). Эта ») В книге Форда и Фалкерсона [671 разрез определяется несколько иначе: разрезоы называется множество дуг ЛЫ, для которых К; Е Х, в"тЕ Х. — Прим. перев, т) Здесь автор использует тот факт, что с= р'' хц — ~" х;. тв;ЕХ, »С ее Х, Ятей (Чтобы получить »то состяошение, надо сложить те уравкеавн ((), которые относятся ко всем Пе Е Х, в нрввестз южобпые члены.) Так как в силу (2) хц~( ~ Ьп=с(Х, Х), а ~, хп м О, то и ~~ с(Х, Х).— Прим. перев. Хтск М,ЕХ У ЕХ гл, я.
млкснмл ишь[и потогз теорема, названная тооремой о максимальном потоке и минимальном разрезе, является основной в теории потоков в сетях. Приведем конструктивное доказательство этой теоремы (сзг (65)), в процессе которого строится максимальный ноток п находится минимальный разрез.
Если мы покажем, что всегда существует поток, величина которого равна пропускной способности некоторого разреза, то теорема будет доказана, поскольку максимальный поток не превосходит пропускной способности зпобого разреза, и в частности. минимального. Тгогвмл 8.1. (О максимальном потоке и минимальном разрезе (64), [65).) В любой сети величина максимального зготока из источника ЛГ„в сток Л', равна пропускной способности минимального разреза, разделяющего гу, и )уь Донлзлтьлы.тво ').
1'ассмотрим некоторое произвольное мнозкество неотрицательных чисел хы, удовлетворяющих условиям (1), (2). Если величина этого потока равна пропускной способности некоторого разреза, то теорема доказана. Если же нет, то величину потока можно увели швать но приводимому ниже правилу до тех пор, пока она не станот равной пропускной способности нокоторого разреза. (Заметим, что лшожество неотрицательных чисел хы, удовлетворяющих условизгм (1), (2), всегда существует: например, можно взять хы — О для всех 1 и 1). Изгея произвольный поток (х;;) в сети, настроим по нему рекуррентно подмножество узлов Х по следующим правилам: О. Лг,сХ. 1.
Если.Д'; ЕХ и хы(бы, то ХгЕХ, 2. Гслн Л'; с Х н хг; ) О, то Хв с Х. Узлы, не припадложащие подмножеству Х, отнесем и множе- ству Х. Используя эти правила для построения множества Х, получим один нз двух возможных результатов. 1". Узел гУ, попадает в множество Х. Тогда для всох зуг, ведущих из х в х, вьнголннетсн: здг-..—.бп (согласно правилу 1), и не существуот дугового потока хя ) О из Х в Х (согласно правилу 2). Отсгода хп =. Ьы и хп — О.
у ..~ с., йх ;ех зех гел зех Следовательно, получен ноток, величина которого равна с (Х, Х). ') Лвтвр приводят доказатет,ство ддя случая, когда дуговые оронусвнья способности аы цсзсчнсленны. Теорема о максимальном котове н мкянма:и,- вом разрезе верна н в более общем случае, когда ве;шчнны Ь~ — произвольные действительные числа (65).— Прая. перев. 2'.
Узел !л'! попа;!нет в множество Х. '1'оглн из определения мпо;кества Х следует, что существует путь иэ !л', в й и ока;кем !л!„.... Л'!, А;;,,, ..., йлс!, в котором для каждой дуги либо хк;!л(6с; !, либо х;„ь;>О. При двпжепии по пути из !У, в Л'! ыекоторьле его дуги будут пройдены в направлении, совпадагощем с их ориентацией (такие дуги называются прямыми дугами этого пути), другие — в направлении, противоположном их ориептацин (такие дуги пазывалотся обратными дугамп этого пути). Из определопия множества Х следует, что существует путь из !Уг в !У„в котоРом х;;, ( Ь... ца всех пРнмых дУгах Л;;+, этого пути и х;,,; » О на всех обратных дугах Л гл! !.
Пусть е,— минимум ра!и!остей Ьь;+, — х!, лз.„взятый по всем прямым дугам этого пути, а ее — минимум величин х!.л! л, взятый по всем его обратным лугам. Тогда е -- !плп (е,, ег) — положительное число. Начнем вычислеппя с целочислепыого потока (цаприллер, пулевого), тогда величина е будет целым положительным числом. Можно увеличить па е потоки хы па всех прямых дугах этого пути и уменьшить на е потоки х,; на всех обраткьлх дугах пути. Таким образом, величина потока увеличится на е и поные зпачепия х;'; будут удовлетворять всем ограничениям (1), (2). Используя этот поный поток, можно построить новое лшожестно Х. Коли узол Дс! по-прежнему прп этом ока;кется н Х, го можно снова увеличить величину потока и т.
д. Так как пропускная способность минимального разреза — конечная величина, а па каждом шаге величина потока возрастает по крайней мере ыа единицу, то после конечного числа шагов мы всегда получим максимальпый поток. ° Обозпачим через Гм мпожество неотрицательных чисел хы, удовлетворялощих огра!плчециял! (1) — (2). Будем называть путь из !У,, в 1У! Увеличиваюи1и.к поток Г„, если хы ( Ьы ыа всех пРЯ- мых дугах и хп ) О ыа всех обратпых дугах этого пути. Из доказательства теоремы 8.1 вытекает Следствие 8.1. Поток Гл, максима еп тогда и то.лько тогда, когда не суи1ествует путп, увеличивало<цего поток с"„!. Сделаем несколько замечаний.
Величина максгылальпого потока в:побой! сети принимает, безусловпо, единственное значение. Но может существовать ыосколт<о разлпчпых максимальыых потоков г'„, имелощых одинаковую величину. Может существовать и песколько ллицимальных разрезов в соти. Рассмотрим, например, сеть па рис. 8.2. Полок;им, что все дуги пмелот пропускные способности, равные едипице. Тогда и дуга А ге, и дуга Лг, я!ьти!ется мипимальпычи разрезалш. Величина максимального потока, копсчно, равыа 1.
11о максимальных пото- ГЛ. З. МАКСИМАЛЬНЫЙ петен 140 ков здесь 51 =х =1, = хз~ — — 1, Р и с. 8.2. Тковнма 8.2. Пусть разделяющие АЕ, и ЕУо ДоказАтвльство. Если Х с: У, то Х() У=У, ХПУ=Х, по- этому (Х()У, Х()~)=(У, У), (Хп У, Хп У)=(Х, Х), ХП~ =а ХПУ=Л, ХПУ=Л. Р к с. 8.3. Тогда Аг б К, Аг~ Е Л, Х = 0 () 8 Х = Р О Л У = — Р () 0* У = Л () 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
