Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 39
Текст из файла (страница 39)
Рассмотрим один специальный класс многопродуктовых задач— задачи о двухпродуктовом потоке в нееригнтироганней сети. Для них справедлива теорема, аналогичная теореме о максимальном потоке и минимальном разрезе. Кроме того, они обладают свойством, аналогичным свойству абсолютной унимодулярности. (В ((731 показано, что результаты этого параграфа выполняются и в случае псевдосимметричной сети т).) Поскольку и доказательство теоремы, и описание алгоритма достаточно громоздко, мы сначала обсудим интуитивную идею, лежащую в их основе.
') Псевдоскмметрвчнсй называют сеть, для каждого уела Фу которой ~~~~ Ь~у четка (см. И73)).— Прим. перев. 1 мл. двтхпгодгктовыв потоки 225 Пусть имеются потоки двух продуктов в сети. Будем максимизировать поток первого продукта, как это делается в обычной одиопродуктовой задаче. После того, как в процессе максимизации получится требуемая величина г (1, 1') потока 1-го продукта, будем увеличивать поток 2-го продукта от нуля до требуемой величины г (2, 2'), стараясь сохранять неизменной величияу потока 1-го продукта. Это делается путем создания в сети цикла для потока 1-го продукта.
Добавление такого цикла либо увеличит дуговые потоки 1-го продукта, либо уменыпит их, в зависимости от направления дуговых потоков, уже имеющихся в сети. Алгоритм, представленный ниже, находит такой цикл для потока 1-го продукта, что при добавлении этого цикла в сети найдутся пути, увеличивающие поток 2-го продукта. Обычно разрез обозначался символом (Х, Х), а пропускная способность разреза — символом с (Х, Х). По причинам, которые станут ясными в дальнейшем, будем теперь использовать символ (г, 1) для обозначения минимального разреза, разделяющего Л, и Л'о и символ с (г, ») — для обозначения пропускнойспособности минимального разреза.
Разрез (г, г) разделяет одну пару узлов. Теперь определим соответствующие понятия, когда разделяется много пар узлов. Приведенным множеством, разделяющим т пар узлов, называется мнол«ество дуг, удаление которых отделяет увел Л'; от уала Л'о (1 = 1, 2, ..., т) и при этом никакое его собственное подмноя<ество не обладает этим свойством. (Заметим, что узел Л'; может оказаться в той же самой компоненте связности, что и Л';, если 1 час.) Дальше в этом параграфе приведенное множество, разделяющее пары вершин, будем называть также «разделяющим мно»кеством». Пропускной способностью рагделлющего множества называется сумма пропускных способностей дуг, входящих в него.
Разделяющее множество, пропускная способность которого минимальна, называется минимальным множеством. Минимальное разделяющее мно.кество, отделяющее узлы Л'~ от узлов Хг (1 = 1, 2,... й), будем обозначать (1, 2,..., /с; 1', 2',..., й'), а пропускную способность минимального разделяющего множества — символом с(1,2,..., к;1',2', ..., й'), Лвммл 11.1. Удаление приведенного множества, рагделлющего к пар углов, рагбивает сеть не более чем на к + 1 компонент свягности. Доклэьтвльство.
Калдая дуга связывает два узла. Поэтому если удалять одну эа другой дуги приведеппого разделяющего множества, то число компопент связности каждый раз либо не меняется„либо увеличивается на единицу. Каждый раз, когда 15 т. хт гл. 11. мпогопРОдуктОВыя потокп 226 число компонент связности увеличивается на единицу, по крайней мере одна новая пара узлов оказывается разделенной. (В противном случае мноя1ество удаляемых дуг не было бы приведенным.) Поэтому, когда число компонент связности станет равным Й + 1, все пары узлов заведомо дол1кпы оказаться разделенными. ° Обозначим через $ — 1 новый узел, полученный.
в результате склеивания узлов ДГ1 и ДГ1 в один узел (т. е. О» делаем произвольно болыпой величиной). Справедлива Лгмттх 11 2. с (1, 2; 1',2 ) = п11п [с (1 — 2; 1' — 2 ), с (1 — 2'; 1' — 2Ц. Доклзхтвльство. Согласно лемме 11.1, удаление минимального разделяющего множества (1, 2; 1', 2') разобьет сеть не Гб1 <а> Р в с. 11Л. более чем на 3 компоненты связности. На рис. 11.1 зти компоненты изобра1ке~ы в виде прямоугольников, а линии между прямоугольниками обозначают мпоя1ество дуг, связыва1ощих эти компоненты.
Если сеть имеет вид, представленный на рис. 11.1 (а), то с(1, 2; 1', 2') = с(1 — 2; 1' — 2'). Если 1ке сеть имеет вид, представленный на рис. 11 1 (б), то с (1, 2; 1', 2') = с (1 — 2'; 1' — 2). Остальные случаи располо1кения узлов 1, 1', 2, 2' в компонентах связности рассматриваются аналогично. Следовательно, с (1, 2; 1', 2') — — ппп (с (1 — 2, 1' — 2'), с (1 — 2'„1' — 2)). ° Лемма 11.2 позволяет найти с (1, 2; 1', 2') посредством решения двух обычных задач о максимальном потоке. Согласно ей для нахождения минимального множества, разделяющего две пары узлов, достаточно рассмотреть только два разбиения мно- 11Л. ДВУХПРОДУКТОВЫЕ ПОТОКИ жества узлов, указанные в лемме 11.2.
Именно зто свойство упрощает задачу о двухпродуктовом потоке в неориентированпой сети. В общем случае нс известен простой способ нахождения минимального мпоясества, разделяющего т (т ) 2) пар узлов. Рассмотрим еще одно свойство разделяющих мпоисеств.
Лепил 11.3. с (1,..., 1; 1,..., 1 ) + с (1 + 1, ° 1+ к' 1' -',— 1',..., 1' + 11') ) с (1,..., 1 + 1с; 1',..., 1' + 1с'). Доклзлтельство. Два разделяющих множества, стоящих в левой части неравенства, вместе образуют множество, разделяющее 1 + к пар узлов. Сумма их пропускных способностей не может быть меньше выражения, стоящего в правой части неравенства, так как зто выражение есть пропускная способность минимального разделяющего множества. В частности, с (1, 1') + с (2, 2') ) ) с(1, 2; 1', 2') ° Сформулируем основную теорему о двухпродуктовых потоках. Теоремл 11.1 (тсорема о максимальном двухпродуктовом потоке и минимальном разрезе [106)).
Два потока 1 (1, 1') и 1 (2,2') являются допустимыми тогда и только тогда, когда выполнены одновременно условия 1 (1, 1') ( с (1, 1'), (1) (2) 1 (2, 2') ( с (2, 2'), 1 (1, 1') + 1 (2, 2') ( с (1, 2; 1', 2'). (3) Максимальная ееличи>са суммы этих двух потоков равна минимальной пропуск>сой способности всех приведенных множеств, разделяюисих рассматриваемые пары узлов, т. е. псах [/ (1, 1') + 1 (2, 2') [ = с (1, 2; 1', 2') = =: ш[п [с (1 — 2; 1' — 2'), с (1 — 2', 1' — 2)[.
(4) Доклзлтельство. Необходимость выполнения условий (1) — (4) очевидна. Доказательство достаточности проведем, построив конструктивный алгоритм нахождения допустимых потоков. Для любого множества дуговых потоков в сети определим рекурсивно следующие множества узлов: 1. Л'16 Х,. Если ЛсрХ> и х[>-! [х[1[(Ъ>сн то Л>ЕХ1. 2. Лг~ Х,. Если Л>> ЯХг и [х[;[ [-х[>(Ъ>1, то Л>,ЕХг.
15ь ГЛ. 11. МНОГОПРОДУКТОВЫВ ПОТОКИ 3 Л'гбХге Если Л'1ЕХге и хм Р4)(Ь1п то Л'~ЕХге'). 4. Лг~Хвь Если Л11с Хв) и хм+хм(ЬКП то Л';с Хг) ). Дуговые потоки одного и того же продукта, протекающие по некоторой дуге в противоположных направлениях, можно анну- лировать, что пе изменит величины этого потока.
Поэтому моекно вычислить остаточную пропускную способность дуги Аеч для потока 1-го продукта следующим образом. Пусть х,', О, т. е. по дуге Ам идет поток 1-го продукта в направлении от Л1 к Жп Если мы еще хотим послать поток 1-го продукта из Л11 в Л'и то остаточная пропускная способность дуги А О равна Ь,"; = Ь;;— — (х11)) — х,';. Если мы хотим послать поток 1-го продукта иа Л'т в Л11, то остаточная пропускная способность дуги АО равна Ь11 — Ь13 — ) х~1 )-(-х)~. Аналогично для потока 2-го продукта мы имеем ЬП=Ь1,— в ) х)1! — х,'; или Ь;; = Ьы — ) х,'1)+4; (в эависилюсти от того, в каком направлении мы хотим пропускать этот поток).
Если Л'1 ~Х1, то существует цень из Л'1 в Л'1О в которой каждая дуга обладает положительной остаточной пропускной способностью: Ьн =- Ьм — ) хп ) -+- х,'; ) О. Следовательно, можно дополнительно пропустить по втой цепи поток 1-го продукта, величины щ1ПЬ; (минимум берется по всем дугам этой цепи).
Аналогично, если Лгз РХг, можно пропустить по некоторой цепи поток 2-го продукта, величины ппп Ь;и где Ьч = Ь;,— — ) х';1 ) ~ хеч ) О. Таким образом, чтобы величина ~(1, 1') + г (2, 2') была мак- симальна, необходимо (но не достаточно), чтобы Л)1 ~ Х, и Л", Е к Хе. Рассмотрим некоторую цепь иэ Л', в Л'е. Для всех дуг этой цепи установим положительное направление следующим образом. Если после удаления дуги А и из цепи узел Л'1 будет связан с уз- лом Л, посредством дуг этой цепи и узел Л; будет связан с узлом Л'в посредством дуг этой цепи, то положительным направлением дуги А1г считается направление от Л'1 к Л1п Заметим, что поло- жительное направление дуги устанавливается относительно неко- тоРой Цепи из Л', в Ле. БУДем говоРить, что ДУговой поток х1г имеет прямое направление, если он идет от 11'1 к ЛГП и обратное, если он идет от Л; к Л1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
