Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 30
Текст из файла (страница 30)
Пусть сп — пропускная способность дуги (1, 1) из множества А, и пусть си=си. Предположим также, что множество узлов задается в виде !1=(1, 2, ... ..., тт). При описании алгоритма будут использоваться следующие обозначения: !2е !80 глава в оц — максимальный поток между узлами ( и ); (Х, Х)ц — минимальный разрез, отделяющий ~ от ) (~енХ, /евХ); С(Х, Х)ц — пропускная способность минимального разреза, отделяющего ( от /. Если некоторый узел з рассматривать как источник, а другой узел à — как сток, то, согласно теореме о максимальном потоке и минимальном разрезе, оп=С(Х, Х),ь Если затем в качестве источника и стока выбирается другая пара узлов (( и ( соответственно), удовлетворяющих одному простому условию, то в алгоритме Гомори — Ху при определении величины оц используется решение задачи о максимальном потоке, найденное иа предыдущем шаге.
А именно, как доказано в работе (251, если узлы ~ и ) выбираются таким образом, что оба они принадлежат Х (или Х), то множество узлов Х (или Х, если ~ и 1 принадлежат Х) может быть объединено в один узел. При этом величина максимального потока из ( в ) будет одной и той же для исходной и конденсированной сетей. Пусть Яц — множество узлов, образованное в результате конденсации всех узлов, лежащих по ту сторону разреза, где не содержатся узлы ~ и ). Пусть Ац — множество дуг, соединяющих узлы из Йц. Тогда модифицированная сеть может быть представлена в виде бц=(й)ц, Ац).
Если известны пропускные способности дуг, принадлежащих Ац, то для нахождения величины максимального потока между узлами ~ и / можно воспользоваться процедурой расстановки пометок. Эти пропускные способности мы определим с помощью следующей простой процедуры. Пусть )ь |ь ..., /,— узлы из Х, непосредственно связанные с узлом й=Х.
Если конденсируется множество Х, то дуги ((, 11), ((, !з), ..., ((, 1,) заменяются одной дугой, соединяющей узел ( и конденсированный узел Х. Пропускная способность этой дуги вычисляется следующим образом: У С,.— =~~~~ ~Сц . гв ! Как отмечалось выше, величина максимального потока из 1' в ) может быть вычислена с помощью процедуры расстановки пометок, примененной к сети Оц. Для определения величины оц вновь необходимо найти минимальный разрез, отделяющий ю' от )'. Пусть (Х, Х)ц — соответствующий разрез с минимальной пропускной способностью.
Теперь можно выбрать другую пару узлов, принадлежащую либо Х, либо Х, и построить другую В качестве множества ветвей дерева выбрать пустое множество. Вса Узлы обьединить в одну группу 1= 1 Выбрать произвольную пару узлов в и 1 Определить максимальный поток из а в 1 с помощью процедуры расстановки пометок Найти минимальный разрез, отделяющий а от 1.
Представить дан ныа разрез ветвью и поместить ее в дерево. Вес ветви положить равным пропускной способности минимального разреза. Данная ветвь должна соединять узлы (или группы узлов), расположенные по разные стороны от найденного минимального разреза Аа Нет 1=П -1 У тано Выбрать произвольнуюМару узлов1и Б еще не отделанных друг от друга в строя. щвмся дереве. Положить в 1и1 = 1 Сконденсировать в один узел каждую связную подсеть, соединенную с группой, содержащвйузлы!и1 1 =1+1 Рлс. 2.56. Блок-схема алгоритма Гонора — Ху.
1а2 Глава 2 2.15.2. ОБОСНОВАНИЕ АЛГОРИТМА Пусть б=(Х, А) — неориентированная сеть, и пусть пропускные способности всех дуг из А удовлетворяют условию сн=сн. Пусть 1, 1, Аенй(. Согласно теореме о максимальном потоке и минимальном разрезе, он=С(Х, Х)н. Если АеБХ, то ом С(Х, Х)н, а если Й~Х, то пм(С(Х, Х)п. Следовательно, он) оы и он) пм, откуда следует, что он) ппп [пы, пвД. Если аналогичные рассуждения повторить для оы и ом, то мы получим следующие результаты: ом)ппп [о;„, о,в], ивн) )ш(п[овв, п,1], где (1, р, й, д, Д вЂ” связное множество узлов из е(.
Следовательно, он)тря[и р, орм олв, овг]. В.общем слу- чае пм ъ ппп [ом,, и...,, п...м..., п„1 [ (2.69) где (1, 1ь (м, Д вЂ” связное множество узлов из К. Перед тем как продолжить наши рассуждения, докажем следующее свойство максимального остовного дерева: шмв шп1 [шин шнм %вал" %,1 [, где (1, 1) — произвольная дуга, не принадлежащая данному де- реву, (й (ь (в, ..., Д вЂ” единственная последовательность узлов, соединяющих ветви дерева, шп — вес дуги сети.
Если неравен- ство (2.70) не верно, то вместо любой дуги пути нз 1 в 1 можно взять дугу (1,/), в результате чего будет построено дерево с ббльшим весом. Данное противоречие доказывает справедли- Вость неравенства (2.70). Если веса ген дуг остовного дерева положить равными пн, "я любой дуги (1, 1), не принадлежащей дереву, будет пиво соотношение пм ( ппп [пн,, о...,..., о, (2.71) конденсированную сеть. В результате выполнения процедуры расстановки пометок можно будет определить другой разрез н построить новую конденсированную сеть. Можно показать, что, после того как будет выбрана и — 1 пара узлов, мы определим все п(п — !)/2 величин максимального потока для исходной сети 6.
Блок-схема алгоритма Гомори — Ху изображена на рис. 2.56. Основная идея алгоритма состоит в итеративном построении максимального остовного дерева, ветви которого соответствуют разрезам, а параметры ветвей — величинам разрезов. Ниже дается обоснование алгоритма и приводится иллюстративный. пример. Детерминированные логики в сетлк где (й ть 1ь ..., 1о 1) — связная последовательность узлов дерева, принадлежащих пути из 1 в 1.
Из неравенств (2.69) и (2.71) получаем, что для любой дуги, не принадлежащей дереву, ем ш)п (о„,, о,,еа,..., п„11 (2.72) Максимальное остовное дерево, удовлетворяющее равенству (2.72), называется деревом разрезов потому, что каждая его ветвь соответствует разрезу, а вес ветви равен пропускной способности разреза. Если требуется определить величину максимального потока между двумя произвольными узлами, надо в дереве найти путь, соединяющий эти два узла, и выбрать в этом пути дугу с минимальным весом. Вес этой дуги равен величине максимального потока между рассматриваемыми узлами. 2.15.3. ПРИМЕР ЗАДАЧИ О МНОГОПОЛЮСНОМ МАКСИМАЛЬНОМ ПОТОКЕ Рассмотрим сеть, изображенную на рис.
2.57. Числа, приписанные дугам, соответствуют их пропускным способностям. Требуется для каждой пары узлов сети определить величину Рис. 2.57. Сеть в задаче о миогополюсиом максимальиом потоке максимального потока между ними. Данная задача решается за л — 1=7 — 1=6 итераций алгоритма Гомори — Ху. Если процедура расстановки пометок применялась бы к каждой паре узлов, то потребовалось бы решить 21 задачу о максимальном потоке. Разрезы, построенные на каждой итерации, состоят из дуг, остаточная пропускная способность которых равна нулю.
Для простоты изложения мы опустили результаты, полученные при выполнении процедур расстановки пометок. Итерация 1. Рассмотрим узлы з=2 и 1=5. Величина максимального потока равна 13. Поэтому эта=пес=13. По разрезу с минимальной пропускной способностью мы определяем, что построение дерева разрезов можно начать с ветви, соединяющей 184 Глава 2 узел 5 н конденсированный узел, состоящий нз узлов 1, 2, 3, 4, 6, 7 (рнс. 2.58а). Вес данной ветви равен 13. Итерация 2. Рассмотрим узлы з= 1 н г'=2. Величина максимального потока равна 19. Поэтому ем=от~=19. По минимальному разрезу мы определяем, что узлы 2 н 5 лежат по одну его сторону, а все остальные узлы сети — по другую сторону этого Рис. 2.58а.
Задача о максимальном потоке: первая итерапия. разреза (рнс. 2.586). Вес ветви, соединяющей узел 2 н конденсированный узел, состоящий нз узлов 1, 3, 4, 6 н 7, равен 19. Итерация 3. Рассмотрим узлы 6 н 7. Величина максимального потока равна 21. Поэтому овт=ож=21. По минимальному раз- Рис. 2.585. Вторая итерация. реву мы определяем, что узел 7 в дереве разрезов соединяется с конденсированным узлом, состоящим нз узлов 1, 3, 4, 6, дугой, вес которой равен 21. Кроме того, узлы 2 н 5 н конденснрованный узел (1, 3, 4, 6) расположены по одну сторону минимального разреза, а узел 7 — по другую сторону этого разреза (рнс.
2.58в). Итерация 4. Рассмотрим узлы з=4 н 1=6. Велнчпна максимального потока равна 25. Поэтому оче=ом=25. По минимальному разрезу вкдно, что узлы 6 н 7 расположены в той же части дерева разрезов, что н узел (1, 3, 4) (рнс. 2.58г). 166 Глава л Итерация 5. Рассмотрим узлы з=1 и 1=4. Величина максимального потока равна 24. Поэтому он=он=24. Определяя минимальный разрез, удаляем узел 1 нз узла (1, 3, 4) и располагаем его по ту сторону узла (3, 4), где не находится ни один из оставшихся узлов (рис.
2.58д). Вес соответствующей дуги в дереве разрезов равен 24. Итерация 6. Рассмотрим узлы з=3 и 1=4. Величина максимального потока равна 22. Поэтому ов4=о4в — — 22. Найдя минимальный разрез, удаляем узел 3 из узла (3, 4) и соединяем его с узлом 4 дугой дерева разрезов, вес которой равен 22. Теперь дерево разрезов стало полным, т. е. состоит из шести дуг. Поэтому процедура заканчивается (рис. 2.58е). Величины максимальных потоков можно записать в виде следующей матрицы: — 19 22 24 13 24 21 19 — 19 19 13 19 19 22 19 — 22 13 22 21 24 19 22 — 13 25 21 13 13 13 13 — 13 13 24 19 22 25 13 — 21 21 19 21 21 13 21— 2.16.
ЗАДАЧА О МНОГОПОЛЮСНОИ ЦЕПИ С МАКСНМАЛЬНОИ ПРОПУСКНОИ СПОСОБНОСТЬЮ С задачей о многополюсном максимальном потоке, рассмотренной в равд. 2.15, тесно связана задача о многополюсной цепи с максимальной пропускной способностью. Алгоритм, описанный в равд. 2.15, позволяет находить максимальный поток между каждой парой узлов.
Очевидно, максимальному потоку между каждой парой узлов могло соответствовать множество путей или цепей из источника в сток. В действительности в задаче о максимальном потоке рассматриваются лишь те пути или цепи, с помощью которых можно увеличить поток из одной точки в другую. Рассмотрим простую сеть, изображенную на рис. 2.59. (Числа, приписанные дугам, соответствуют верхним границам потоков по ним.) Величина максимального потока между узлами А и 13 равна 40, а соответствующие потоки по дугам следующие )лв=20, 1ллс=20, 1лсв=5, 1вв=25, ~аз=15. Узлы А и 13 соединены тремя цепями, как показано ниже. Рассмотрим следующую задачу, относящуюся к приведенной выше сети: какая цепь, ведущая из узла А в узел О, имеет !87 Детерминированные потоки в сетях максимальную пропускную способность? Очевидно, цепь с максимальной пропускной способностью определяется последова- тельностью Узлов ~ ч1 -, а величина максималь- /еа = 20 ного потока по этой цепи равна Ею»к=20.
Задача, которую мы хотим рассмотреть в данном разделе,— это задача о многополюсной цепи с максимальной пропускной способностью, т. е. задача о цепи с максимальным Ле= 20 потоком между всеми парами узлов. Ху [311 была разработана Усе= 5 эффективная вычислительная ,7»о = 25 процедура, которая представляет собой модификацию трехместной операции, используемой при решении задачи о многополюсной кратчайшей це- 20 и 25 пи (пути).
Данный алгоритм работает следующим образом. л 5 и Шаг 1. Построить матрицу пропускных способностей раз- 25 15 мерам пК,п, элементы которой соответствуют пропускным способностям дуг между узлами !Рис. 2,59, Сеть и задаче о цепи с и) (01'=1,2, ..., и). максимальной пропускной способШаг 2. а. Для каждого 1=1, пастью. 2, ..., п выполнить следующую процедуру: исключить )чю строку и 1-й столбец матрицы и над каждым оставшимся элементом А» (диагональные элементы также исключаются) выполнить трехместную операцию А» —— шах(А»; ш(п(Аь Н,»1) для всех (,й~), 1=1, 2, ..., и. Вторая матрица, называемая матрицей маршрутов, необходима для определения внутренних узлов каждой цепи. Матрица маршрутов также имеет размеры п,'и,'п, а й-й элемент (-й строки в ней первоначально равен й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
