Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 30
Текст из файла (страница 30)
Величина максимального потока между любыми двумя полюсами 7у г и Л'7 исходной сети У равна 9.3. Апвлпз свти 17$ ппп (о;„, о„ь,..., ов ), где щ„о„ь,..., цц — пропускные способности дуг, образующих единственный путь из Л~; в Л т в построенном дереве Т. Доклзлтвльство. Заметим, что все дуги, связывающие вершины дорева Т, изображают минимальные разрезы, отделяющие некоторые пары полюсов сети Л, Покажем, что прану- к Х скная способность, приписан- Е ная каждой из дуг, равна величине максимального потока в Л' между двумя полюсами, нахо- Об дящимися в соседних вершинах дерева. Рассмотрим дугу, связывающуго две вершины дерева, одна из которых содержит некоторый полгос Л'„а другая — некоторый полюс Хь.
Обозначим ® через Х множество узлов, на- Гту \ ходящихся в той же части дерена, что и узел Л' „через Х вЂ” мно- Р н с. 9.9. жество узлов, находящихся в той же части дерева, что и )Уь (рис. 9.9). Рассматриваемой дуге приписана пропускная способность с (Х, Х), которая как будет показано ниже, равна величине макснмалыюго потока 1,ь между узлами Л', и Хь в исходной сети Л'. Пусть (Х, Х) является минимальным разрезом, разделяющим некоторые узлы Х; ЕХ и Ут~Х. Величина максимального потока 1,ь равна величине некоторого минимального разреза в исходной сети.
По лемме 9.3 существует минимальный разрез (7, У), разделяющий узлы )у, и )уь и не пересеканнцийся с разрезом (Х, Х). Положим для определенности, что Л'„Е 7, Хь Е 7. Пусть 7 ~ с:Х, 7 ~ Х, как изображено на рис. 9.9. (Случай, когда 7 ~ Х, У:э Х анализируется аналогично.) Существует две возможности: 1) )У; ~г, 2) Х;ЕХ Д /. Покажем, что в обоих случаях с(7, Т) ) .- с(Х, Х). 1) Пусть У;~7. Этот узел обозначен на рис. 9.9 символом 1н заключепнгвм в крунгок. Тогда разрез (Хо /) разделяет Л'с и )У|, с(7, 7)~Д;=с(Х, Х) (иначе (Х, Х) но был бы минимальным разрезом, разделяющим ~'; и Л';). 2) Пусть )У~ ~Х П /. Это узел обозначен на рис. 9.9 симво- лом !з, заключенным в кружок.
По лемме 9.1 и теореме 8.2 гл. е. многополюснык ылнснллггьнык потоки сущостпует минимальный разрез (У, У), разделяющий узлы Лгг и Л', и не пересекагощийся с (Х, Х) и с (/, /)'). Пусть для определенности Л'; с У, Лг„с У. Тогда узлы гуг, и Л'т принадлежат У. (Если один иа узлов Лг„Лге принадлежит У, а другой — У, то разрезы (У, У) и (Х, Х) пересекаются; оба узла Л',, Лге принадлежать У не могут, поскольку Ли и Хь— соседние пеРнгины деРева, пРичем Лгг лежит в той же части дереза, что и гт'„а разрез (У, Т) отделяет Лгг и Лю) Так как (У, У) — минимальный разрез, разделяющий Л'; и Лю то 1г„=-с(У, У).
Далее, поскольку (У, У) — разрез, разделпющий с(У, У))1гг=с(Х, Х). (15) Так как (7, /5) — разрез, разделяющий Лг, и Лг» то из (15) следует с(/, Х)))ы-.-с(У, У)) с(Х, Х). (Пг) Таким образом, и п случае 1, и п случае 2 с(/, /5))с(Х, Х). (17) Заметим, что (Х, Х) — разрез, разделягощий Лг, и Лгю позтому с(Х, Х))),е =--с(/, /5). (18) Из (17) и (18) следует, что с(/, Я) = с(Х, Х) — (,г,. Поэтому соотношение (5) нз $ 9.2 длп величины максимального потока и сети между дпумя несоседними полюсами дсрепа примет пид )гг)ппп()г„)„ю ...,(кг)=пнп(п;„п„ь, ...,гз;), (19) где Л;„А„е, ..., Агг — последовательность дуг, спязывагощая узлы Лгг и Лг; п дереве. С другой стороны, пропускная способность каждой дуги и пра- вой части (19) является (по построению дерева) пропускной сно- собностькг РазРеза, отдслЯгощего Лгг от Лг; п исходной сети Лг, и, следовательно, )гг(пг(п(пг„, ц,е, ..., гзг).
(20) Из (19) и (20) следует утверждение теоремы. ° г) Пусть (У» У) — некоторый икпнмадьпый разрез, ке перееекающийса е (Х, Х), а 1уз, У ) — икнпиагнный разрез, пе пересекающийся с (Х, Х). Тогда (У, У) —. (У, () Уз, Уг () Уз) — ипннзгзлыгый разрез, пе пересекающпйся с (Х, Х) и с (Х, У). 9.3. АнАлиз сети 177 Рассмотрим численный пример, иллюстрирующий анализ сети. Пусть в сети на рис. 9.10 числа рядом с дугами являются нх пропускными способностями. Будем искать максимальные потоки между узлами Х„Х„79, н Хм Сначала выбираем два произвольных узла, скан<ем М, и У„ и находим максимальный поток между ними.
Получаем мини- Р в с. 931. Р вс 9,10а мальный разрез (М„Уз, Ус (М„йгс,'Ус) величины 13. Символически это изображено па рис. 9.11. Затем находим максимальный поток между Дгз и загс в сети, изображенной на рис. 9Л2. Зта сеть получена с помощью сжатия узлов У„Мм дгс (рис. 9ЛО) в один узел. В результате получаем Р я с. 933. Р и с. 9Л2. минимальный разрез (Лм Фэ, Фс, 7У„ДГз ! Фс) величины 14, изображенный па рис. 9.13. Заметим, что вершина (3, 5) соединена с вершиной (1, 2, 6), потому что они лежат по одну сторону в минимальном разрезе, разделяющем Хэ и Х,. Затем находим максимальный поток между У, и Уз в сети, изобраягонной на рис.
9Л2. В результате получаем минимальный разрез (М„йгм Ус, йг„Х, ( 79,) величины 15, изображенный символически на рис. 9.14. 12 т. хт 178 Гл. с. многополюсные МАксимАлы1ые потоки Теперь каждая вершина в полученном дереве содержит только по одному полюсу. Таким образом, найдены следующие величины максимальпых потоков в сети (рис. 9.14): ~1з = ~11 = ~11 = 13, 1ы=1ы = 14, ~зс = 15.
Они равны соответствующим величинам максимальных потоков в исходной сети (рис. 9.10). Р я с. 9Л5. Р в с. 9.14. Если бы потребовалось найти величины максимальных потоков между всеми парами узлов, тогда надо было бы просто продолжить описанный процесс: выбрать, например, узлы Х1 и 7тс, и найти максимальный поток между ними в сети, изображенной Р ко. 9Л7.
Р в с. 9.16. на рис. 9Л5. В результате получили бы минимальный разрез (Ф1, Хз ( 79с, Уз, Ую Л'с) величины 17, изображенный на рнс. 9.16„ После зтого надо выбрать узлы 71'1 и 11'з и найти максимальный поток между ними в сети, представленной на рнс. 9.17. В резуль- тате получим минимальный разрез (Л'1 ! Ха )тв Л'с 1тю 7тс) величины 18, изображенный на рнс. 9Л8. С помощью дерева, изображенного на рнс. 9.18, мо1кно легко найти величины максимальных потоков ме1кду всеми парами узлов (опи выписаны в табл.
9.1). Сети, представленные на рис. 9.18 и 9ЛО, имеют одинаковые величины 717 максимальных потоков между всеми парами узлов. Такие сети, как уже говорилось раньше, называются потоко-эквивалентными друг другу. Если в 2-х сетях равны величины макси- э.з, Анллиз сети 179 мальных потоков между парами полюсов, принадлежащих некоторому заданному множеству, то ати сети называются потокоэквивалентными по отношению к заданному множеству узлов.
Р и с. 9.18. Например, сети па рис. 9Л4 и 9ЛО являются потоко-эквивалентными по отношению к 17У„Хз, 7У», 1тэ). Описанный выше метод анализа сети позволяет строить потокозквивалентную сеть, которая является деревом. Заметим, что Таблица 9.$ О1 О2 Оз О4 Оз Оа О1 Оз Оз О4 Оз Оз существует много деревьев, которые потоко-эквивалентны некоторой заданной сети. Однако потока-эквивалентное дерево, построенное в этом параграфе, обладает следующей особенностью: каждая ветвь этого дерева соответствует некоторому минимальному разрезу в исходной сети, Поэтому это дерево называется деревом разрезов [89].
Дерево разрезов, содержащее п уалов, изображает и — 1 минимальных разрезов исходной сети, которые не пересекаются друг с другом. На рис. 9.19 этн разрезы изображены пунктирными линиями. 12в ~99 гл. е. многополюснык млксимальнын потоки Рвс. 9Л9, 9.4. Синтеа сети (Гомори и Ху (891) В предыдущем параграфе было показано, как находить величины максимальных потоков в ааданной сети. Теперь будет ивуп (о — 1) чаться обратная аадача: если заданы 2 чисел гм, ограничивающих сниву величины ~ы максимальных потоков между узлами, (б> Са) Р в с. 9.20. надо уанать, какой вид будет иметь пеориентировапная сеть, у которой ~ы ' в гы и общая пропускная способность дуг минимальна? Пусть заданы о (о — 1) 2 чисел гм.
Их можно рассматривать как длины дуг полного графа с п узлами. Построим максимальное связывающее дерево етого графа. Величины гм, соответствующие дугам максимального связывающего дерева, будем называть доминирующими требованиями, а построенное дерево — деревом доминирующих требований Т. Например, если ааданы числа гп, представленные на рис. 9.20(а), то дерево доминирующих требовапий Т ивображено на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
