5.9. ЗАДАЧИ О ПУТЯХ И УМНОЖЕНИЕ МАТРИЦ

Пусть — замкнутое полукольцо. Можно определить -матрицы элементов из с обычными суммой и произведением. Иными словами, пусть матрицы состоят из элементов соответственно для Тогда означает, что для всех означает, что для всех Легко доказать следующую лемму.

Лемма 5.10. Пусть -замкнутое полукольцо и множество -матриц над Пусть обозначают соответственно сложение и умножение матриц, матрица, все элементы которой равны 0, а матрица с 1 на главной диагонали и вне ее. Тогда замкнутое полукольцо.

Доказательство. Оставляем в качестве упражнения.

Пусть ориентированный граф, где Пусть функция разметки определена, как в алгоритме 5.5, а обозначает -матрицу с Следующая лемма связывает вычисление, выполняемое алгоритмом 5.5, с вычислением замыкания матрицы в полукольце -матриц над

Лемма 5.11. Пусть таковы, как сказано выше. Тогда элемент матрицы равен

Доказательство. для Индукцией по легко показать, что элемент матрицы А а равен сумдое стоимостей путей длины идущих из Отсюда непосредственно следует, что элемент матрицы А а равен сумме стоимостей всех путей из в

Из леммы 5.11 вытекает, что алгоритм 5.5 можно рассматривать как алгоритм вычисления замыкания матрицы. В теореме 5.5 утверждалось, что алгоритм 5.5 требует элементарных операций

(т. е. операций и над элементами полукольца). Обычный алгоритм умножения матриц также требует элементарных операций. Мы покажем, что, когда элементы берутся из замкнутого полукольца, вычисление произведения двух матриц эквивалентно (по сложности) вычислению замыкания матрицы. Точнее, если дан какой-то алгоритм вычисления произведения матриц, то можно построить алгоритм вычисления замыкания, и обратно, причем порядок времени вычисления будет тем же. Значение этого результата лучше прояснится в гл. 6, где будет показано, что, когда элементы берутся из кольца, для умножения матриц хватает менее чем операций. Рассматриваемая конструкция состоит из двух частей.

Теорема 5.6. Если замыкание произвольной -матрицы над замкнутым полукольцом можно вычислить за такое время что то существует алгоритм умножения двух -матриц с временем работы удовлетворяющим неравенству для некоторой постоянной с.

Доказательство. Пусть надо вычислить произведение двух -матриц Сначала образуем -матрицу

и найдем ее замыкание. Заметим, что

Следовательно,

Так как можно прочитать в правом верхнем углу, заключаем отсюда, что

Это доказательство теоремы 5.6 имеет следующую интерпретацию в виде графа. Рассмотрим граф узлами Разобьем их на три множества Будем считать, что все ребра графа идут либо из в либо из в Такой граф

Рис. 5.21. Интерпретация теоремы 5.6 в виде графа.

изображен на рис. 5.21. Пусть такие -матрицы, что элемент матрицы А служит меткой ребра, идущего из в элемент матрицы В служит меткой ребра, идущего из Тогда элемент произведения оказывается суммой меток путей, идущих из поскольку каждый такой путь образован ребром из в некоторый узел и следующим за ним ребром из Поэтому сумма меток всех путей из совпадает с ( элементом матрицы

Теперь докажем обращение теоремы 5.6. По данному алгоритму умножения матриц можно найти алгоритм замыкания, время работы которого с точностью до постоянного множителя совпадает с временем работы данного алгоритма.

Теорема 5.7. Если произведение любых двух -матриц над замкнутым полукольцом можно вычислить за такое время что то существует алгоритм, вычисляющий замыкание матрицы за время удовлетворяющее неравенству для некоторой постоянной с.

Доказательство. Пусть X — -матрица. Сначала рассмотрим случай, когда степень числа 2, скажем 2. Разобьем X на четыре матрицы размера

В силу леммы 5.11 можно считать, что матрица X представляет граф в котором множество узлов разбито на два множества размера 2-1. Матрица А представляет ребра между узлами множества матрица ребра между узлами из матрица В — ребра, идущие из узлов множества в узлы множества а

Рис. 5.22. Граф О.

матрица С — ребра, идущие из узлов множества V, в узлы множества Это отражено на рис. 5.22.

Путь из концы которого принадлежат либо

1) никогда не выходит за пределы либо

2) для некоторого найдутся такие узлы где что все лежат в все в а рассматриваемый путь идет из внутри затем по некоторому ребру уходит в потом вдоль некоторого пути внутри идет в узел после чего по некоторому ребру уходит в затем по пути внутри идет в и, наконец, приходит в откуда вдоль пути внутри идет в Этот тип пути показан на рис. 5.23.

Сумма меток, приписанных путям, удовлетворяющим условию 1 или 2, очевидно, равна А именно, представляет пути, идущие из затем в и далее в на рис. 5.23.

Рис. 5.23. Пути, удовлетворяющие условию 2.

Следовательно, представляет те пути, соединяющие узлы в которые либо состоят из одного ребра, либо прыгают прямо в остаются там на некоторое время и затем прыгают обратно в Все пути, соединяющие узлы из множества можно представить в виде последовательности путей, представленных матрицей Таким образом, представляет все пути, соединяющие узлы из Следовательно, верхний левый угол матрицы X занят матрицей

Обозначим через С помощью аналогичных рассуждений можно представить матрицу X в виде

Матрицы можно вычислить, проделав такую последовательность шагов:

Эти шаги требуют выполнения двух замыканий, шести умножений и двух сложений -матриц. Поэтому можно записать:

Три слагаемых в правой части неравенства (5.6) — это сложности соответственно замыканий, умножений и сложений. Мы утверждаем, что найдутся такие постоянная с и функция что и удовлетворяет (5.6) для всех k. Базис, т. е. случай тривиален, поскольку постоянную с можно взять сколь угодно большой. Для проведения шага индукции предположим, что для некоторой постоянной с. Из условия теоремы, т. е. из неравенства заключаем, что (Заметим, что Следовательно, из (5.6) вытекает, что

Снова в силу условия теоремы так что

Если взять то (5.7) влечет за собой а это и требовалось доказать.

Если не является степенью числа 2, то можно вложить X в большую матрицу, размер которой есть степень числа 2:

где I — единичная матрица минимально возможного размера. Это вложение увеличит размер матрицы не более чем вдвое, и, значит, постоянная увеличится не более чем в 8 раз. Таким образом, найдется такая постоянная с, что для всех независимо от того, являются ли они степенями числа 2 или нет.

Следствие 1. Время, необходимое для вычисления замыкания булевой матрицы, имеет тот же порядок, что и время вычисления произведения двух булевых матриц того размера.

В гл. 6 мы познакомимся с асимптотически более быстрыми алгоритмами вычисления произведения булевых матриц и тем самым покажем, что транзитивное замыкание графа можно вычислить за время, меньшее

Следствие 2. Время, необходимое для вычисления замыкания матрицы над множеством неотрицательных целых чисел с операциями MIN и в качестве сложения и умножения элементов, имеет тот же порядок, что и время вычисления произведения двух матриц такого же типа.

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