произведение

Х(р) = X(vt, v2) 0 X(v2, v3) 0 • • • 0 X(vk-i, vk).

Единичный элемент 1 для умножения будет меткой пустого пути (длины 0). Если путь р не является путём в графе (то есть при некотором г пара (иг-,не является ребром), то в выражении

для Х(р) один из множителей и потому всё произведение (см. пункт 2 определения замкнутого полукольца) равны 0.

Мы будем иллюстрировать применение замкнутых полуколец на примере задачи о кратчайших путях (для случая неотрицательных весов). В качестве S возьмём множество S = U {оо} (множество неотрицательных вещественных чисел с добавленной (плюс) бесконечностью). Тогда веса всех рёбер будут элементами S. Операцией «умножения«0 будет обычное сложение; чтобы не запутаться, отныне мы будем брать в кавычки слова «произведение», «сумма» и т.п., если они относятся к операиям в полукольце. Тогда «произведением» меток на рёбрах вдоль пути будет сумма весов рёбер, то есть вес пути. «Единицей» полукольца будет нейтральный элемент относительно сложения, то есть 0: можно написать 1 = 0. Метка пустого пути (обозначим его е) будет равна нулю: Х(е) = w(s) = 0 = 1.

Возвращаясь к общей ситуации, определим соединение, или конкатенацию (concatenation) двух путей р\ = (v\,v2,... ,Vk) и р2 = (vk, vk+i,... ,vi) как путь

Plop2 = (vt, v2,... , vk, vk+i,... , vi),

(соединение имеет смысл, если конец первого пути совпадает с началом второго). Ассоциативность «умножения» гарантирует нам, что метка соединения путей равна «произведению» их меток:

A(piop2) = А(иь v2) 0 X(v2, v3) 0 • • • 0 X(vk-i, vk)Q

X(vk, vk+1) 0 X(vk+1,vk+2) 0 • • • 0 A(u/ i, vi)

= (A(ub v2) 0 X(v2, v3) 0 • • • 0 X(vk-i, vk))Q (X(vk, vk+1) 0 X(vk+1, vk+2) 0 • • • 0 A(u/ i, vi))

= X(Pl)QX(p2)

Как мы увидим, различные задачи о путях могут рассматриваться как частные случаи такой общей задачи. Дано замкнутое полукольцо и граф с метками на рёрах; найти (для всех пар вершин г, j G V) суммы меток по всем возможным путям из г в j:

Uj = ®X(p).(26.11)

Эта «сумма» может быть бесконечной (путей из г в j может быть бесконечно много). При её вычислении можно включать и пути,

Рис. 26.6 26.7 Сумму меток путей pi ор2 и pi ops можно записать как (A(pi) 0 А(рг)) Ф (-ЧрО © -Чрз))- По свойству дистрибутивности это выражение равно A(pi)0(A(p2)©A(p3)).

Рис. 26.7 26.8 Благодаря циклу с имеется бесконечно много путей из вершины v в вершину х, а именно, pi о р2, pi о с о р2, pi о с о с о р2 и т. д.

проходящие по отсутствующим в графе рёбрам: как мы договорились, метки таких рёбер равны 0, поэтому и метки этих путей равны 0 и по нашему предположению (свойство 6) на «сумму» такие пути не влияют. Коммутативность и ассоциативность оператора © (свойство 7) позволяют нам не указывать порядок путей при суммировании.

Вернёмся к нашему примеру, в котором элементами S были неотрицательные действительные числа и символ оо, а «умножением» было обычное сложение. Если мы теперь определим «сложение» как взятие минимума (точнее, точной нижней грани, так как мы должны определить его и для бесконечных последовательностей), то получим замкнутое полукольцо (свойства 1-8 легко проверить). Отметим, что элемент 0=оо является нейтральным элементом для «сложения»: min (а, оо) = а.

