![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Матрица достижимостиЗадач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х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 Рис. 4.1. Достижимость в графе: а –граф; б – матрица смежности; в – матрица достижимости; г- матрица контрдостижимости.
Для графа, приведенного на рис. 4.1,а, множества достижимостей находятся следующим образом:
R (х1) = { х1 }
R (х2) = { х2 }
R (х3) = { х3 }
R (х4) = { х4 }
R (х5) = { х5 }
R (х6) = { х6 }
R (х7) = { х7 }
Матрица достижимости имеет вид, как показано на рис. 4.1,в. Матрицу достижимости можно построить по матрице смежности (рис. 4.1,б), формируя множества T+xi)для каждой вершины xi .
|