2. Матрицы достижимостей и контрдостижимостей

Матрица достижимостей R = [r_ij] определяется следующим образом:

Множество вершин R(x_i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых в матрице достижимостей равно 1.

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

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

R(x_i)={x_i}ÈГ(x_i)ÈГ²(x_i)È…ÈГ^p(x_i). (1.1)

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

Матрицу достижимостей можно построить следующим образом. Находим достижимые множества R(x_i) для всех вершин x_i Î X способом, приведенным выше. Положим r_ij=1, если х_j Î R(x_i), и r_ij=0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

Матрица контрдостижимостей Q = [q_ij] определяется следующим образом:

Контрдостижимым множеством Q(x_i) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершины x_i. Аналогично построению достижимого множества R(x_i) на основе соотношения (1.1) можно сформировать множество Q(x_i), используя следующее выражение:

Q(x_i) = {x_i}ÈГ^-1(x_i)ÈГ^-2(x_i)È…ÈГ^-p(x_i), (1.2)

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

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

Следует заметить, что столбец x_i матрицы Q совпадет со строкой x_i матрицы R, т. е. Q = R^T, где R^T – матрица, экспонированная к матрице достижимостей R.

Пример

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

Рис.

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

R(x₁)={x₁}È{x₁} ={x₁}

R(x₂)={x₂}È{x₃}È{x₁, x₄, x₇}È{x₂, x₄}È{x₁}={x₁, x₂, x₃, x₄, x₇}

R(x₃)={x₃}È{x₁, x₄, x₇}È{x₁, x₂}È{x₁, x₃}={x₁, x₂, x₃, x₄, x₇}

R(x₄)={x₄}={x₄}

R(x₅)={x₅}È{x₄}={x₄, x₅}

R(x₆)={x₆}È{x₅}È{x₄}={x₄, x₅, x₆}

R(x₇)={x₇}È{x₁, x₂}È{x₁, x₃}È{x₁, x₄, x₇}È{x₁, x₂}={x₁, x₂, x₃, x₄, x₇}

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

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

Так как R(x_i) является множеством вершин, достижимых из x_i, a Q(x_j) - множеством вершин, из которых можно достигнуть x_j, то R(х_i)ÇQ(x_j) - множество таких вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от х_i к х_j.

Матрицы достижимостей и обратных достижимостей, определенные выше, являются полными в том смысле, что на длины путей от х_i к х_j не накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и контрдостижимостей – надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти ограниченные матрицы тоже могут быть построены с помощью соотношений (1.1) и (1.2) – надо действовать точно так, как раньше, при нахождении неограниченных матриц, но только теперь р будет верхней границей длины допустимых путей.