Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 35
Текст из файла (страница 35)
!О. НРА!"!Аншие цвпи и ИОтОки минимАльнОЙ стоимости таа ца ХО,З О! Оз Оз О4 Оз ® От Таблица 10.8 О! Оз Оз О4 Оз ® От О! Оз Оз О4 Ое От Докажем теперь, что выражение (2) определяет именно те узлы, которые входят в кратчайшую цепь. Пусть!!!! — промел<уточный узел в кратчайшей цепи из !!!р в !!!а, имеющий наименьший индекс, а !1'! и Р» — два узла„соседпйо с уалом !1'! в атой кратчайшей цепи. При вычислениях получится: !!!» ) О!! + д!», и мы положим (1, я) = (1, у) = у.
(Напомним, что (1, !') с самого начала вычислений был равен !', и ! — саиыи меньший индекс узла в цепи.) Так как Аы и Ат„являются базисными дугамк, то |ол. двкомпозиционныи ллгор«тм при всех дальнейших вычислениях останется (|, 1) = 1 и (1, Й) = Й. Таким образом, выражение (2) правильно указывает, что в кратчайшей цепи аа узлом Л<< идет узел Ум а за узлом Л|< — узел )т ь. Теперь заменим'исходную кратчайшую цепь иа Ур в |<|о другой, которая имеет ту же длину, что и исходная, но меньшее число узлов, т.
е. введем новую базисную дугу А<э длины й<г + <[,ю Продолл<ая рассуя<дения рекуррентно, получим требуемое утверждение. Рассмотрим еще одну задачу [109[. Пусть имеется сеть с пропускными способностями дуг Ь|Й Назовем пропускной способностью пути из узла |<'р в узел Л|о величину наименьшей из пропускных способностей дуг этого пути. Путь из Фр в Уо будем называть путем с максимальной пропускной способностью, если его пропускная способность не меньше, чем пропускная способность любого другого пути из |<|р в Ф .
Тернарная операция, аналогичная введенной в этом параграфе операции (1), может быть использована для нахождения путей с максимальной пропускной способностью между всеми парами узлов сети. В этом случае тернарная операция имеет следующий вид: Ъ|ь< — — шах [Ь<ь, шш (Ьм, Ь;„)) (3) для всех <, Й ~1, и проводится последовательно для[ = 1, 2, ... ..., и. Вместе с вычислением матрицы Ьы вычисляется справочная матрица размера т Х и, аналогичная справочной матрице, рассмотренной выше.
Элемент (<, Й) атой матрицы полагается сначала равным Й, а затем (<, 1), если Ьц, ( ш[п (Ь<п Ь;ь), ($, Й)= | (|, Й), если Ь<ь> ш1п(Ььо Ьы). 10.3. Декомпозиционный алгоритм (Ху ]111], ]113]) Очень часто сеть не является сильно связной, т. е. состоит из менее чем и (и — 1) дуг. В этом случае соответствующая матрица расстояний имеет много элементов, равных бесконечности. Это обстоятельство испольауется в декомпозиционном алгоритме, рассматриваемом ниже. Введем сначала несколько новых понятий. Рассмотрим некоторое подмножество узлов в сети и обозначим его буквой А. Пусть Х вЂ” некоторое другое подмножество уалов. Назовем множество Х множеством, отрезающим А, если оно обладает следу<ощкм свойством: при удалении из сети множества Х вместе со всеми инцидентными дугами сеть распадается на две несвязные компоненты, одна из которых содержит все узлы мнон<ества А и только эти узлы.
Множество Х, отрезающее А, называется минимальным отрезающим множеством, если никакое 2О4 ГЛ. 1О. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ собственное подмножество Х не обладает указанным свойством. Ясно, что множество всех соседних с А узлов является минимальным множеством, отрезающим А. Сначала рассмотрим декомпозиционный алгоритм в его простейшей форме, а именно покажем, как разложить сеть на две части.
Предположим, что наша сеть 1Т разбита на три множества узлов: У = А () Х О В, где Х вЂ” минимальное мноя1ество, отрезающее А. Обозначим через ~ А ~ мощность множества А. Присвоим узлам из множества А индексы 1„2,..., ~ А 1, а узлам из Х— индексы ! А ! + 1, ~ А ~ + 2, ) А ) + ~ Х !. Тогда соответствующая матрица расстояний будет иметь вид, представленный в таблице 10.4, причем РА„= (111.), где Л1 С А, 1У~ ~ А, .0Ав = ЫП), где Л11 Е А, 11'1 с В и т. д. Ь начале вычислений все элементы Плв и В вА равны бесконечности. Мы ввели обозначение Э з для матрицы расстояний (а11), где Л1 ба и Лбб р. Иногда удобно использовать символ а' з для обозначения одного из элементов матрицы .О„а.
Таблица 10.4 Введем новое понятие — условно кратчайшая Чель. Цепь называется условно кратчайшей, если она является кратчайшей при условии, что все узлы этой цепи принадлежат некоторому заданному подмножеству уазов сети. Кратчайшее расстояние между Ж1 и У~ обозначим с)11 (при этом кратчайшая цепь из 11'1 в Л~ может содержать любые дуги сети). Длину условно кратчайшей цепи из Л11 в У1 обозначим 1111 (у), где у — то подмнон1ество, которому должны принадлежать узлы этой цепи. Матрицу условпо кратчайших расстояний (сй1 (у)), где У1 ~ а, )У~ Б р, обозначим П„"'э(у), а ее элементы — д з(у).
Так как вся сеть обозначена буквой Л, то ат1(Ф)=ат;. Если известно, )что кратчайшая цепь лежит в множестве у, то С1аэ (7) = ааз (11~) ' (1) Введем обозначение А =А ИХ, В=В() Х. Будем считать, что исходная сеть образована из двух сетей, перекрывающих друг друга. Первая из этих сетей, называемая А-сетью, состоит из >0.3. дякомпознцноннь>н л:>Горитм 205 узлов ЛР<, принадлежащих А, и дуг Ам, где Л><, У>ЕА.
Вторая сеть, называемая В-сетью, состоит из уалов №, принадлежащих В, и дуг Аь>, где №, М, ЕВ. Сначала выполним тернарные операции в А-сети. В результате получим условно кратчайшие цепи между всеми парами узлов А-сети. В частности, получатся условно кратчайшие расстояния мея<ду всеми парами уалов из Х. После этого выполним тернарные операции в В-сети, причем в качестве расстояний между узлами из Х возьмем условно кратчайшие расстояния, найденные ранее при вычислениях в А-сети. Затем выполним тернарные операции снова в А-сетн. Алгоритм декомпозиции для двух перекрывающихся сетей основан на следующей теореме.
Тхогвмк 10.1. Пусть У = А()Х()В, причем удаление множества Х делает сеть несвязной. Пусть найдены условно кратчайшие расстояни Вхх (Л). Ч'огда кратчайшие расстояния между любыми двумя узлами В-сети могут быть получены, если тернарные операции выполнять только в В-сети. (Заметим, что А = Л> — В.) До><азлтвльство.
Коли кратчайшая цепь лежит целиком в множестве В, то <Вв (Л>) = «вв (В), т. е. достаточно выполнить тернарные операции только в В-сети. А л а Рассмотрим теперь случай, когда кратчайшая цепь имеет 2 несколько участков, лежащих в множестве А. Символически атот 3 случай изобран<ен на рис. 10.6. Рассмотрим кратчайшую цепь <> нз Л<р в 1Ую сна>коз< из № в №. Так как эта цепь начинается н 5 6 кончается в В, а Х является мноя<еством, отрезающим В, то любой участок рассматриваемой цепи, лежащий в А, должен начинаться Р я с. <0.6.
и кончаться в множестве Х. Р(а рис. 10.6 иаображены два таких участка: из № в № и иа У, в № Коли известны величины <~"' (А) = <1,*> (>»>> — В) и <(,*г (А) = = д,", (>т — В), то можно считать, что именно в В-сети имеется две дуги: Лег длины <1,*,(Ф вЂ” В) и Ам длины Ы,",(>>> — В). Тогда кратчай<пая цепь из Л>< в >>>е состоит из следующих частей: цспн иа № в >Ую дуги Агг, цепи иэ Л>г в №, дуги Аио цепи иэ Л', в Уг, причем все эти части лежат целиком в В-сети »се ГЧ.
!О, НЭАТЧАЙП!ИЕ ПЕПИ И ПотОКИ МИПИМАЛЬНОЙ СТОИИОСТИ Таким образом, при нахождении кратчайшей цепи достаточно рассматривать только В-сеть. Заметим, что проведенные рассуждения не зависят от числа участков цепи, лежащих в А. Ясно, что теорема остается справедливой, если в ее формулировке поменять местами А и В. зз Введем теперь одну специальную операцию над матрицами, которая будет испольаоваться в декомпозиционном алгоритме.
Заметим, что, для того чтобы попасть из некоторого узла Ф! г А в некоторый узел Ф» Е В, необходимо пройти по крайней мере через один узел Рт ~ Х. Если перебрать все цепи, проходящие через каждый из узлов Фт Е Х, и выбрать среди них кратчайшую, то в результате, естественно, будет найдено кратчайшее расстояние Н;». Таким образом, при фиксированных !' и к надо выполнить следующую операцию: де»=шш(с(»!+!(»»), у=1, ..., р, У!ЕА, Л»ЕВ, (2) где р — мощность множества Х. Пусть матрицы расстояний РА»х(У) н Рхв()т') имеют раамеры соответственно и х р и р хи».
Операция (2) напоминает операцию умножения двух матриц, в которой символ «Х» заменен символом «+», а суммирование заменено взятием минимума. Будем называть операцию (2) композицией матриц. Общее число сложений при выполнении всех операций (2) равно и, х и» х р; таково же общее число сравнений. Сформулируем теперь декомпозиционный алгоритм для случая двух перекрывающихся сетей. Ш а г $. Выполнить в сети А все тернарные операции применительно к матрице РАА РАх В результате выполноння этого шага получим матрицы РАА(А), РАх(А), Рй»(А), Рхх(А).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
