Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 34
Текст из файла (страница 34)
Следует отметить, что утверждение (2) является достаточным (но не необходимым) условием применимости описанного выше алгоритма. В заключение параграфа рассмотрим одно интересное и не совсем очевидное приложение задачи о кратчайшей цепи, а именно задачу нахождения минимального разреза в (з, ~)-плоской сети (64), Сеть называется ллоской, если ее можно начертить на плоскости так, чтобы все ее дуги пересекались только в узлах сети, Неориентированная плоская сеть называется (г, 1)-ллоской, если после добавления к ней дуги А,1 она останется плоской. Например, плоская сеть, изображенная на рис.
$0.2, не является (г, 1)- плоской. Эта же сеть, но без дуги А»м уже будет (г, т)-плоской. Рассмотрим (г, 1)-плоскую сеть, которая получится, если из сети на рис. 10.2 удалить дугу А,з. Пусть числа рядом с дугами 1О.ь кглтчАйшик цепи 197 выражают их пропускные способности. Требуется найти минимальный разрез, отделяющий узлы Лг, и Х,. Эта задача, конечно, может быть решена посредством нахождения максимального потока с помощью метода расстановки пометок. Но оказывается, ее можно решить проще: минимальный разрез в исходной сети соответствует кратчайшей цепи в сети, двойственной к ней '). Двойственная сеть строится следующим обрааом. Сначала чертится дуга А,о если в исходной сети атой дуги не было. Получится 1 9'. Р и с.
10.3. плоская сеть с и узлами. Плоскость чертежа окажется разделенной па грани (области, ограниченные ребраьш и не содержащие внутри себя ни вершин, ни ребер). Дуга Ам будет разделять две грани, одна из которых является внешней. Поместим по одному узлу в каждую из этих граней и обозначим их через гьг; и Х[.
Аналогично, поместим по одному узлу в каждую из граней, разделенных дугой Ап, и обозначим их через Ф; и Дг;.. Проведем в двойственной сети дуги А[я которые связывают узлы Х[ и Лг;ь ') Задача яахождоиия максимального потока в [г, 1)-плоской сети проще, чем в общем случае, и аффсктивво решается (за О (в') действий) без испольаоваиия двойствевкой сети [см. [64[, стр. 399).
Алгоритм поиска кратчайшей цепи в двойственной сети будет ие сложнее [по чисау действий) алгоритма кахояздевия максимальпого потока в исходиой сети, если число узлов в двойственной сети ие превышает (по порядку) числа узлов в исходпой цепи. Зто действительно так: число узлов в двойственной сети равно числу грапей ) в исходной сети, а в плоской сети [ ~( 4 2я — 4 [см., папример, [18е[). — Прим. варев. 193 ГЛ. 10. КРАТЧЛЙП1ИВ ПИПИ И ПОТОКИ МИПИМА11ЬНОИ СТОИМОСТИ Каждой дуге Ам исходной сети будет соответствовать дуга А1! двойственной сети. Каждому разрезу, разделяющему 111, и !У! в исходной сети, будет соответствовать некоторая цепь из 11'; в Л11.
Положим, что пропускная способность Ь!! дуги Аы равна длине 111! дуги АЧ. В атом случае кратчайшая цепь из 11'; в 11'1 будет соответствовать минимальному разрезу, разделяющему 11', и 11'1. Рис. 10.3 иллюстрирует описанное построение. 10.2. Многополюсные кратчайшие цепи (Флойд [63[, Ху [1Щ Мерчленд [158[! Уоршелл [209[) В атом параграфе рассматривается задача нахождения кратчайших цепей между всеми парами узлов сети. Предполагается, как и в з 10.1, что длины о!! могут не удовлетворять неравенству треугольника и условию симметричности. В отличие от з 10.1 теперь величины и1! могут быть и отрицательными.
При этом делается предположение менее ограничительное, чем условие 111! ) 0: сумма длин дуг по любому направленному циклу должна быть неотрицательна (иначе понятие кратчайшей цепи теряет смысл). Заметим, что для любой неориентированной дуги А1! последнее предположение не менее ограничительно: иэ него следует, что г!1! )~ 0 (поскольку неориентированную дугу можно рассматривать как пару прОтивоположно направленных дуг, кал дая из которых имеет ту же длину, что и исходная неориентированная дуга). Как отмечалось в $ 10А, задача оказалась бы тривиальной, если бы выполнялось перавенство треугольника 11!1. + Н!» ) Ы!», в этом случае кратчайшей цепью между произвольной парой узлов !У! и Л!! была бы сама дуга Ам. В произвольной сети лишь некоторые дуги Ам являются кратчайшими цепями из Л!! в 11'!, 'такие дуги будем называть базисными.
Заметим, что в з 10.1 все дуги дерева были базисными (обратное неверно). Предположим, что известна кратчайшая цепь, скажем, из узла Л1р в узел Лрч. Тогда зта цепь должна состоять только из базисных дуг, в протйвном случае она не будет кратчайшей.
Если теперь ввести дугу Аро с длиной, равной длине рассматриваемой цепи из !Ур в Л", то зта дуга Арч будет базисной. Задачу йахождения кратчайших цепей между всеми парами узлов можно решить, добавив базисные дуги (если таких дуг в сети не было) ме1кду всеми парами узлов. При добавлении базисной дуги ей ставится в соответствие длина, равная длине кратчайшей цепи, состоящей из базисных дуг исходной сети. Рассмотрим следующую операцию, определенную для фиксированного узла !у~. 4»1=ш1п(о1ю о1;+о!») (для всех 1~ЙФ)). (1) Эту операцию будем называть термарной. 10.2. МНОГОП011ЮСПЫК КРАТЧАЙ1ПИК ЦКП11 При осуществлении операции (1) сравнивается длина 121А дуги А,А И дЛИНа ЦЕПИ ЛГ1 — Лгт — ЛГА, а ЗатЕМ ДЛИНЕ дуГИ Аза Прненанвается значение 1111 + Ы)з, если й1А ) 2111 + дуь. Оказывается, что если выполнить операцию (1) последовательно для каждого узла Л11 (1 =- 1, 2,..., п), то полученные в результате значения с(1А будут длинами кратчайших цепей между 4 --ь г г г / -ь з + А 'Ь Р и с.
10А. всеми парами узлон. (Заметим, что при атом общий объем вычислений не превышает и (и — 1) (и — 2) действий слоткения и сравнения.) Идея доказательства атого факта заключается в следующеы. Каждая кратчайшая цепь должна состоять из базисных дуг исходной сети. Значит, надо доказать, что в ревультате выполнения алгоритма будет получена базисная дуга, длина которой равна сумме длин базисных дуг, входящих в кратчайшую цепь. Рассмотрим произвольную кратчайшую цепь; например, одна такая цепь представлена на рис.
10.4. При выполнении операции (1) в сеть будут последовательно добавляться базисные дуги, изображенные пунктиром на рис. 10.4. Так как сумма расстояний по любому направленному циклу в сети неотрицательна, то понятие кратчайшей цепи между любыми двумя узлами имеет смысл. Если при выполнении операции (1) получится дуга Арч, длина которой больше кратчайшего расстояния между Лгр и Лге, то на некотором дальнейшем шаге длина этой дуги обязательно изменится и станет равной кратчайшему расстоянию между 11р и Лге ').
После атого величина огре уже не будет изменяться, поскольку она не может 1) Более строго доказательство можно провести следующим образом. Пусть Л'1 — пРомежуточный узел з кратчайшей цепи из Л'в з Л', имеющий наименьший индекс, а Л"1 и ЛА — дза узла, соседних с Л11 з этой цепи. Прн вычислениях по формуле (1) получится А1з ) А1 + 42А, и мы введем ноэу1о дугу А1А длины 012+ Ы з.
Таким образом, для дуги А;ь утверждение доказано, Теперь заменим исходную кратчайшую цепь из Лр з Л1 другой, содержащей ноэу1О дУгу А;», зта цепь имеет ту >ке длину, но меньшее число узлов, Далее продогпкаем рассуждения по индукции.— Прим. иерее. 2СС ГЛ. 10. КРАТЧАЙШИК ЦВПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ быть уменыпена. На рис. 10.4 показана произвольная кратчайшая цепь мезкду узлами, скажем, Хз и Хз, состоящая из базисных дуг Ам, Ам, Азз, Азз и Аз„. Если выполнить операцию (1) последовательно для каждого узла дзз (1 = 1, 2,..., 9, ...), то новые базисные дуги будут появляться одна за другой: сначала Азз, затем Азз, Азз и Агз.
Чтобы проследить, какие дуги исходной сети входят в кратчайшую цепь, построим следующую справочную таблицу, которая заполняется по мере последовательного выполнения операции (1). В самом начале элемент (з, Й) таблицы, стоящий на пересечении з-й строки и Й-го столбца, полагаем равным Й. После выполнения операции (1) пусть элемент (з, Й) указывает первый промежуточньгй узел в кратчайшей цепи между Л~з и 11'з, если такой узел существует. Если такого з промежуточного узла не существует, то полагаем элемент (з, Й) равным Й, Таким образом, (1, 1), если з(1з )зззг+зз1з, (д Й) =, (2) (1, Й), если зззз~~з(1з+1)зз.
Во всех вычислениях мы до сих пор полагали, что 11„=0 для всех з. Если Р в с. 10,5. положить зз11 = оо для всех з, а в операции (1) разрешить, чтобы з = Й, то последовательное выполнение операции (1) дает возможность найти кратчайшие циклы, содержащие узел Хз. Если при таких вычислениях величина зз11 становится отрицательной, то это показывает, что в сети существует оззрицателькмй цикл (т.
е. такой, у которого сумма длин входящих дуг отрицательна). Задача нахождения отрицательных циклов в сети имеет много различных приложений. Рассмотрим сеть, изображенную на рис. 10.5; длины дуг указаны в табл. 10.1. Необходимо найти кратчайшие цепи между всеми парами узлов. Выполнение операции (1) при 1 = 1 заключается в том, что пересчитываются все элементы табл.
10.1, не лежащие в первой строке или первом столбце. Имеем 11гз. — — шш(з(гз, 11гз+Ызз) = шш(оо, 11+30) =41, з(м . '= ш1п (Ызг, 1111+зззг) =шзп (оо, 30+ 11) = 41; все остальные элементы пе изменяются. Выполнение операции (1) при 1 = 2 заключается в том, что пересчитываются все элементы табл, 10.1, не лежащие во второй 201 10.2. МНОГОПОЛЮСНЫЕ КРЛТЧЛЙШИЕ ЦЕПИ Таблица 10.1 01 02 Оз 04 Оз Ое От 01 02 Оз 04 Ое 07 строке и втором столбце. Заметим, что при этом уже используются результаты вычислений при 1 = 1. Имеем 1(зь:=ш1п(1(р„4, +ь(м)=шш(19, 41+12)=19, 011 . .= Пцп (д1„1112 +ь(м) = ш1п (со, 11+12) = 23, ь(1ь, = шш ф1ь, б12 + Ызь) = ш1п (со, 11+ 2) = 13, ь(зь. =1П1п(ь(зь, 1122 +1(м) =1п1п(оо, 41+2)=43, ь(ьз =1(34~ а»1=1111~ ь(ы=-Аь~ «ьз=ь(зь' остальные элементы не изменяются. Продолжая вычисления таким образом, окончательно получим табл. 10.2, в которой указаны длины кратчайших цепей, и справочную табл.
10.3, с помощью которой определяются узлы, входящие в кратчайшие цепи. Пусть, например, нужно найти кратчайшую цепь из Х1 в Л"з. Тогда по табл. 10.3 сначала находим элемент (1,6) = 2. Затем находим (2,6) = 4 и (4,6) = 6. Следовательно, кратчайшая цепь из Л'1 в Л', проходит через узлы Л', Л'ь. В общем случае если нужно найти кратчайшую цепь из Хр в Л'», то по справочной таблице сначала находим элемент (р, а) = = а, который означает, что узел Лзь является первым промежуточным узлом в кратчайшей цепи из Хр в Л' . Затем находим элемент (Й, д), который указывает первый промея;уточный узел в кратчай1пей цепи из Лл в Х . Этот процесс продолжается до твх пор, пока не будет найден элемент (1, д) = д, который означает, что найдены все узлы, входящие в кратчайшую цепь из Л' в Л'ю а именно 2оз Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
