Достижимость и транзитивное замыкание

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

Определение 19.5. Транзитивное замыкание (transitive closure) орграфа есть орграф с теми же вершинами, но ребро из s в t в этом транзитивном за­мыкании возможно в том и только том случае, ког­да существует ориентированный путь из s в t в задан­ном орграфе.

Другими словами, в транзитивном замыкании име­ется ребро, исходящее из любой вершины в каждую вершину, достижимую из этой вершине в исходном орграфе. Вполне понятно, что транзитивное замыкание содержит в себе всю информацию, необходимую для решения задачи достижимости. На рис. 19. 13 предла­гается к рассмотрению небольшой пример.

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

Перемножение булевых матриц. Булевой матрицей (Boolean matrix) называется матрица, элементы которой принимают двоичные значения, т.е. 0 или 1. Пусть за­даны булевы матрицы А и В. Вычислите произведение С двух заданных матриц, используя логические опера­ции and (u) и or (или), соответственно, вместо арифме-

РИСУНОК 19.13. ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ

Рассматриваемый орграф (вверху) содержит восемь ориентированных ребер, но его транзитивное замыка­ние (внизу) показывает, что существуют ориентированные пути, соединяющие 19 из 30 пар вершин. Структурные свойства орграфа отражаются в его транзи­тивном замыкании. Например, строки 0, 1 и 2 матрицы смежнос­ти в транзитивном замыкания идентичны (равно как и столбцы О, 1 и 2), поскольку эти вершины содержатся в ориентированном цикле рассматриваемого орграфа.

В матричной системе обозначений мы просто записываем эту операцию как С = А* В. Эта операция определена для матриц, состоящих из любых типов элементов, для которых определены операции 0, + и *. В частности, если а + b интерпретируется как логичес­кая операция or, а операция а*Ь — как логическая операция and, то получается умноже­ние булевых матриц. В языке C++ мы можем воспользоваться следующим вариантом:

Глава 19. Орграфы и ориентированные ациклические графы

for (s = 0; s < V; s++) for (t = 0; t < V; t++)

for (i = 0, C[s] [t] = 0; i < V; i++) if (A[s][i] & & B[i][t]) C[s][t] = 1;

Чтобы вычислить элемент C[s][t] произведения матриц, мы инициализируем его значением О, затем присваиваем ему значение 1, если находим некоторое значение i, для которого как A[s][i], так и B[i][t] равны 1. Выполнение этих вычислений эквивалентно присвоению C[s][t] значения 1 в том и только том случае, когда результат побитового выполнения операции and над строкой s матрицы А столбца t матрицы В имеет ненулевое значение.

Теперь предположим, что А - это матрица смежности орграфа А, и мы используем приведенный выше программный код для вычисления С = А*А = А² (простая замена в программном коде обозначения В на А). Если рассматривать этот программный код при­менительно к матрицам смежности, то сразу становится ясно, что он вычисляет: для каж­дой пары вершин s и t мы помещаем в С ребро, ведущее из s и t, в том и только том слу­чае, когда имеется такая вершина i, для которой в А существует как путь из s и i, так и путь из i и t Другими словами, ориентированные ребра в А² в точности соответствуют ориентированным путям длиной 2 в А. Если при этом мы учтем петли в каждой вершине графа А, то в А² появятся ребра графа А, иначе их там не будет. Эта зависимость между умножением булевых матриц и путей в орграфе показана на рис. 19.14. Она немедленно приводит нас к элегантному методу вычисления транзитивного замыкания любого орграфа.

Свойство 19.6. Транзитивное замыкание орграфа можно вычислить путем построения матрицы смежности А этого графа, добавления петли каждой вершины и вычисления А^у.

Доказательство: В соответствии с аргументацией предыдущего параграфа, А³ содержит ребро для каждого пути орграфа длиной меньшего или равного 3, в матрице А ⁴ со­держится каждый путь орграфа, длина которого меньше или равна 4 и т.д. У нас нет необходимости рассматривать пути, длина которых больше V, в силу принципа " кар­тотечного ящика": любой такой путь хотя бы один раз должен повторно пройти через одну из вершин (поскольку в графе всего V вершин), поэтому он не добавляет какую-то новую информацию в транзитивное замыкание, поскольку обе вершины, связан­ные таким путем, соединены также ориентированным путем, длина которого мень­ше V (который можно получить за счет удаления цикла из пути в повторно посещенную вершину). ■

РИСУНОК 19.14.