Достижимость и обратная достижимость вершин графа

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

При исследовании и оптимизации дискретных систем на графовых моделях часто возникает вопрос, существует ли путь от вершины x_i к вершине x_j. Если такой путь существует, то говорят, что вершина x_j достижима из вершины x_i. В ряде случаев необходимо определить достижимость за конечное число шагов вершины x_j из вершины x_i, т. е. достижимость только на таких путях, длины которых не превосходят заданной величины.

Матрица достижимостей R[1,1] = {r_ij} и матрица обратных достижимостей Q[1,1] = {q_ij} определяется следующим образом:

r_{ij= {} 1, если вершина x_j достижима из x_i, (2.3).

0 в противном случае;

q_{ij= {} 1, если из вершины x_j можно достигнуть (2.4).

вершину x_i, 0 в противном случае.

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

Обозначим через 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.