Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 32
Текст из файла (страница 32)
Проверить, найдется ли нспомечсппый узел, смежный узлу с пометкой й. Если да, то присвоить этомупепомечсппому узлу пометку 1с + 1. Если пайдстся несколько Непомеченных узлов, смежных узлу й, то какому-то нз пнх присвоить пометку к + 1. Если среди узлов, смежных узлу к, нет непомечепных, ~~р~ (ш1п (гц гьа гор) Иэ (2) и (9) следует ~;р —— ш1п (гы, г;ю ..., гер). Таким образом, все доминирующие требования выполняются как равенства. Перейдем к построению цикла, для которого равпомерпое дерево является деревом разрезов. Для построепия такого цикла нужпо, чтобы любой дуге дерева соответствовал в цикле разрез иэ двух дуг, каждая пропускной способности г/2.
Рассмотрим процедуру расстановки пометок, которая по данному дереву Т строит нужный цикл. зл. сянтвз сити 187 то перейти к узлу я — 1 и проверить, найдется ли непомеченный узел, смежный уалу я — 1. Если да, то пометить его я + 1; если нет, то перейти к узлу я — 2 и проверить, найдется ли непомеченный узел, смежный узлу ес — 2, и т. д. Ш а г 3.
После того как все узлы дерева Т окажутся помеченными, построить следующий цикл: 1, 2,..., и, 1. Этот цикл является искомым. На рис. 9.26 приведены два возмон<пых варианта расстановки пометок в дереве с помощью описанной процедуры. Докажем, что для цикла, полученного в результате расстановки пометок, дерево Т является деревом разрезов. Для этого рассмотрим произвольиуго дугу 1ы дерева. Например, возьмем Р и с. 9.26, дугу, которая на рис. 9.26 (а) обозначена Аьм а иа рис. 9.26 (б)— Азз.
Этой дуге иицидеитяы узлы с пометками л и у; пусть 1 у. Если дугу )ы удалить из дерева, то опо распадется яа две комяоиекты связности В и С, одна из которых будет содержать узел Лгм а другая — й у л). Пусть я — наибольшая из пометок узлов, попавших в ту же компоненту, что и дер Тогда узел с пометкой ') Нам нужно доказать, что в синтезиругощем цикле компоненты В и С соединены ровно двумя дугамв. Длв этого достаточно показать, что если помечен какой-то узел из С, то перейти обратно в В можно ешжь после того, как будут помечены все узлы из С.
Нредполон«им, что узел 1 лежит в В. Из алгорвтл«а видно, что в С мы могли попасть только по дуге 1« .. Значит, узел «у»не был помечен. Следовате»л»зло, нет ни одной дугн дерева, которая вела бы нз С в непомеченный увел пз В. Так как все узлы в С по алгоритму получают плдексы больжие, чем уже помеченные узлы в В, то попасть в В мы можем только «обратным ходом», просматривая все помеченные в С узлы.— Прим. иерее. 188 гл, ю многополюсныв максимальнын потоки й + 1 должен попасть в ту же компоне. ту, что и 7У1.
(Если й = п, то роль й + 1 играет 1.) Так как 7' — наименьшая из пометок узлов, попавших в С, то узел с пометкой 7' — 1 так>не должен попасть в тУ же компонентУ, что и 7Уо СлеДовательно, кажлой дуге )ы дерева соответствуют две дуги цикла, А;,,; и Аю д+м разделяющие в цикле те же множества узлов, что и дуга 117 в дереве.
Упражы ения 1. Найти потоко-эквивалентное дерево для сети, изображен ной на рис. 9.1. 2. Привести алгоритм, превращающий потоко-эквивалентное дерево в потоко-эквивалентный путь. Например, дерево на рис. 9Л8 является потоко-эквивалентным пути на рис. 9.27.
7 13 13 3 14 4 Р и с. 9.27. 3. Решить задачу синтеза сети с минимальной пропускной способностью, если заданы требования, представленные на рис. 9.28: а) найти доминирующую сеть; Р и с. 9.29. Р и с. 9.28. б) найти сеть, в которой доминирующие требования выполняются как равенства. 4.
Будет ли дерево разрезов определяться однозначно, если в сети все величины Ьм различны? 5. Показать, что если сеть ориентированная, то условие ~1ь Ъ ппп Д1н 5~д) является необходимым, но не достаточным для дополнение 189 реализуемости мнолГества чисел ~ы в качестве множества максимальных потоков. 6. Пусть задано дерево требований, представленное на рис. 9.29. Решить задачу синтеза многоползосной сети с минимальной пропускной способностью, чтобы при этом требования точно выполнялись как равенства. Дополнение 1. Предположим, что имеется неориептировапная сеть с и узла. ми и требуется найти максимальные потоки между р узлами неко.
торого заданного подмножества узлов. Алгоритм, предложенный Аккерсом [2), заключается в упрощении сети таким образом, чтобы упрощенная сеть оставалась потоко-эквивалентной исходной Гш Р в с. 9.80. сети по отношению к заданному подмножеству узлов. Пусть АГ;— некоторый узел, пе принадлежащий заданному подмножеству узлов и инцидентный некоторым трем узлам, как показано на рис.
9.30 (а). Тогда узел Х; может быть удален из сети, а сеть примет вид, изобралГенный на рис. 9.30 (б). Если применить этот прием несколько раз, то сеть можно значительно упростить. 2. Пусть заданы требования г» к потоку и стоимость см дуги Аы единичной пропускной способности. Требуется построить сеть минимальной стоимости, удовлетворяющую заданным требованиям к потоку (см.
Гомори и Ху [90]). Нерешенные задачи 1. Пусть пропускные способпости дуг в неориентпрованной сети принимают только значения 0 в 1. Каковы необходимые и достаточные условия, которым должны удовлетворять элементы квадратной матрицы, чтобы они являлись величинами максимальных потоков между всеми парами узлов в некоторой сети? (Заме- 190 ГЛ. 9. МНОГОПОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОНИ тим, что неравенство треугольника в этом случае является необходимым условием, но не достаточным.) 2.
При синтезе сети минимальной пропускной способности в оптимальном решении пропускные способности дуг могут быть полуцелыми числами. Как построить сеть минимальной пропускной способности, чтобы пропускные способности дуг были бы все целыми числамир 3. Задана сеть с ограниченными пропускными способностями дуг. В сети выделено й пар узлов ХО Х,; Лз, Лз, ...,У», Жд . Найти множество дуг, отделяющее узлы У1, Хз, ..., ХА от Хм, Узо ...,ЛГА и обладающее минимальной пропускной способностью с(1, 2, ..., й; 1', 2', ..., й'). 4.
Задана неориентированная сеть с ограниченными пропускными способностями дуг. Найти множество дуг, удаление которых из сети разбивает ее на й компонент, причем это множество должно обладать минимальной пропускной способностью. (Заметим, что при й = 2 и й = и — 1 задача тривиальна.) 5. Пусть пропускные способности дуг не ограничены, а заданы ограниченные пропускные способности узлов.
Рассмотреть для атого случая задачи реализации, анализа и синтеза сети. ГЛАВА 10 КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ стоимости 10.4. Кратчайшие цепи (Дийкстра [49)) В этом параграфе будет рассмотрена одна из основных задач теории сетей — задача нахождения кратчайшей цепи между двумя заданными узлами '). Опа имеет многочисленные практические приложения, а таки е часто используется при решении различных задач оптимизации. Имеется сеть, каждой дуге А;; которой поставлена в соответствие длина, или расстояние дп. Длиной цепи называется сумма длин дп, взятая по всем дугам атой цепи.
Требуется найти цепь минимальной длины из заданного узла Ле в заданный узел Лге. Если узлы сети интерпретировать как города, а величины дм— как стоимости пРоезда из гоРода Л'е в гоРоД Л'и то кРатчайшаЯ цепь представляет собой самый экономный маршрут. Существует много практических задач, в которых ищутся не кратчайшие цепи, а цепи, удовлетворяющие каким-либо другим критериям оптимальности. Но наиболее известна и распространена задача о кратчайшей цепи. В этом параграфе будет предполагаться, что все величины д;; неотрицательны.
Если некоторая пара узлов Л'о Л'1 пе связана дугой, то полагаем ом = оо. Заметим, что величины дп являются произвольными и не обязаны удовлетворять неравенству треугольника Ым + д1л )~ И;ю Если бы это неРавенство выполпЯлось, задача оказалась бы тривиальной, так как тогда кратчайшей цепью из Ле, в Лее была бы всегда дуга А„. Величины дм, кроме того, не обязаны удовлетворять условию симметричности Ип = Ото Будем вместо нахождения кратчайшей цепи из Ле, в Л"„искать кратчайшие цепи из Ле, во все остальные узлы Л'е сети. Это объясняется тем, что л1обой узел Л'; может оказаться нокоторым промежуточным узлом кратчайшей цепи из Ле, в Лее.
Если узел Лг; принадлежит кратчайшей цепи из Л', в Л',, то ее часть из Х, в Лг, должна быть кратчайшей. Действительно, в противном случае указанную часть цепи из Лг, в Л'~ можно было бы заменить па кратчайшую, и при этом получилась бы более короткая цепь из Л; в Х,. По это противоречило бы тому факту, что первоначальная цепь иэ Л, в Л'е является кратчайшей.
Ч В литературе ова известка также под иаавакием задачи о кратчайшем яутв.— Прим. ред. 199 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОИ СТОИМОСТИ Рассмотрим дуги, которые входят в кратчайшие цепи из № во все остальпые узлы 1«'1; эти дуги образуют некоторый граф. Попытаемся удалить из этого графа как можно больше дуг так, чтобы при этом сохранилось по одной цепи из № в кан«дый узел Х1. (Если существует только одна кратчайшая цепь из узла № в узел №, то нельзя уже удалить ни одной дуги.) Если имеется, напри. мер, две кратчайшие цепи из № в 1ч1, то какая-то дуга в одной из этих цепей мо1кет быть удалена (а именно, последняя дуга цепи — Ат или Ап). После удаления всех таких «лишних> дуг останется граф, который будет деревом. Таким образом, если некоторая дуга Ам принадлежит атому дереву, то кратчайшей цепью из 1«'1 в Л'т будет сама зта дуга А Ы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
