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

187

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

1. В(1) = 1,

1. В(п) не убывает при возрастании п,

1. 4B(n)^B(2n)^8B(n).

Комментарий к условию 3. Неравенство В(2п) s= 8В(п) отсекает те алгоритмы умножения булевых матриц, сложность которых рас­тет быстрее чем п³. Алгоритм должен построить п² элементов матри­цы-произведения, поэтому его сложность не может расти медленнее чем п², и в соответствии с этим в ограничения включается неравен­ство 4В(п)^В(2п).

Для булевой матрицы X порядка п будем, как и прежде, обозна­чать ее транзитивно-рефлексивное замыкание через X*.

Пусть G — ориентированный граф с п вершинами и С —его мат­рица смежности. Предположим вначале, что п—четное число: п = 21. Разобьем множество вершин V = {v₁, v₂,..., v_2l} графа G на два под­множества У₁ = {v₁, v₂,..., V;} и V₂ = {v_;+1, v_l+2, ...,v_2l}, а множество ре­бер графа G — на четыре подмножества Е₁₁,Е₁₂,Е₂₁,Е₂₂: начало каж­дого из ребер из множества E_pq принадлежит V_p, а конец — V_q, где p,qe{1, 2}. Если исходная матрица С представлена в блочном виде

(11 с12л

с21 C 22 ,

где каждый блок—это матрица порядка I, то матрица C_pq несет пол­ную информацию о ребрах из множества E_pq. Рассмотрим пути в гра­фе G, соединяющие вершины из множества У₁. Назовем ходом путь из вершины в вершину этого множества, представляющий собой

65535. либо продвижение по ребру, принадлежащему Е₁₁,

65535. либо продвижение по ребру, принадлежащему Е₁₂, за которым сле­дует некоторый путь по ребрам из Е₂₂ и затем продвижение по ребру, принадлежащему Е₂₁.

65535. 188