(S.-f, •, О, 1), где S - множество элементов, а + и • - бинарные операции на S, обладающие следующими пятью свойствами:

1) (S, +, 0) - моноид, т. е. множество S замкнуто относительно + {a-\-bS для всех а и b из S), операция -f ассоциативна (а4- (Ь+с)= (а4-Ь)+с для всех а, Ь, с из S) и О служит единичным элементом (а+0=0+а=а для всех а из S). Тройка (S, •, 1) также является моноидом. Кроме того, мы предполагаем, что О служит аннулятором, т. е. д. 0=0-0=0.

2) Операция + коммутативна (a+b=b-\-ay и идемпотентна (а-\-а=а).

3) Операция • дистрибутивна относительно + (а • (Ь -Ь с)=а • b + + а • с и (Ь+с) •а=Ь- а+с • а):

4) Если а±, Оа, . . ., flj, . . . - счетная последовательность элементов из S, то сумма fli-faa-f. . .+аг+. . . существует и единственна. Более того, ассоциативность, коммутативность и идемпотентность выполняются не только для конечных, но и для бесконечных сумм.

5) Операция • дистрибутивна не только относительно конечных сумм, но и относительно счетных (это не следует из свойства 3). Таким образом, из свойств 4 и 5 вытекает, что

(2a,)-(y) = 2(«,-)=S(S(«,-V)-

пример 5.9. Приведем три системы замкнутых полуколец. 1. Пусть Si=({0, 1), +, •, О, 1), а сложение и умножение заданы таблицами

Свойства 1-3 проверить легко. Что касается свойств 4 и 5, то заметим, что счетная сумма равна О тогда и только тогда, когда все слагаемые равны 0.

2. Пусть Si={R, MIN, +, +00, 0), где R - множество неотрицательных вещественных чисел, включая -f-cx). Легко проверить, что -foo служит единичным элементом для MIN, а О - для +.

3. Пусть S - конечный алфавит (т. е. множество символов) и 8з= (f Z, и , •, 0, {е}), где f i - семейство множеств, состоящих из конечных цепочек символов из Е, включая пустую цепочку в (т. е. цепочку длины 0). Здесь U обозначает операцию объединения

5.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ

множеств, а • - их конкатенацию Единичным элементом для и служит 0, а для • - {в}. Свойства 1-3 читатель может проверить сам. Что касается свойств 4 и 5, то достаточно заметить, что счетные объединения определяются такой эквивалентностью: (AiU UaU- • •) равносильно xAt для некоторого i. □

Центральной операцией в нашем анализе замкнутых полуколец будет унарная операция *, называемая замыканием. Если (S, +, •,

о, 1) - замкнутое полукольцо и agS, то положим а*-Уа, где

ао=1 и а=а-а-. Иными словами, значение а* равно бесконечной сумме 1+а+а-а+аа-а+. . . . Заметим, что свойство 4 определения замкнутого полукольца гарантирует, что а* б S. Из свойств 4 и 5 вытекает равенство а* = 1+аа*. Отметим, что 0* = 1* = 1.

Пример 5.10. Рассмотрим полукольца Si, Sa и Ss из примера 5.9. В Si выполняется а* = 1 для а=0 или 1. В Sa равенство а*=0 выполнено для всех а £ 7?. В Ss выполняется Л* = {е} и {Лха- • • А>1 а XtA для 1<1<й} для всех AF,. Например, {а, Ь}* = = {е, а, Ь, аа, аЬ, Ьа, bb, ааа, . . .}, т. е. {а, Ь}* состоит из всех цепочек символов а и Ь, включая пустую цепочку. Вообще Fx= =5(2*), где SiX) обозначает множество-степень для X. □

Теперь возьмем ориентированный граф G= {V, Е), в котором каждое ребро помечено элементом некоторого замкнутого полукольца (S, +, •, О, 1) ). Определим метку пути как произведение (•) меток ребер, составляющих этот путь, причем метки берутся в порядке прохождения ребер. В частности, метка пути нулевой длины равна 1 (единичному элементу для операции • рассматриваемого полукольца). Для каждой пары узлов (v, w) определим с (и, w) как сумму меток всех путей между v к w. Назовем с (и, w) стоимостью прохождения т v в w. Условимся считать, что сумма по пустому множеству путей равна О (единичному элементу для операции + нашего полукольца). Заметим, что если G имеет циклы, то между V и W может быть бесконечно много путей, но аксиомы замкнутого полукольца гарантируют, что c(v, w) определяется корректно.

Пример 5.11. Рассмотрим ориентированный граф на рис. 5.17,

в котором каждое ребро помечено элементом полукольца Si, описанного в примере 5.9. Метка пути v, w, х равна 1 • 1 = 1. Простой

1) Конкатенацией А-В множеств А и В называется множество {х\х=уг. уА и гВ).

2) Читателю следует не упустить из виду аналогию между рассматриваемой ситуацией и недетерминированным конечным автоматом (см. Хопкрофт, Ульман [1969] или Ахо, Ульман [1972]), который мы еще обсудим в разд. 9.1. Там узлы представляют собой состояния, а метки ребер - символы из некоторого конечного алфавита.

Рис. 5.17. Помеченный ориентированный граф.

ЦИКЛ КЗ W в W имеет метку 1 • 0=0. Вообще каждый путь положительной длины, идущий из W BW, имеет метку 0. Однако стоимость пути нулевой длины из ш в ау равна 1. Следовательно, c(w, w)=l □

Изложим алгоритм вычисления c{v, w) для всех пар узлов v uw. Основными шагами этого алгоритма, занимающими единицу времени, будут операции +, - и * произвольного замкнутого полукольца. Конечно, для таких структур, как множество всех множеств цепочек над некоторым алфавитом, не понятно, можно ли в принципе реализовать эти операции в отведенное им "единичное время". Но для тех полуколец, которыми мы будем пользоваться, эти операции легко выполнимы.

Алгоритм 5.5. Вычисление стоимости прохождения между узлами

Вход. Ориентированный граф G= (V, Е), где V={vi, v, . . ., Vn) и функция разметки /: (УХ S, где (S, +, •, О, 1) - замкнутое полукольцо. Полагаем l{Vi, t))=0, если (vt, V])E.

Выход. Для всех i и /, заключенных между 1 и п, элемент с (к,, Vj) из S, равный сумме по всем путям из Vi в Vj меток этих путей.

Метод. Вычисляем С/ для всех l<t<n, 1</<п и 0<Л<п. Величины Cij задуманы как суммы меток путей, идущих из у,- в Vj, все узлы которых, кроме, быть может, концов, принадлежат множеству {Vi, Vi, . . ; t)ft}. Например, путь у„, «з, Vg рассматривается при вычислении Cg и Clg, но не Clg. Алгоритм выглядит так:

begin

1. for t 1 until п do С], 1 +l{Vi, V,);

2. for l<i, /<п и do C4i*-l{Vi, Vj);

3. for k*-\ until n do

4. for 1 < t, / < rt do

5. cli or+c?*- • (Cfe) * • Cif,

6. for 1 < /, / < rt do с (v,, V,) CI

end □

Теорема 5.5. Алгоритм 5.5 использует O(n) операций +, • ы * из полукольца и вычисляет с {vt, Vj) для l<t, jn.

Доказательство. Легко проверить, что строка 5 выполняется л* раз, причем каждый раз используются четыре операции, и for-циклы в строках 1, 2 и 6 итерируются не более раз каждый. Поэтому достаточно О (л*) операций.