Если считать меткой ребра его вес, то меткой пути будет также его вес (сумма весов рёбер), а уравнение (26.11) определяет /8j как точную нижнюю грань весов всех путей из г в j.

Понятие полукольца позволяет выполнять алгебраические преобразования с метками путей. Пример такого рода приведён на рис. 26.7.

В более сложных случаях число путей может быть бесконечно. Такой пример приведён на рис. 26.8. Здесь (считаем, что других путей из и в ж нет) формула (26.11) приводит к «сумме»

A(pi) 0 А(р2) © A(pi) 0 А (с) 0 А(р2) © X(Pl) 0 А (с) 0 А (с) 0 А(р2) © ... =

= A(pi) ©(10 А (с) © А (с) 0 А (с) ©...)© А(р2)

Для краткой записи такой «суммы» введём следующее определение. Пусть а - произвольный элемент замкнутого полукольца S. Замыканием (closure) элемента а назовём выражение

а* = 1 ф а ф (а а) ф (а а а) ф ...

Тогда предыдущее выражение (для рис. 26.8) можно записать как А(Р1).(А(с))*.А(Р2).

В нашем примере полукольца (соответствующего задаче о кратчайших путях) имеем а* = min{A;aA; = 0,1, 2,...} = 0 для любого элемента а 0. Что и не удивительно: если цикл имеет неотрицательный вес, то идти по нему нет смысла.

Примеры замкнутых полуколец

Один такой пример мы уже расмотрели: полукольцо S\ = {M°U {оо}, min,+, оо, 0}. Мы можем расширить это полукольцо, разрешив отрицательные элементы, а также элемент -оо. Получится полукольцо 5*2 = {Ш. U {+оо} U { -оо}, min, +, +оо, 0} (упр. 26.4-3). Это полукольцо можно использовать при доказательстве правильности алгоритма Флойда-Уоршалла для случая отрицццательных весов. Отметим, что теперь

Г 0,если а 0, а = <

[ -оо,если а < 0.

Второй случай (а < 0) говорит нам, что цикл отрицательного веса можно проходить многократно, и веса будут стремиться к -оо.

Задаче о транзитивном замыкании соответствует замкнутое полукольцо 5*3 = ({0,1}, V, Л, 0,1). При этом все рёбра исходного графа имеют пометку 1 (а отсутствующим соответствует значение 0 = 0, как мы говорили). В этом полукольце значение вычисленное по формуле (26.11), равно 1, если парапринадлежит транзитивному замыканию (то есть есть путь из г в j), и равно 0 в противном случае. Отметим, что для этого кольца 1* = 0* = 1.

Динамическое программирование и сумма меток по путям

Покажем, как можно вычислить выражение (26.11) с помощью алгоритма, аналогичного алгоритму Флойда-Уоршалла и алгоритму вычисления транзитивного замыкания.

Напомним, что нам дано замкнутое полукольцо S и ориентированный граф (G, V), рёбра которого помечены элементами S. Мы хотим для каждой пары вершин i,j вычислить «сумму» (в смысле полукольца)

= ©А(Р)

где «суммирование» происходит по всем путям из г в j, а А(р) есть метка пути р, то есть «произведение» меток на его рёбрах.

(к)

Рассмотрим величину I- , которая получится, если ограничить суммирование только теми путями, в которых все промежуточные вершины лежат в множестве {1, 2,... , к}. Для iff можно написать рекурентное соотношение:

4? = © © it~l)r © *8-1))- (26.12)

Это формула напоминает рекурентные соотношения (26.5) и (26.8); разница в том, что в ней есть «множитель» (/ 1)*, соответствующий «сумме»меток всех циклов, начинающихся и кончающихся в к. (Почему не было такого множителя в алгоритме Флойда-Уоршалла с неотрицательными весами и в алгоритме вычисления транзитивного замыкания? Дело в том, что в обоих случах а* = 1 и поэтому этот «множитель» можно было опустить.)