Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим 0 в столбец Т+для элемента х2и просматриваем 2-ю строку матрицы. Находим, что элементы a22=1и a25=1. Заносим 1 в 5-ю клетку Т+. 2-я клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг начинается просмотром 5-й строки матрицы смежности, соответствующий вершине х5графа. Находим, что элементы a51=1 и a54=1, т. е. из вершины х5 имеются дуги в вершины х1 и х4 или иначе из вершины х2 имеются пути длиной 2 в вершины х1 и х4. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T+(х2). На 3-м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим элементы a12=1, a13=1, a43=1. В соответствующие свободные клетки заносим значения
Рис. 3.3. Построение прямого (а) и обратного (в) транзитивных замыканий для графа (б)
Это возможно сделать только для вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х3нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.
Таким образом, в столбце T+(х2)стоят числа равные длине пути от вершины х2 к соответствующим вершинам графа. Путь от х2 к х3равный 3 показан штриховой линией на рис. 3.3,б. В столбце T+(х2) отмечены все вершины, достижимые из вершины х2, следовательно, они входят в T+(х2).
T+( х2 ) = { х1, х2, х3, х4, х5 }.
Во втором столбце показано построение прямого транзитивного замыкания вершины х1 – T+(х1).
T+( х1 ) = { х1, х2, х3, х4, х5 }.
Нахождение обратного транзитивного замыкания по матрице смежности показано на рис. 3.1,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х3 – T-( х3 ), которое на-чинается с занесения 0 в 3-ю клетку строки T-( х3 ). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1, просматриваем 3-й столбец матрицы А. Определяем элементы равные 1, т. е. a13=1 и a43=1. Следовательно, в графе из вершин х1 и х4 есть дуги в вершину х3. Заносим 1 в 1-ю и 4-ю клетки T-(х3). На втором шаге просматриваем 1-й и 4-й столбцы матрицы A. Находим a51=1, a61=1, a54=1и проставляем 2 (так как длина пути от этих вершин до вершины х3 равна 2) в свободные клетки T-(х3), т. е. в 5-ю и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбцов матрицы A. Элементы a25=1, a65=1, a66=1 позволяют поставить 3 во 2-ю клетку строки T-( х3 ). 4-й шаг просмотра 2-го столбца дает элементы a12 = 1 и a22 = 1, уже вошедшие в T-(х3). Итак, сфор-мировано обратное транзитивное замыкание для вершины х3.
T-( х3 ) = { х1, х2, х3, х4, х5, х6 }.
Числа, стоящие в клетках T-( х3 ), показывают длину кратчайшего пути от соответствующих вершин до вершины х3.
Во второй строке показано формирование обратного транзитивного замыкания вершины х1.
T-( х1 ) = { х1, х2, х5, х6 }.