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

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

Если множество E дуг графа G рассматривать как бинарное отношение на множестве вершин V графа G, то R будет матрицей смежности для графа G*=(V,E*), в котором E* - транзитивное замыкание бинарного отношения E, т.е. vaE*vb, если существует цепочка va=v1,v2,...,vn-1,vn=vb, viÎV, i=1,...,n, такая что v1Ev2E...Evn-1Evn.

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

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

1) aij(0)=aij;

2) aij(k)=aij(k-1)Úaik(k-1)Ùakj(k-1) (5.1)

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

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

1. Для k=0 утверждение очевидно, так как aij(0)=aij, далее смотри определение матрицы смежности.

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

aij(t-1)Úait(t-1)Ùatj(t-1), равно единице тогда и только тогда, когда либо aij(t-1)=1, либо ait(t-1)=1 и atj(t-1)=1. Другими словами aij(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, следовательно, aij(t)=1 тогда и только тогда, когда существует путь из вершины i в вершину j с промежуточными вершинами, выбираемыми из множества {1,2,...,t}.

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

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

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

Алгоритм следует из выражения 5.1

for k=1 to |V| do

for i=1 to |V| do

for j=1 to |V| do

aijaijÚaikÙakj