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

В предыдущей главе для нахождения сильносвязных компонент орграфа 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.Алгоритм нахождения транзитивного замыкания

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

for k=1 to |V| do

for i=1 to |V| do

for j=1 to |V| do

a_ija_ija_ika_kj

Упражнения:

1. Заметим, что в алгоритме 2, основанном на выражении 5.1, элементы матрицыА^(k-1)непосредственно преобразуются в элементы матрицыА^(k), то есть не используется дополнительная память для хранения элементов матрицыА^(k-1). Докажите, что такая реализация выражения 5.1 корректна.

2. Очевидно, что трудоемкость алгоритма нахождения транзитивного замыкания O(|V|³). Представьте строки матрицыАв битовой форме и снизьте трудоемкость алгоритма до O(|V|²). Реализуйте оба варианта алгоритма и сравните время их работы.

3. Реализуйте алгоритм нахождения матрицы достижимости на основе использования стратегии поиска в глубину или ширину и сравните время работы этого алгоритма с временем работы алгоритма нахождения транзитивного замыкания.

4. Доработайте алгоритм нахождения транзитивного замыкания таким образом, чтобы в случае достижимости вершины jиз вершиныiсохранялась информация о пути, по которомуjдостижима изi.

Указание. Для хранения путей используйте матрицу Pразмераnn, гдеn– число вершин графа. Элементы матрицы можно определить одним из двух способов:

1) P_ij– вершина, предшествующая вершинеjна пути из вершиныiв вершинуj;

2) P_ij– вершина, следующая за вершинойiна пути из вершиныiв вершинуj.