Глава 7. Сводимость

Непосредственно видно, что (i, j)-элемент матрицы C_nv(C₁₂AC*₂AC₂₁) равен 1, если и только если существует ход, соединяющий вершины

V;, Vj G У_г. При этом ясно, что из V; можно добраться в Vj О;, Vj е V_x) по

ребрам графа G, если и только если существует последовательность хо­дов, приводящая из v_t в у,-, т. е. если и только если (i, _/)-элемент мат­рицы

(C_nV(C₁₂AC*₂AC₂₁))*

равен 1. Обозначим эту матрицу F_n. Мы имеем

*21 ^2₂

для некоторых матриц F₁₂, F₂₁, F₂₂, при этом матрица F_pq, р, q g {1, 2}, несет информацию о существовании путей из вершин множества V_p в вершины множества V_q. Рассуждениями, сходными с приведенными выше, можно показать, что

F₁₂ = F_nAC₁₂AC*₂, F₂₁ = C*₂AC₂₁AF_n, F₂₂ = С*₂₂ V (С*₂ А С₂₁ A F_n А С₁₂ А С*₂);

эти выражения удобны для вычисления матрицы С*: четыре матри­цы F_{p q}, р, q g {1, 2}, можно найти, выполнив два построения транзи-тивно-рефлексивных замыканий, шесть умножений и два сложения матриц порядка Z:

U = С*₂, V = С₁₂ A LT, W = U А С_2Ъ F_n = (C_nV(VAC₂₁))*, F₁₂=F_nAV, F₂₁ = W AF_n, F₂₂ = UV(F₂₁AV).

Мы указали рекурсивный переход от матриц порядка 21 к матрицам порядка Z. Учитывая, что С* = С для матрицы первого порядка, мы получаем алгоритм вычисления С* для случаев, когда порядок п мат­рицы равен 2^к, к^О. Пусть для умножения булевых матриц исполь­зуется алгоритм со сложностью В{п), которая удовлетворяет услови­ям 1—3, приведенным в начале этого примера. Для п = 2^к мы име­ем следующее соотношение, которому будет удовлетворять сложность

§ 28. Линейная сводимость

189

T(n) полученного алгоритма построения транзитивно-рефлексивного замыкания:

0, еслиk=0,

2T(2^k-1) +6B(2^k-1)+2·2^2(k-1), если k > 0.

, . О, если к = и, _г

^ГС2⁵^ (^ЖЗ)

В силу условия 3 имеем В (2^-) ^ 4B(2^fc-²) при fc ^ 2. Дополнительное использование условия 1 дает нам B(2^2fc-1) ^2^2(fc-1) при fc^ 1. Заме­няя 2²*-¹⁵ во второй строке соотношения (28.3) на B(2^fc-1), получаем

0, еслиk=0,

2T(2^k-1)+8B(2^k-1), если k > 0.

т^к ^' если к = и,

Г(2 )*S (28.4)

Докажем по индукции, что

r(2^fcK4B(2^fc), fc = 0,l,... (28.5)

Для к = 0 это неравенство очевидно, так как ГЦ) = О, ВЦ) = 1. Пусть ЬОи неравенство выполнено для к - 1. Тогда 2Т(2^к-¹) s= 8B(2^fc-¹), и, как следствие (28.4), мы получаем Т{2^к) ^ 16B(2^fc-1). В силу условия 3

мы имеем B(2^fc-!) ^ \в{2^к), откуда следует (28.5).

Если п не есть число вида 2^к, то от матрицы С переходим к мат­рице

^С_{'=» ,°}

С (Г

порядка 2^к, взяв единичную матрицу I_s некоторого порядка, мень­шего чем порядок матрицы С. Таким образом, порядок матрицы С' меньше, чем 2п, т. е. 2^к < 2п. Из (28.5) следует, что

T(n) = r(2^fc)^4B(2^fc).

Так как 2^к < 2п и функция В(п) —неубывающая, получаем 4B(2^fc) ^ ^4В(2п). Отсюда

Т{п) s= 4B(2n) SS 4 ■ 8 • В(п) = 32В(п)

для всех п и

Т{п) = 0{В{п)), (28.6)

что и требовалось.

Из сказанного следует, что если использовать для умножения квад­ратных булевых матриц алгоритм со сложностью, растущей медлен­нее, чем п³, и удовлетворяющей условиям 1—3, то можно строить тран-зитивно-рефлексивное замыкание со сложностью, растущей медлен­нее, чем сложность алгоритма Уоршелла (пример 23.2). Напомним, что

190