Определение матриц достижимостей и обратных достижимостей с помощью прямых и обратных отображений

Обозначим через RM(x_i) множество вершин графа, достижимых из заданной вершины x_i. Это множество состоит из таких элементов x_j, для которых элемент r_ij (2.3) в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице достижимостей R равны 1, поскольку каждая вершина достижима из себя самой с помощью пути длиной 0.

Поскольку отображение Г(x_i), описанное в п.2.1.2, является множеством таких вершин x_j, которые достижимы из x_i с использованием дуг длиной 1 [т.е. Г(x_i) – такое множество вершин, для которых в графе существуют дуги (x_i,,x_j)], то Г(Г(x_i)) = Г²(x_i) состоит из вершин, достижимых из x_i с использованием путей длиной 2. Аналогично Г^р(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длиной Р.

Так как любая вершина графа, которая достижима из x_i, должна быть достижима с использованием пути (или путей) длиной 0, или 1, или 2,…,

или Р (с некоторым конечным, но, возможно, достаточно большим значением Р), то множество вершин, достижимых из x_i, можно представить в виде

RM(x_i) = {x_i}È Г(x_i) È Г²(x_i) È Г^р(x_i). (2.5)

Таким образом, множество RM(x_i) может быть получено последовательным выполнением (слева направо) операций объединения в соотношении (2.5) до тех пор, пока «текущее» множество не перестанет увеличиваться по размеру при очередной операции объединения. С этого момента последующие операции не будут давать новых членов множеству, и, таким образом, будет образовано достижимое множество RM(x_i). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число Р меньше числа вершин в графе.

Имея RM(x_i) для всех вершин графа, можно построить матрицу достижимостей R так. Положим r_ij = 1, если x_j Î R(x_i) и r_ij = 0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

Для построения матрицы обратных достижимостей применим обратные отображения (п.2.1.3). Обозначим через QM(x_i) множество таких вершин графа, что из любой вершины этого множества можно достигнуть вершины x_i.

Аналогично построению достижимого множества RM(x_i) на основе соотношения (2.5) можно «сформировать» множество QM(x_i), используя следующее выражение:

QM(x_i) = {x_i} È Г^-1(x_i) È Г^-2(x_i) È … È Г^-р(x_i), (2.6)

где Г^-2(x_i) = Г^-1(Г^-1(x_i) и т.д.

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

Имея QM(x_i) для всех вершин графа, можно построить матрицу обратных достижимостей Q. Положим q_ij = 1, если x_j Î QM(x_i) и q_ij = 0 в противном случае.

Из определений матриц R и Q очевидно, что столбец x_i матрицы Q совпадает со строкой x_i матрицы R, т.е. Q = R^T.