Достижимость в графах

Достижимость и контрдостижимость

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица хi быть передана другому лицу хj, т. е. существует ли путь, идущий от вершины хi к вершине хj. Если такой путь существует, то говорят, что вершина хj достижима из вершины хi. Можно интересоваться достижимостью вершины хj из вершины хi только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. п. задачи.

Достижимость в графе описывается матрицей достижимости R=[rij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

rij=1, если вершина хj достижима из хi,

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

Множество вершин R(xi) графа G, достижимых из заданной вершины xi, состоит из таких элементов xj, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г+1(xi) является множеством таких вершин xj, которые достижимы из xi с использованием путей длины 1, то множество Г+(Г+1(xi)) = Г+2(xi) состоит из вершин, достижимых из xi с использованием путей длины 2. Аналогично Г+p(xi) является множеством вершин, которые достижимы из xi с помощью путей длины p.

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

$$R (x_{i}) = \{ x_{i} \} \cup Г^{+1}(x_{i}) \cup Г^{+2}(x_{i}) \cup \dots \cup Г^{+p}(x_{i})$$.

Как видим, множество достижимых вершин R(xi) представляет собой прямое транзитивное замыкание вершины xi, т. е. R (xi) = T+(xi). Следовательно, для построения матрицы достижимости находим достижимые множества R (xi) для всех вершин $$x_{i}\in X$$. Полагая, rij=1, если $$x_{j} \in R (x_{i})$$ и rij=0 в противном случае.

Для графа, приведенного на ,а, множества достижимостей находятся следующим образом:

$$R (х_{1}) = \{ х_{1} \} \cup \{ х_{2}, х_{5} \} \cup \{ х_{2}, х_{4}, х_{5} \} \cup \{ х_{2}, х_{4}, х_{5} \} = = \{ х_{1}, х_{2}, х_{4}, х_{5} \}$$,

$$R (х_{2}) = \{ х_{2} \} \cup \{ х_{2}, х_{4} \} \cup \{ х_{2}, х_{4}, х_{5} \} \cup \{ х_{2}, х_{4}, х_{5} \} = = \{ х_{2}, х_{4}, х_{5} \}$$,

$$R (х_{3}) = \{ х_{3} \} \cup \{ х_{4} \} \cup \{ х_{5} \} \cup \{ х_{5} \} = \{ х_{3}, х_{4}, х_{5} \}$$,

$$R (х_{4}) = \{ х_{4} \} \cup \{ х_{5} \} \cup \{ х_{5} \} = \{ х_{4}, х_{5} \}$$,

$$R (х_{5}) = \{ х_{5} \} \cup \{ х_{5} \} = \{ х_{5} \}$$,

$$R (х_{6}) = \{ х_{6} \} \cup \{ х_{3}, х_{7} \} \cup \{ х_{4}, х_{6} \} \cup \{ х_{3}, х_{5}, х_{7} \} \cup \cup \{ х_{4}, х_{5}, х_{6} \} = \{ х_{3}, х_{4}, х_{5}, х_{6}, х_{7}\}$$,

$$R (х_{7}) = \{ х_{7} \} \cup \{ х_{4}, х_{6} \} \cup \{ х_{3}, х_{5}, х_{7} \} \cup \{ х_{4}, х_{5}, х_{6} \} = = \{ х_{3}, х_{4}, х_{5}, х_{6}, х_{7} \}$$.

Матрица достижимости имеет вид, как показано на ,в. Матрицу достижимости можно построить по матрице смежности (,б), формируя множества T+(xi) для каждой вершины xi .

Матрица контрдостижимости Q = [ qij], i, j =1, 2, ... n, где n – число вершин графа, определяется следующим образом:

qij=1, если из вершины xj можно достичь вершину xi ,

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

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

$$Q (x_{i}) = \{ x_{i} \} \cup Г^{-1}(x_{i}) \cup Г^{-2}(x_{i}) \cup \dots \cup Г^{-p}(x_{i})$$.

Таким образом, видно, что Q (xi) – это есть не что иное как обратное транзитивное замыкание вершины xi , т. е. Q (xi) = Т-xi). Из определений очевидно, что столбец xi матрицы Q (в котором qij=1, если $$x_{j} \in Q (x_{i})$$, и qij=0 в противном случае) совпадает со строкой xi матрицы R, т. е. Q = RT,где RT – матрица, транспонированная к матрице достижимости R.

Матрица контрдостижимости показана на ,г.

Следует отметить, что поскольку все элементы матриц R и Q равны 1 или 0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной точки зрения основными операциями являются быстродействующие логические операции.

Нахождение множества вершин, входящих в путь

Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество вершин, в которые есть пути из вершины xi, а T–(хj) – множество вершин, из которых есть пути в xj, то $$T^{+}(x_{i}) \cap T^{–}(x_{j})$$ – множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от xi к xj. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин xi и xj. Все остальные вершины графа называются несущественными или избыточными, поскольку их удаление не влияет на пути от xi к xj.

Так для графа на нахождение вершин, входящих в путь, например из вершины х2 в вершину х4, сводится к нахождению $$Т^{+}( х_{2}) =\{ х_{2}, x_{3}, х_{4}, х_{5}, х_{6}\} , Т^{-}( х_{4}) =\{ х_{1}, х_{2}, x_{3}, х_{4}, х_{5}\} , \ и \ их \ пересечения \ T^{+}(х_{2}) \cap T^{–}(х_{4}) =\{ х_{2}, x_{3}, х_{4}, х_{5}\}$$.

Матричный метод нахождения путей в графах

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А2 определяется по формуле

$$a^{(2)}_{ik}= \sum ^{n}_{j=1}a_{ij}a_{jk}$$

Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа aij и ajk равны 1, в противном случае оно равно 0. Поскольку из равенства aij = ajk = 1 следует существование пути длины 2 из вершины xi в вершину хk , проходящего через вершину xj , то ( i -й, k -й) элемент матрицы А2 равен числу путей длины 2, идущих из xi в хk .

На таблице 4.1a представлена матрица смежности графа, изображенного на . Результат возведения матрицы смежности в квадрат А2 показан на таблице 4.1б.

Так "1", стоящая на пересечении второй строки и четвертого столбца, говорит о существовании одного пути длиной 2 из вершины х2 к вершине х4 . Действительно, как видим в графе на , существует такой путь: a6, a5 . "2" в матрице A2 говорит о существовании двух путей длиной 2 от вершины х3 к вершине х6 : a8, a4 и a10, a3 .

Аналогично для матрицы смежности, возведенной в третью степень ), a (3) ik равно числу путей длиной 3, идущих от xi к хk . Из четвертой строки матрицы A3 видно, что пути длиной 3 существуют: один из х4 в х4(a9, a8, a5), один из х4 в х5(a9, a10, a6) и два пути из х4 в х6(a9, a10, a3 и ).

Таким образом, если a р ik является элементом матрицы Aр ,то a р ik равно числу путей (не обязательно орцепей или простых орцепей) длины р, идущих от xi к хk .