Нахождение транзитивных замыканий по матрице смежности

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х₂графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим 0 в столбец Т⁺для элемента х₂и просматриваем 2-ю строку матрицы. Находим, что элементы a₂₂=1и a₂₅=1. Заносим 1 в 5-ю клетку Т⁺. 2-я клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг начинается просмотром 5-й строки матрицы смежности, соответствующий вершине х₅графа. Находим, что элементы a₅₁=1 и a₅₄=1, т. е. из вершины х₅ имеются дуги в вершины х₁ и х₄ или иначе из вершины х₂ имеются пути длиной 2 в вершины х₁ и х₄. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T⁺(х₂). На 3-м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим элементы a₁₂=1, a₁₃=1, a₄₃=1. В соответствующие свободные клетки заносим значения

Рис. 3.3. Построение прямого (а) и обратного (в) транзитивных замыканий для графа (б)

Это возможно сделать только для вершины х₃, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х₃нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.

Таким образом, в столбце T⁺(х₂)стоят числа равные длине пути от вершины х₂ к соответствующим вершинам графа. Путь от х₂ к х₃равный 3 показан штриховой линией на рис. 3.3,б. В столбце T⁺(х₂) отмечены все вершины, достижимые из вершины х₂, следовательно, они входят в T⁺(х₂).

T⁺(х₂) = { х₁, х₂, х₃, х₄, х₅ }.

Во втором столбце показано построение прямого транзитивного замыкания вершины х₁ – T⁺(х₁).

T⁺(х₁) = { х₁, х₂, х₃, х₄, х₅ }.

Нахождение обратного транзитивного замыкания по матрице смежности показано на рис. 3.1,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х₃ – T^-(х₃), которое на-чинается с занесения 0 в 3-ю клетку строки T^-(х₃). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1, просматриваем 3-й столбец матрицы А. Определяем элементы равные 1, т. е. a₁₃=1 и a₄₃=1. Следовательно, в графе из вершин х₁ и х₄ есть дуги в вершину х₃. Заносим 1 в 1-ю и 4-ю клетки T^-(х₃). На втором шаге просматриваем 1-й и 4-й столбцы матрицы A. Находим a₅₁=1, a₆₁=1, a₅₄=1и проставляем 2 (так как длина пути от этих вершин до вершины х₃ равна 2) в свободные клетки T^-(х₃), т. е. в 5-ю и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбцов матрицы A. Элементы a₂₅=1, a₆₅=1, a₆₆=1 позволяют поставить 3 во 2-ю клетку строки T^-(х₃). 4-й шаг просмотра 2-го столбца дает элементы a₁₂ = 1 и a₂₂ = 1, уже вошедшие в T^-(х₃). Итак, сфор-мировано обратное транзитивное замыкание для вершины х₃.

T^-(х₃) = { х₁, х₂, х₃, х₄, х₅, х₆ }.

Числа, стоящие в клетках T^-(х₃), показывают длину кратчайшего пути от соответствующих вершин до вершины х₃.

Во второй строке показано формирование обратного транзитивного замыкания вершины х₁.

T^-(х₁) = { х₁, х₂, х₅, х₆ }.