Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 28
Текст из файла (страница 28)
8.13, принимая числа, указанные рядом с дугами, за их длины. 3. 1(рн доказательстве теоремы о максимальном потоке и минимальном разрезс множество Х определялось следующими правилами: Л>,сХ, если Л'>~Х и х»(Ь», то Л>>ЕХ, если Л>>ЕХ и х>>)О, то Л>>сХ. Дать аналогичное рекуррентное определение минимального разреза (У, У), используя некоторый максимальный поток нз Л>е в Л>> и начиная с правила Л'> с У.
') Дойствнтсльно, в атон случае строки а>атрнцм А линейно эаввспни.— При.в, рад. 163 дополнение 4. Задана сеть, содержащая ориентированные и пеориентированные дуги; величина максимального потока из Х, в ?у, равна и. Изменится ли величина максимального потока, если заменить Р з с. 838. каждую пеориепткрованиую дугу пропускной способности Ь парой ориентированных дуг с противоположными направлениями (причем каждая из пих имеет ту же пропускную способность Ь)? Почему? 5. Задана сеть, в которой величина максимального потока из?т', в?у~ равна и.
Какова будет величина максимального потока, если в сеть добавить пеориентированпую дугу пропускной способности Ь? Что изменится, если дугу с пропускной способностью Ь, наоборот, удалить из исходной соти? Дополнение 1. При получении максимального потока с помощью метода расстановки пометок все помотки стираются после нахождения некоторого пути, увеличивающего поток.
В модификации етого метода, предложенной Скоипсом 11771 и Д;коисоном!1191, каждый узел получает 3 пометки. После нахождения некоторого пути, увочкчнвающего поток, стирается только одна ветвь некоторого дерева, содержащего найденный путь, увеличивающий поток. В работе Джонсона проводится также обсуждение свойств базисных решений в сетевых терминах. 2.
В работах Миптя [151 — 154! подробно обсуждаются результаты, связанные с использованием потоковых задач в электрических цепях. 3. Всякая сеть может быть описана матрицей инциденций узлов по отношению к дугам. Таким образом, можно определить, что такое разрез для матрицы ннциденций узлы — дуги. Рассмотрим теперь произвольную матрицу дойствительпых чисел. Монзпо ли для пее определить, что такое разрез? Обобщение сетевых понятий на более абстрактные и общие системы проведено в работах Фалкерсона 1991, Эдмондса и Фалкерсона [571.
глдвд 9 МНОГОПОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОКИ 9Л. Постановки задач В предыдущей главе рассматривалась задача о максимальном потоке между двумя заданными узлами сети. Все осталы»ые узлы являлись промежуточными; в ких выполнялось условие сохранения потока (в электротехнических терминах эти узлы можно рассматривать как промежуточные подстанции в линии электропередачи).
В яастоящей главе мы будем искать максимальные потоки между всеми парами узлов сети, т. е. каждая пара узлов может рассматриваться как источник и сток, а все остальные узлы — как проме»куточпые. Будем изучать только иеориентированные сети, т. е. такие, в которых Ьы = Ь»; для всех С». Именно для таких сотой пайдопы простые и красивые решения. (В работе !95) условие Ьы = Ьп замоиено более слабым.) Будут проанализированы следующие вопросы. 1.
Условие реализуемости. Обозначим через»»» величину максимального потока между узлами»з'» и»у» (С» =- 1, 2,..., и; 1 ~»). Какая связь существует между этими величинами»»,? Каковы з(а — 1) необходимые и достаточные условия того, что множество чисел является мнонзоством величин максимальных потоков»,» между всеми парами узлов в нокоторой сети? 2. Анализ сети. Задана сеть с ограниченными пропускными способностями дуг. Каковы величины»;» максимальных потоков ме»кду всеми парами узлов в заданной сети? Гстественпо, чтобы ответить па этот вопрос, достаточно решить задачу о потоке для всех пар узлов, по, оказывается, моэкно обойтись более простыми средствами.
3. Синтез сети. Построить сеть, в которой величины максимальных потоков»;» между всеми парами узлов удовлетворяют заданным ограничениям снизу и в которой общая пропускная способность всех дуг максимальна. 9.2 услОВие Ркллизуемости 165 9.2. Условие реализуемости (Гомори н Ху )89)) В заданной ноориентированной сети с пропускными способностями дуг Ь11 = — 611 величины максимальных потоков 111, очевидно, являются симметричными, т. е. 111 — — - ~;1. (Для удобства положим 111 =- со для всех Ц Справедлива следующая тоорема: Теовема 9.1 (теорема о реализуемости). Для тоги чтобы множес во неотри1)отельных чисел 1ц = 111 (1, 1 =- 1, 2,..., и) являлось множеством величин максимальных потоков в некоторой сети, необходимо и достаточно, чтобы ~12)ш1п(/1п 112) (для любых 1, 1, 12).
(1) ДОкл алтея ьстВО. Необходимость. В качестве источника возьмем узел )У1, а в качество стока — Узел 11'ю ТогДа по теоРеме о максимальном потоке и минимальном разрезе (2) у1к=с(Х, Х), где Д11с Х, 11'ьсХ. Узол 11'1 принадлежит либо Х, либо Х. Если 1чвс Х, то (Х, Х) будет разрезом, разделя1ощим 12'1 и Мю н, следовательно, 1ы(с(х, х) =(1„. (3) Если же )У~ С Х, то (Х, Х) будет разрезом, разделяющим 11'1 и 11'1, поэтому 112 -с(Х Х)=-112 (4) Итак, должно выполняться хотя бы одно из условий (3) — (4), н, следовательно, 112 ) ш1п (~1ы 112).
Необходимость доказана. Нреждо чем доказывать достаточность, сделаем несколько замечаний. Из соотношения (1) по индукции следует, что (5) Авв11Н (11Ь ЙЗ ° ° ~ 1в-1, а) где 1111, О12,..., 11'„— любой набор узлов рассматриваемой сети. Возьмем любые трн узла в сети н рассмотрим величины максимальных потоков 21;, (тю 112 мел'ду ними. (Напомним, что ~1; =.
=- 1;1.) Оказывается, что среди этих трех чисел по крайней мере два должны быть равны. Действительно, если бы все три числа были разлнчнь1, то, поместив меньшее нз них в левую часть перавенства И), мы получили бы противоречие. Более того, если одно 166 ГЛ. 9. МПОГОПОЛЮСНЫЕ МЛКСНМЛЛЬНЫЕ ПОТОКИ иа этих трех чисел не равно двум другим, то оно должно быть больп(п — 1) ше, иначе снова получим противоречие с (1). Если начертить неориептированных дуг между всеми уаламн сети, длины которых пропорциональны величинам максимальных потоков то каждый треугольник будет иметь по две равные стороны, а третья сторона будет больше или равна другим. Таким образом, неравенство (1) является своего рода «неравенство»1 треугольника», которое налагает па величины /1; максимальных потоков сильные ограничения.
п(п — 1) Из соотношения (5) следует, что среди величин (» — — 1'11 (в сети с п узлами) существует не более п — 1 различных. Докажем п(п — 1) это следующим образом. Рассмотрим полный граф с, дуга- 2 ми, длины которых пропорциональны соответствующим величинам максимальных потоков.
Выберем среди этих дуг те, которые образуют максимальное связываз>щее дерево. Оказывается, что каждая из величин ~11 должна быть равна длине одной из и — 1 дуг этого дерева. Предположим, что )1„— одна из величин (1н которая не равна ни одной из длин дуг дерева. Существует едннСтВЕННЫй ПУТЬ ИЗ У1 В Дг„, СОСтОЯЩИй ИЗ ДУГ РаССМатРИВаЕМОГО максимального связывающего дерева. Из (5) следует, что величина 11п должна быть больше или равна минимальной из длин (1) дуг, входящих в этот путь. Если бы величина )'1„была строго больше, то мы могли бы заменить минимальную из дуг, входящих в путь, дугой длины 11„. При этом получилось бы другое связывающее дерево с общим несом, большим, чем у максимального связывагощего дерева, что невозможно. Достаточность. Построим сеть, в которой заданный набор чисел и;;, удовлетворягощнх условию (1), будет множеством величин максимальных потоков между всеми парами узлов этой сети.
Для этого числа пм, )» 1, удовлетворяющие условию (1), будем считать длинами дуг некоторого полного графа. Найдем в этом графе максимальное связывающее дерево. Затем рассмотрим сеть, имеющую ту же структуру, что и построепноо дерево, у которой пропускные способности дуг Ьы равны заданным числам пы. Покангем, что в втой сети поток мен«ду Х1 и У;, такой, что )1) =— = — ивн будет максимальным. Действительно, для любой пары узлов этой сети выполняется соотношение )11= ш(п(Ь;1, Ьм, ..., Ь«1) = 1пш(пп, л1ю ° ° ° лв!) где Ьн, Ь1ю..., Ь«1 — пропускные способности дуг, образу1ощих в дерево единственный путь из У1 в Х;.
Но, как было замечено выше, для чисел иы, удовлетворяющих условию'(1) (а следо- 9.3. лнллнз сети 167 ватсльно, н условию (5)), справедливо пи= щ1п(пн, пн, ..., и ). Таким обРазом, ~1з = псь ° Зал1етим, что при доказательство достаточности мы показали, что если некотороо мпозкество чисел является множеством величин максимальных потоков (илн, как говорят, реализуемо в качестве множества максимальных позпокое, то оно реализуемо деревом. 9.3. Анализ сети (Гомори и Ху )891) Обратимся теперь к задаче анализа потоковой соти. Имеотся ноорнонткрозанная сеть с ограинченнымн пропускными способностями дуг 51р Требуется найти величины максимальных потоков Р и с. 9.1. между р узлами соти, где 2 ( р ( и, Покажем, что для этого р(р — И но нужно, раз вычнслнть максимальный поток между на>идой парой узлов, а достаточно решить лишь р — 1 задач о максимальном потоке, причем каждый раз задача решается в более простой сети, чем исходнан.
Рассмотрим сначала процесс, называемый сжатием нескольких узлов в один узел. Основная идея состоит в том, что несколько узлов сети приннма1отся за один (ркс. 9.1). Другими словами, мОжнО считать что дуги между всечи юсжиыаемыми» узлами получают бескопеч11ую пропускную способность. При этом дуги, связывающие некоторый узел У1 (не нрннадлежащии'к числу сжимаоыых) со псами сжимаемыми узлами, заменяются одной дугой с пропускной способностью, равной сумме пропускных способностей заменяемых связывающих дуг. ГЛ.
В. МНОГОНОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОКИ ??аирииер, если сжать узлы гв'в, )в'в и Жв в один узел (рис. 9.1), то получится сеть, изображенная иа рис. 9.2. В соти на рис. 9.1 величина максимального потока ~вз — — с (У, У) =- 4. Здесь У = = (2), У =- (1, 3, 4, 5, 6, 7, 8), минимальный разрез (У, У) состоит из дуг Лм, Авв, Лг,. Увеличение пропускных способностей дуг, не принадлежащих атому минимальному разрезу (У, У), не повлияет на величину с (У, У) и может лищь увеличить пропускную способность других разрезов, разделяющих )в'в и Х~.
Таким образом, при свкатин узлов гтв, Ув Ув разроз (У, У) Р и с. 9.2. останется минимальным разрезом, раздоляющим )ув и )ун Следовательно, при вычислении максимального потока /в, можно, например, сжать узлы гв'в, Лгв, )вв в один и производить вычисления в сети, изображенной на рис. 9.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
