Операции выполняются слева направо до тех пор, пока очередная операция объединения не перестанет изменять текущее множество Q (xi).

Из определений очевидро, что столбец Xi матрицы Q (в котором Qij - и если Xj g Q (xi), и gij = О в противном случае) совпадает со строкой Xi матрицы R, т. е. Q = где R - матрица, транспонированная к матрице достижимостей R.

2.1. Пример

Найти матрицы достижимостей и обратных достижимостей для графа G, приведенного на рис. 2.1. Матрица смежности графа

6 имеет вид

Рис. 2.1.

Множества достижимостей находятся с помощью соотношения (2.1):

В (Xt) = {Xt} и iX2, Xs} и {2, 4, Xs} и {Х2, Х4, 3-5} =

- Хг, Х4, Xs},

R (Хг) = {хг} и {хг, х^} U {х^, х^, х^) U {х^, х^, х^) =

/г (хз)={х,} и {Xi} и (2:5) и {хъ)= ={3:3.3:4.2:5},

Л(Х4) = {Х4}и{Х5}иМ =

={2:4.2:5},

л (а: ) = {2:5} и {2:5}-

={2:5},

/? (Хв) = {Хв} и {Хз, Х,} и {Х4, Хв} и {Хз, Х5, Х,} и {Х„ Х5, в}

= {Хъ, Х4, Х5, Хв, Х,}, /? (Х7) = {Х,} и {Х4, Хв} и {2:3, 2:5, Х,} и {Х4, Х5, Хв} =

= (Хз, Х4, Х5, Хв, Х7}

Следовательно, матрица достижимостей имеет вид

матрица обратных достижимостей такова:

Q = R =

Следует отметить, что поскольку все элементы матриц R и Q равны 1 или О, то каждую строку могкно хранить в двоичной форме, используя одно (или больше) машинных слов. Таким

образом, нахождение матриц R и Q с вычислительной точки зрения является довольно простой задачей, поскольку объединение множеств в соответствии с выражениями (2.1) и (2.2) и сравнение текущих множеств после каждого объединения, проводимое для выяснения необходимости продолжения процесса построения соответствующих множеств,- все это можно осуществить на ЭВМ с помощью одной логической операции

Так как R (х,) является множеством вершин, достижимых из Xi, а Q (xj) - множеством вершин, из которых можно достигнуть Xj, то к (xi) П Q (xj) - множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от Xi к Xj. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин Xi и Xj [7]. Все остальные вершины х, (х,) П Q {xj) называются несущественными или избыточными, поскольку их удаление не влияет на пути

от Xi к Xj.

Матрицы достижимостей и обратных достижимостей, определенные выше, являются полными в том смысле, что на длины путей от Xi к Xj пе накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и контрадостижимостей - надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти ограниченные матрицы тоже могут быть построены с помощью соотношений (2.1) и (2.2) - надо действовать точно так, как раньше, при нахождении неограниченных матриц, но только теперь р будет верхней границей длины допустимых путей.

Граф называют транзитивным, если из существования дуг (xi, Xj) и {xj, Xk) следует существование дуги (х х^). Транзитивным замыканием графа G = {X, А) является граф Gt = = {Х, A{jA), где А' является минимально возможным множеством дуг, необходимых для того, чтобы граф Gfc был транзитивным. Так как путь от х, к xj в графе G должен соответствовать дуге {xi, Xj) в Gfc, ТО совершенно очевидно, что матрица достижимостей R графа G почти полностью совпадает с матрицей смежности А графа Gfc - надо только в матрице А поставить на главной диагонали единицы.

3. Нахождение сильных компонент

Сильная компонента (СК) графа G была определена в предыдущей главе как максимальный сильно связный подграф графа G. Поскольку в сильно связном графе произвольная вершина Xj достижима из любой другой вершины Xi, то в ориентированном

1) В гл. 7, посвященной изучению деревьев, приводятся другие способы построения множеств R (ж;) и Q (ij). Эти способы базируются на процедуре расстановки пометок в вершинах графа (пометки ставят начиная с вершины xi).