Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

для некоторой сети кратчайшие расстояния использовать для вычислений в следующей сети. То есть, например, матрица рас­ стояний Dx„x„(N —Я) должна быть заменена матрицей (X).

По теореме 10.1 будут получены следующие матрицы расстояний:

кратчайшие расстояния между всеми парами узлов, не.лежащими

Операции композиции матриц должны выполняться в следую­ щем порядке:

А ® Х а ® В и Х в ,

AU Х А U В ® Х в @С U Хс,

А[ ] Х а \ ] В \} Х в \}С ® x c ® d и X D,

A U Х А U • • • U F ® X f ®G U X q,

А { ] Х а {] . . . и С ф Х е ф Я .

При этих вычислениях матрица DAxB(N), полученная при выпол­

жения (таково же и число операций сравнения). На шаге 1 число сложений равно (t © 8 )3 ф ( т — 2)(£© 28)3. На шаге 2 —

2 (*+ S)3 + ( m - 2 )(* + 26)3. .

На шаге 3 —

2 {t + (2t + 8) -f- . . . + [(m — 2) t -f- (m —3) 8 ]} • 8 (t + 8 ) + + 2 [(m— 1 )f + (m — 2 ) 6 ] 6£ = m( m — l ) i 28 +

+ 2 (m — 1) (m — 2) tb2,-f (m — 2) (m — 3) 83.

Таким образо..., общее число операций сложения равно

(2 т — 1) t3-f- (иг2 + 11m — 15) t2b -f-

+ (2m2 + 18m — 35) tb2 + (m2 + 11m — 23) 83. (5)

Если, не 'используя декомпозиционного алгоритма, выполнить тернарные операции непосредственно на всей сети, то общее

14 т x v

названа линейной, так как при этом т пересекающихся подмно­ жеств А, В, . . ., Н расположены как быв линию (рис. 10.7 (а)). Можно рассмотреть декомпозицию сети, в которой подмножества

Р и с . 10.8.

на сети А*, В*, С*, Е * и затем осуществить линейную декомпози­ цию сети В* на две меньшие — A, F, а. сети Е* на три меньшие —

Пусть имеется сеть с п узлами, и надо найти в ней кратчайшие пути между р выделенными узлами, р ^ п. Будем говорить, что некоторая сеть с р узлами эквивалентна по расстоянию исходной сети с п узлами, если кратчайшие расстояния между р (р — 1 )

парами выделенных узлов в обеих сетях одинаковы. На рис. 10.8 изображены две сети, которые эквивалентны по расстоянию отно­ сительно выделенных узлов N t, JV2, N s, N t .

Понятие эквивалентности по расстоянию может быть исполь­ зовано для удаления из сети на некотором этапе вычислений тех узлов и дуг, которые не влияют на этом этапе на вычисления крат­ чайших расстояний. На рис. 10.9 приведены некоторые примеры сетей, эквивалентных по расстоянию. В частности, если сеть с 4 узлами, изображенную на рис. 10.9 (с), превратить в изобра­ женную на этом же рисунке сеть, с 3 узлами, то все кратчайшие расстояния между узлами N±, N 2, N 3 могут быть найдены в но­ вой сети.

Используя. простые преобразования сети, изображенные на рис. 10.9, можно удалить из сети п — р узлов и построить новую

14*

212 гл. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ стоимости

сеть с р узлами, эквивалентную по расстоянию исходной сети. Затем к новой сети можно применить тернарные операции или

декомпозиционный алгоритм. Можно считать, что, когда в дока­ зательстве теоремы 10.1 вычислялась матрица D x x ( A \ j X ) , из сети N было удалено все множество узлов А.

10.4.Потоки минимальной стоимости

Вгл. 8 каждой дуге сети соответствовала пропускная способ­

ность bt], указывающая максимальное количество потока, кото­ рое можно пропустить через эту дугу. Пусть теперь, кроме того,

Формально задача ставится следующим образом: минимизировать

0 ^ . х ц ^ Ь ц (при всех i, j).