Матрица достижимости

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х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-го порядка Г⁺¹(xi) является множеством таких вершин xj , которые достижимы из xi с использованием путей длины 1, то множество Г⁺(Г⁺¹(xi)) = Г⁺²(xi) состоит из вершин, достижимых из xi с использованием путей длины 2. Аналогично Г^+p(xi)является множеством вершин, которые достижимы из xi с помощью путей длины p.

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

R (xi) = { xi } Г⁺¹(xi) Г⁺²(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⁺x_i)для каждой вершины xi .