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

Через Т (Г) обозначим бинарное отношение, которое выполняется для пары вершин а и а’, если между ними существует последовательность операторов (вершин) вида а_1, а_{2, …,} а_l, а для каждой пары соседних элементов выполняется отношение Г:

а₁ Г а

а₂ Г а₁

а’ Г а_l

(Все диапазоны вершин попарно связаны дугами).

Под транзитивным замыканием для а_i подразумевается выполнение отношения Т (Г) для вершин а_i и некоторой вершины а_j (совокупности вершин а_j). Таким образом, путь из а_j в а_i определяет выполнение бинарного отношения Т (Г) для вершин а_j и а_i (то есть наличие пути характеризует транзитивное замыкание для вершины а_i и связанных с нею вершин а_j).

Транзитивный образ вершины а_i - это множество вершин графа, удовлетворяющих отношению Т (Г), то есть образ – это все вершины а_j , в которые ведет пут из данной вершины а_i при условии транзитивного замыкания для рассмотренных вершин.

а_i T (а_i) { а_j }

Вершины а_j должны удовлетворять следующему свойству:

а₁ Г а_i , а₂ Г а_{1, … ,} а_j Г а_n

При n 0 предполагается, что вершины либо непосредственно следуют за рассматриваемой а_i , либо соединены с данной вершиной некоторым путем.

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

T (a_i) = {a_j}, то есть вершины, для которых выполняется отношение Т (Г) транзитивного замыкания с вершиной a_i. Тогда образ вершины a_i - это множество вершин a_j, в которые возможны пути из рассмотренной вершины a_i.

Пример графа:

Рисунок 9 - Граф

Для a_kij (где i – номер яруса, j – номер операции на графе) выполняется условие транзитивного замыкания (условие для образа вершины a_i ), тогда образ вершины a_i имеет вид:

T (a_i) = {a_k11, a_{k12, … ,} a_k33, a_k34}

Вершины a_kij T (a_i) связаны бинарным отношением Т (Г) с вершиной a_i.

Формализация транзитивного замыкания (транзитивного образа вершины)

Вспомогательные множества S₀ и Т_0.

S₀ - множество всех вершин a_i, рассматриваемых на начальном шаге формирования ЯПФ.

S_{0 =} S⁽⁰⁾ = {a_i}

Т₀ – это сформированный на начальном шаге транзитивный образ вершины a_i.

Т₀ = Т⁽⁰⁾ =

Тогда для определения транзитивного образа вершин графа реализуется рекурсивная процедура :

T(ⁿ⁺¹⁾ = T⁽ⁿ⁾ Г(S⁽ⁿ⁾)

S⁽ⁿ⁺¹⁾ = T⁽ⁿ⁺¹⁾ \ T⁽ⁿ⁾, где Г(S⁽ⁿ⁾) - множество вершин графа, в которые ведут дуги из вершин множества S⁽ⁿ⁾;

n – номер шага процедуры;

S⁽ⁿ⁾ - это множество вершин графа на n-ом шаге, связанных с рассмотренной вершиной a_i путями. Выполнение шагов алгоритма интерпретируется дискретно во времени. Через Tⁿ обозначено дополнительное множество на (n+1) шаге, связанных путями с данной вершиной a_i.

Пример реализации для рассмотренного вида графа (рисунок 1).

T⁽ⁿ⁺¹⁾ = Tⁿ Г(S⁽ⁿ⁾ )

S⁽ⁿ⁺¹⁾ = T⁽ⁿ⁺¹⁾ \ T⁽ⁿ⁾

1. S⁽⁰⁾ = {a_j}, T⁰ =

2. T¹ = {a_k11, a_k12} = {a_k11, a_k12}

S¹ = {a_k11, a_k12}

3. T² = {a_k11, a_k12} {a_k21, a_k22, a_k23} = {a_k11, a_k12, a_k21, a_k22, a_k23}

S²= {a_k21, a_k22, a_k23}

4. T³, S^{3 –} те операции, которые зависимы от a_i и определены на соответствующем l-oм шаге процедуры.

5. S³= {a_k31, a_k32, a_k33, , a_k34}

T^{3 –} является образом вершины a_i, учитывающей как прямые, так и транзитивные зависимости от операций a_i.

Условие окончания реализации процедуры формирования образа Г(S⁽ⁿ⁾) = .

Транзитивный образ вершины определяет те вершины графа, которые должны находиться на нижестоящих ярусах ЯПФ. Соответствующий ярус ЯПФ формируется на основе выражения S⁽ⁿ⁺¹.⁾

Обратное транзитивное замыкание определяется в том случае, если реализуется бинарное отношение T^-1(Г). Бинарное отношение выполняющееся для пары вершин, если на графе существует путь из вершин из вершин a_i, a_j.

На основе бинарного отношения T^-1(Г) формируется некоторый прообраз рассматриваемой вершины a_j.

T^-1(Г) (a_i, a_j)

T (Г) (a_i, _…, a_j)