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

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х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 , состоит из таких элементов xi , для которых (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 (xi) = { xi } Г+1(xi) Г+2(xi) ... Г+p(xi).
Как видим, множество достижимых вершин R(xi)представляет собой прямое транзитивное замыкание вершины xi , т. е. R (xi) = T+(xi). Следовательно, для построения матрицы достижимости находим достижимые множества R (xi)для всех вершин xi X. Полагая, rij=1, если xj R (xi)и rij=0 в противном случае.

Рис. 4.1. Достижимость в графе: а –граф; б – матрица смежности; в – матрица достижимости; г- матрица контрдостижимости.
Для графа, приведенного на рис. 4.1,а, множества достижимостей находятся следующим образом:
R (х1) = { х1 } { х2, х5 } { х2, х4, х5 } { х2, х4, х5 } = = { х1, х2, х4, х5 },
R (х2) = { х2 } { х2, х4 } { х2, х4, х5 } { х2, х4, х5 } = = { х2, х4, х5 },
R (х3) = { х3 } { х4 } { х5 } { х5 } = { х3, х4, х5 },
R (х4) = { х4 } { х5 } { х5 } = { х4, х5 },
R (х5) = { х5 } { х5 } = { х5 },
R(х6)= {х6 } { х3, х7 } { х4, х6 } { х3, х5, х7 } { х4, х5, х6 } = { х3, х4, х5, х6, х7},
R (х7) = { х7 } { х4, х6 } { х3, х5, х7 } { х4, х5, х6 } = = { х3, х4, х5, х6, х7 }.
Матрица достижимости имеет вид, как показано на рис. 4.1,в. Матрицу достижимости можно построить по матрице смежности (рис. 4.1,б), формируя множества 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 (xi) = { xi } Г-1xi) Г-2xi) ... Г-pxi).
Таким образом, видно, что Q (xi)– это есть не что иное как обратное транзитивное замыкание вершины xi , т. е. Q (xi) = Т-xi). Из определений очевидно, что столбец xi матрицы Q (в котором qij=1, если xj Q (xi), и qij=0 в противном случае) совпадает со строкой xi матрицы R, т. е. Q = RT,где RT – матрица, транспонированная к матрице достижимости R.
Матрица контрдостижимости показана на рис. 4.1,г.
Следует отметить, что поскольку все элементы матриц R и Q равны 1 или 0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной точки зрения основными операциями являются быстродействующие логические операции.