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

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

Если множество E дуг графа G рассматривать как бинарное отношение на множестве вершин V графа G, то R будет матрицей смежности для графа G *=(V, E *), в котором E * - транзитивное замыкание бинарного отношения E, т.е. v _a E * v _b, если существует цепочка v _a= v ₁, v ₂,..., v _n_-1, v _n= v _b, v _iÎ V, i =1,..., n, такая что v ₁ Ev ₂ E... Ev _n_-1 Ev _n.

Рассмотрим способ нахождения транзитивного замыкания (тоже матрицы 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 }.