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