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

Обратное транзитивное замыкание

Прямое транзитивное замыкание

Транзитивные замыкания

Обратные отображения

Обратным отображением 1-го порядка для вершины х_iявляется множество элементов x_jтаких, что существует дуга(x_j, х_i), принадлежащая множеству дуг графа, т. е.

Г^-1(х_i) = { x_j: дуга (х_j, х_i) А }.

Обратные отображения 2-го, 3-го и т. д. n-го порядка определяются следующим образом:

Г^-2(x_i)= Г^-(Г^-1(x_i)),

Г^-3(x_i)= Г^-(Г^-2(x_i)),

...

Г^-n(x_i)= Г^-(Г^(n-1)(x_i)).

Для графа на рис. 3.1 обратные многозначные отображения вершины х₁ находятся следующим образом:

Г^-1(x₁)=x₅,

Г^-2(x₁)= Г^-(Г^-1(x₁))=Г^-(x₅)= x₂,x₄,

Г^-3(x₁)= Г^-(Г^-2(x₁))=Г^-(x₂x₄)= x₁,

Г^-4(x₁)= Г^-(Г^-3(x₁))=Г^-(x₁)= x₅ и т.д.

П р и м е ч а н и я:

1. Когда отображение действует не на одну вершину, а на множество вершин Х_q = { х₁, х₂,..., х_q }, то под Г(Х_q) понимают объединение

Г(х₁) Г(х₂)... Г(х_q).

2. Многозначное отображение для неориентированного графа строится, если представить каждое ребро двумя противоположно направленными дугами (рис. 3.2).

Рис. 3.2. Граф: а – неориентированный; б – тождественный ему ориентированный

Прямым транзитивным замыканием некоторой вершины х_i – T⁺(х_i)является объединение самой вершины х_iс прямыми отображениями 1-го порядка, второго порядка и т. д., т. е.

T⁺(х_i) = х_i Г⁺¹ (х_i) Г⁺²(х_i)...

Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.

Так, для графа на рис. 3.1.

Г⁺¹ (х₁) = { х₂, х₃ }, Г⁺²(х₁) = { х₃, х₅ }, Г⁺³(х₁) = { х₃, х₁ }, Г⁺⁴(х₁) = {х₂, х₃}.

Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х₁получается следующим образом:

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

Проанализировав множество вершин, входящих в T⁺(х_i), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины х_i. Таким образом, можно дать второе определение T⁺(х_i).

Прямое транзитивное замыкание некоторой вершины х_i T⁺(х_i)– это множество вершин, достижимых из вершины х_i, т. е. T (х_i) = { х_j | путь из х_i в х_j }.

Обратным транзитивным замыканием некоторой вершины х_i –T^-(х_i)является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n -го порядка, т. е.

T^-(х_i) = х_i Г^-1(х_i) Г^-2(х_i)...

Иначе, обратное транзитивное замыкание для некоторой вершины х_i – T^-(х_i) – это множество вершин, из которых достижима вершина х_i, т. е. T^-(х_i) = { x_j | путь из x_j в х_i }.

Рассмотрим построение обратного транзитивного замыкания для графа на рис. 3.1.

Г^-1(х₁) = { х₅ }, Г^-2(х₁) = { х₂, х₄ }, Г^-3(х₁) = { х₁ }, Г^-4 (х₁) = { х₅ },

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

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 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^-(х₃). Итак, сформировано обратное транзитивное замыкание для вершины х₃.