Транзитивное замыкание орграфа

В предыдущей главе для нахождения сильносвязных компонент орграфа G =(V, E) нам нужно было найти матрицу достижимости R. Как было отмечено, для этого можно использовать поиск в глубину или в ширину. Теперь рассмотрим подробнее, что представляет собой матрица R.

Если множество E дуг графа G рассматривать как бинарное отношение на множестве вершин V графа G, то R будет матрицей смежности для графа G *=(V, E *), в котором E * - транзитивное замыкание бинарного отношения E.

Рассмотрим способ нахождения транзитивного замыкания (тоже матрицы R) без применения поиска.

Пусть исходный граф G =(V, E) представлен матрицей смежности A. Можно вычислить матрицу R по матрице А, определяя последовательность матриц A ⁽⁰⁾, A ⁽¹⁾,…, A ^(|V|) следующим образом:

1) a_ij ⁽⁰⁾= a_ij;

2) a_ij ^{( k )}= a_ij ^{( k -1)}Ú a_ik ^{( k -1)}Ù a_kj ^{( k -1)} (5.1)

Утверждение: a_ij ^{( k )}=1 тогда и только тогда, когда существует путь из вершины i Î V в вершину j Î V с промежуточными вершинами, выбираемыми только из множества {1,2,..., k }Í V.

Докажем это утверждение, используя принцип математической индукции:

1. Для k =0 утверждение очевидно, так как a_ij ⁽⁰⁾= a_ij, далее смотри определение матрицы смежности.

2. Пусть утверждение верно для k = t -1, тогда a_ij ^{( t )}, определяемое как

a_ij ^{( t -1)}Ú a_it ^{( t -1)}Ù a_tj ^{( t -1)}, равно единице тогда и только тогда, когда либо a_ij ^{( t -1)}=1, либо a_it ^{( t -1)}=1 и a_tj ^{( t -1)}=1. Другими словами a_ij ^{( t )}=1 в двух случаях:

1) существует путь из вершины i в вершину j, проходящий только по вершинам из множества {1,2,..., t -1},

2) существуют пути из i в t и из t в j, также проходящие только по вершинам из множества {1,2,..., t -1}.

Таким образом, во втором случае путь из вершины i в вершину j проходит по вершинам из множества {1,2,…, t }={1,2,…, t -1}È t, следовательно, a_ij^{( t )}=1 тогда и только тогда, когда существует путь из вершины i в вершину j с промежуточными вершинами, выбираемыми из множества {1,2,..., t }.

Итак, утверждение справедливо для k = t. Следовательно, для любого k =0,1,…,| V | утверждение истино.

На основании доказанного утверждения вытекает, что R = А ^{(| V |)}.

Алгоритм 2.Алгоритм нахождения транзитивного замыкания