Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 40
Текст из файла (страница 40)
Заметим ~еперь, что если Л', б Х е, то сУЩествУет Цепь из Л'е в Л',, в котоРой кал1ДаЯ ДУга АП имеет остаточпу1о пропускную способность Ьн + х11 — 4, ) О, и поло- жительное направление соответственно — от Л11 к ЖП Эта цепь называется обратным путем из Лге в Л",, Аналогично, если Лз с Хм, то существует цепь из Лгг в Л'г., для каждой дуги Аоч которой Ь;;+х,'; — х,'; ) О, и положительное 1) Индексы соответствуют первым буквам английских слов Ьаск1еег1( (обраткый) к (огвег1) (прямой),— Прим. перев ыл.
двгхпводгктовыв потоки 229 направление каждой дуги — направление от Л'«к ЖР Эта цень называется прямым путем из Л'г в Л'г . Прямой и обратный пути могут быть найдены с помощью метода расстановки пометок. Для простоты мы иногда будем называть эти два пути двойным путем из Лг в Лг' Пропускная способность обратного пути определяется как пип(Ьи+х,'; — х»;), где положительное направление дуги Ап— направление от У; к Х~ (минимум берется по всем дугам этого пути). Аналогично, пропускная способность прямого пути равна пп'в (Ь»т+ х,'; — х,';). Очевидно, что двойной путь из Л'«в Л'г существует, если имеются обратный и прямой пути.
Заметим, что обратный и прямой пути идут из узла Л'г в узел Л', и слова «из Л'г в Л «» будем иногда опускать. Имеет место следующая лемма. Лкммл 11А. Разрез (Хгь Хгь), в котором Фг ~Х»ь существует тогда и только' тогда, когда нет обратного пути иг Льг в Л'г . Доклзлтвльство. Пеобходимость. Пусть существует разрез (Хгь, Хгь) в котором Л'г с Хгь. Пусть Аы — любая дуга, связывающая Хгь н Х,ь, такая, что Л';~Хгь и Л'гЕХгь По определению мнок ества Хгь, доля<но выполняться: х,';+ х,'; = Ьп (иначе бы узел )У~бХгь).
Каждая цепь из Фг в Л'г должна содержать по крайней мере одну дугу из (Х„, 7«ь), причем, как мы выяснили, для любой дуги из (Х,ь, Х,ь) Ьп — х,'; — х,';=О. Отсюда следует, что ке существует обратного пути иа Жг в Л'г . Достаточность. Предположим теперь, что не существует обратного пути из Л'г в Л'г . Построим тогда множество Хгь рекурсквно по приведенным выше правилам, начиная с узла Л'г.
На всех дугах Аон для которых Л';ЕХ»ь и Л'гЕХ«ь, выполняется равенство х,';+ х,'; =- Ьср Множество всех таких дуг образует разрез (Хгь Хгь), такой, что Л'г 6Хгь. ° Проанализируем теперь, как расположены узлы Л «и Л'« . В зависимости от того, есть в разрезе (Х,ь, Х,ь) дуга А;; с х)г Ф О или нет, возмолгны два случая. В первом случае по некоторой дуге ~Ап разреза (Хгь, Хгь) поток х19 ~ О. Тогда невозможно, чтобы Л', Е Хгь и Л'1 Е Хгь. Действительно, в этом случае найдется по крайней мере одна цепь из У, в Л'н, которая содержит некоторую дугу Аь~ из (Хгю Хгь) с дуговым потоком х ь)О, где У,бХ,ь и Л'»ЕХгь. ГЛ.
!1. МПОГОПРОДУКТОВЫК! ПОТОНИ Но это пРотивоРечит томУ фактУ, что Ьь! — х11! — хй=Ь11+х)ь— — хь!1=0 (поскольку по услови1о задачи должно быть |хй)(Ьы), Аналогично невозможно, чтобы узлы Л'! и Л'! оба находились в Хзь или оба находились в Хзь. Действительно, тогда должна существовать цепь из Л! в 511, содерх1ащая две дуги из (Хзь, Хзь), одна из которых имеет х11д)0. Следовательно, если для некоторой дуги Ап разреза (Хзь, Хзь) поток х,'; чь О, то Л11 Е Хзь, Л!1 Р Хзь. Во втором случае дчя каждой дуги разреза (Хзь, Хзь) поток хг! — — О, т.
е. по каждой дуге разреза (Хэм Хзь) идет поток х';; = =Ьп. Тогда нет никаких ограничений на расположение узлов Ж! и Л'1.. (Естественно, что оба эти узла должны Пел!ать либо В Хзь~ ЛИбО В Хзь ) ° Лвмиа 11.5. Разрез (Хзп Хз!), где Л'з Е Хзп существует тогда и только тогда, когда нет прямого пути из Л!з в Лз. Доказатвльство этой леммы совершенно аналогично доказательству леммы 11.4, поэтому оно опускается.
° Аналогично вышеизложенному доказывается, что если в разрезе (Хзп Хз!) по некоторой дуге Аы поток х1;~0, то Ж1бХз! и Л! сХг! Из лемм 11.4 и 11.5 вытекает, что следующие два события А и В взаимно исключают друг друга. А. Существует либо разрез (Хзь1 Х11,), такой, что Л'з ЕХ,ы либо разрез (Хзп Хз!), такой, что Лз с Хзп В. Существует двойной путь из Лв в Лэ. Введем следующие обозначения! х)=ш1пхзп где минимум берется по всем ненулевым дуговым потокам х!1; 0 прямого направления на дугах прямого пути; хь1=пппх,'!., где минимум берется по всем ненулевым дуговым потокам хп)0 обратного направления на дугах обратного пути; ь!=ш1п(ь!з+хзп — хзз), где Ап — дуги прямого пути с положительным направлением от Л; к Л"з, Ьь=ппп(Ьп.рх;'; — х,';), где АΠ— дуги обратного пути с положительным направлением от Л! к Лзб хву=-шгп(х), хь)' Ьь! ш1п (Ьь Ь!)' 11.!.
ДВУХПРОДУКТОЗЫК ПОТОКИ 23! Теперь рассмотрим алгоритм, с помощью которого можно определить, допустимы ли потоки ! (1, 1') и / (2, 2') и, если они допустимы, построить их. (Этот же алгоритм может быть использован для построения !пах [/ (1, 1') + у (2, 2')).) Пусть г (1, 1') и г (2, 2') — требуемые значения потоков у (1, 1') и у (2, 2').
Чтобы обеспечить конечность алгоритма, будем предполагать, что г (1, 1'), г (2, 2') и Ь;; — четные числа. (В одно- продуктовой задаче о максимальном потоке предполагается, что Ь;! — целые числа.) В вычислительном отнотпепии зто не является ограничением, потому что рациопальные дуговые пропускные способности можно свести к четным целым числам.
Алгоритм построения двухпродуктовых потоков, называемый методом циклического потока, заключается в следующем ([106)). Ш а г О. Найти у (1, 1'), равный г (1, 1') (если это возможно), исходя из заданных Ь;;. Это обычная задача нахождения однопродуктового потока. Для ее решения можно воспользоваться методом расстаповки пометок Форда и Фалкерсона [65). Если окажется, что шах / (1, 1') ( г (1, 1'), то заданные ограничения па поток являются несовместными.
В противном случае перейти к в!агу 1. (Если требуется найти шах [у (1, 1') + у (2, 2')), то на шаге 0 найти шах ~ (1, 1') = с (1, 1').) Ш а г 1. Найти максимальный поток г (2, 2'), исходя из пропускных способностей Ь[| = Ь,~ — [ х'„[ ~ х1;. Это тоже обычная задача о максимальном потоке (т. е. требуется определить, принадле!кит ли узел Ле к Хг или нет). Если при этом получается / (2, 2') ) г(2, 2'), то алгоритм построения допустимых потоков закопчен. Если же у (2, 2') ( г (2, 2'), перейти к шагу 2. Ш а г 2.
Найти двойной путь иэ Л'е в Лз . Если его не существует, то заданные ограничения на поток явля|отся несовместными. (Если реп|ается задача максимизации потоков, то получен |пах [1(1, 1') + ! (2, 2')).) Если нсе двойной путь существует, то положить вв = ппп (хь!и 0,5Ьы) !). (Если существует несколько прямых и обратных путей, то можно выбрать из них любую пару путей.) Двойной путь можно рассматривать как цикл. Поэтому можно отправить поток 1-го продукта величины Ь от Л'е к ЛГе по обратному пути, а аатем дальше от Л|е к Л!'ттпо прямому пути. Очевидно, что зта операция не изменит величины у (1, 1'), к в каждом узле Л', ') А|!горити и все утверждения этого параграфа остаются справедлизыии, если положить 5 .= 0,55ьр а величины х', х', х! не вводить в расе ы смотрение (си. [15*[) ° — Прим. перев, ГЛ.
11. МНОГОПРОДУКТОВЫЕ ПОТОКИ % будет выполняться условие ~ х,'; = О. Но для некоторых дуг может оказаться, что [х,'; [+ [ х[1 [) Ьм. (Совершенно ясно, что дуговые потоки одного продукта, идущие в разных направлениях, взаимно уничтожатся.) Перейти к шагу 3. Ш а г 3.
Увеличить 1'(2, 2') на 26. Для этого надо направить поток 2-го продукта по прямому и по обратному пути, т. е. Ь единиц потока по кая дому из путей. После этого величина 1 (2, 2') увеличится на 26. Далее мы покажем, что при этом [х,', [+ + [х,'1 [~ (Ь1; на каждой дуге. Перейти к шагу 1.
Шаги 1, 2, 3 повторяются, и в конце концов либо совокупность заданных ограничений окажется недопустимой, либо будет построен поток, удовлетворяющий заданным ограничениям. Рассмотрим сеть, изображенную на рис. 11.2. На рис. 11.3 — 11.6 линии из длинных черточек со стрелками указывают направление потока 1-го продукта, из коротких черточек со стрелками — направление потока 2-го продукта. Сплошные линии изображают дуги, на которых пет дуговых потоков. Возле каэкдой дуги указывается 3 числа: первое число — Ьп, второе — х[1э третье — х,';. Если имеется только одно или два числа, это означает, что остальные числа — нули.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
