Отношение достижимости модулей графов. Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности Нахождение множества вершин, входящих в путь

Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения

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

Задач, в которых используется понятие достижимости , довольно много.

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

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

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

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

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

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

R (x i) = { x i } Г +1 (x i) Г +2 (x i) ...Г +p (x i).

Как видим, множество достижимых вершин R(x i)представляет собой прямое транзитивное замыкание вершиныx i , т. е.R(x i) = T + (x i). Следовательно, для построения матрицы достижимости находим достижимые множестваR(x i)для всех вершинx i X. Полагая,r ij =1, еслиx j R(x i)иr ij =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)для каждой вершиныx i .

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

q ij =1, если из вершиныx j можно достичь вершинуx i ,

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

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

Q (x i) = { x i } Г -1 (x i) Г - 2(x i) ...Г -p (x i).

Таким образом, видно, что Q (x i)– это есть не что иное как обратное транзитивное замыкание вершиныx i , т. е.Q (x i) = Т - (x i). Из определений очевидно, что столбец x i матрицыQ(в которомq ij =1, еслиx j Q (x i), иq ij =0в противном случае) совпадает со строкойx i матрицыR, т. е.Q = R T ,гдеR T – матрица, транспонированная кматрице достижимости R.

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

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

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

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

Рис. 4.2. Орграф

Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из вершины х 2 в вершинух 4 , сводится к нахождениюТ + (х 2) ={ х 2 , х 3 , х 4 , х 5 , х 6 },

Т - (х 4) ={ х 1 , х 2 , х 3 , х 4 , х 5 }, и их пересеченияT + (х 2) T – (х 4) ={ х 2 , х 3 , х 4 , х 5 }.

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

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

a (2) ik = n j=1 a ij a jk

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

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

Так "1", стоящая на пересечении второй строки и четвертого столбца, говорит о существовании одного пути длиной 2 из вершины х 2 к вершинех 4 . Действительно, как видим вграфе на рис. 4.2, существует такой путь:a 6 , a 5 . "2" в матрицеA 2 говорит о существовании двух путей длиной 2 от вершиных 3 к вершинех 6:a 8 , a 4 иa 10 , a 3 .

Аналогично для матрицы смежности, возведенной в третью степень A 3 (таблица 4.1в),a (3) ik равно числу путей длиной 3, идущих отx i кх k . Из четвертой строки матрицыA 3 видно, что пути длиной 3 существуют: один изх 4 вх 4 (a 9 , a 8 , a 5), один изх 4 в

х 5 (a 9 , a 10 , a 6)и два пути изх 4 вх 6 (a 9 , a 10 , a 3 и a 9 , a 8 , a 4). МатрицаA 4 показывает существование путей длиной 4 (таблица 4.1г).

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

По аналогии с графом достижимости определим граф сильной достижимости.

Определение: Пусть– ориентированный граф.Граф сильной достижимости
дляимеет тоже множество вершини следующее множество рёбер
в графевершиныивзаимно достижимы.

По матрице графа достижимости
легко построить матрицу
графа сильной достижимости. Действительно из определений достижимости и сильной достижимости непосредственно следует, то для всех пар
,
, значение элемента
равно 1 тогда и только тогда, когда оба элемента
и
равны 1, т.е.

По матрице
можно выделить компоненты сильной связности графаследующим образом:

Повторяем второй шаг до тех пор, пока все вершины не будут распределены по компонентам.

В нашем примере для графа примера 14.1. по матрице
получаем следующую матрицу графа сильной достижимости

Используя описанную выше процедуру, находим, что вершины графа разбиваются на 4 компоненты сильной связности:
,
,
,
. На множестве компонент сильной связности также определим отношение достижимости.

Определение: Пусть
и
– компоненты сильной связности графа. Компонента
достижима из компоненты
, если
или существуют такие две вершины
и
, чтодостижима из.
строго достижима из
, если
и
достижима из
. Компонента
называется минимальной, если она не является строго достижимой ни из какой компоненты.

Так как все вершины в одной компоненте взаимно достижимы, то нетрудно понять, что отношения достижимости и строгой достижимости на компонентах не зависят от выбора вершин
и
.

Из определения легко выводится следующая характеристика строгой достижимости.

Лемма: Отношение строгой достижимости является отношением частичного порядка, т.е. оно антирефлексивно, антисимметрично и транзитивно.

Это отношение можно представлять в виде ориентированного графа, вершинами которого являются компоненты, а ребро
означает, что
строго достижима из
. Ниже показан граф компонент для графа примера 14.1.

В данном случае имеется одна минимальная компонента
.

Во многих приложениях ориентированный граф представляет собой сеть распространения некоторого ресурса: продукта, товара, информации и т.п. В таких случаях естественно возникает задача поиска минимального числа таких точек (вершин), из которых этот ресурс может быть доставлен в любую точку сети.

Определение: Пусть
- ориентированный граф. Подмножество вершин
называетсяпорождающим , если из вершин
можно достичь любую вершину графа. Подмножество вершин
называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является.

Следующая теорема позволяет эффективно находить все базы графа.

Теорема: Пусть
- ориентированный граф. Подмножество вершин
является базой тогда и только тогда, когда содержит по одной вершине из каждой минимальной компоненты сильной связности и не содержит никаких других вершин.

Доказательство: заметим вначале, что каждая вершина графа достижима из вершины, принадлежащей некоторой минимальной компоненте. Поэтому множество вершин
, содержащих по одной вершине из каждой минимальной компоненты, является порождающим, а при удалении из него любой вершины перестаёт быть таковым, так как вершины из соответствующей минимальной компоненты становятся недостижимы. Поэтому
является базой.

Обратно, если
является базой, то оно обязано включать хотя бы по одной вершине из каждой минимальной компоненты, иначе вершины такой минимальной компоненты окажутся недоступны. Никаких других вершин
содержать не может, так как каждая из них достижима из уже включённых вершин.

Из этой теоремы вытекает следующая процедура построения одной или перечисления всех баз графа :

Пример 14.3: Определим все базы ориентированного графа .

На первом этапе находим компоненты сильной связности :

На втором этапе строим граф строгой достижимости на этих компонентах.

Определяем минимальные компоненты:
,
и
.

Наконец перечисляем все четыре базы :
,
,
и
.

G(V,X) с петлями, но без кратных дуг задает бинарное отношение Х на множестве V. Полный граф соответствует универсальному соотношению. Неориентированный граф соответствует симметричному соотношению. Дополнение графа соответствует дополнению отношения. Изменение направления дуг соответствует обратному отношению.

Орграфы и бинарные отношения один и тот же класс объектов, описанных разными средствами. Бинарные отношения, функции являются базовыми средствами для построения подавляющего большинства математических моделей, использующих для решения практических задач, а графы допускают наглядное представление в виде диаграммы. Это объясняет широко использование диаграмм различного типа в кодировании и проектировании.

Вершина b орграфа (графа) G называется достижимой из U в том и только том случае, когда U=V или существует путь (маршрут) соединяющий U с V (U – начальная вершина, V – конечная вершина). Таким образом на множестве вершин орграфа (графа) определено не только отношение смежности А, но и отношение достижимости Т.

Матрицей достижимости Т орграфа(графа) G называется T 2 n×n, элементы которой находятся из условия: 1, если достижимо из ; 0, если не достижимо из .

Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.

Введенное отношение достижимости на вершинах графа G(V,Х): вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, достижимость является рефлексивным и транзитивным замыканием отношения смежности.

Найти матрицу смежности, транзитивное и рефлексивное замыкание.

Связность в графах. Слабая, односторонняя и сильная связность в орграфах. Матрица связности и сильной связности. Компоненты связности. Определение матрицы сильной связности на основе матрицы достижимости.

G(V,Х) называется связным , если любая его вершина достижима из любой другой вершины.

Орграф G(V,Х) называется односторонне связным , если для любых двух его вершин, покрайней мене одна достижима из другой.

Орграф G(V,Х) называется сильно связным , если любая его вершина достижима из любой другой.

Орграф G(V,Х) называется слабо связным , если связным является соответствующий ему не орграф, полученный в результате удаления ориентации дуг.

Орграф, не являющийся слабо связным, называется несвязным .

Компонентой сильнодействующей связи орграфа G(V,Х) называется максимальное, по числу вхождения вершин сильносвязный подграф данного орграфа. Аналогично определяется компонента связности не орграфа.

Матрицей сильной связности (связности) орграфа (графа) G(V,Х) называется S n×n, элементы которой находятся из условия: 1, если достижимо из и достижимо из ; 0, если не достижимо из и не достижимо из .

(орграф) сильносвязным или связным, для этого достаточно определить наличие 0 в матрице, если

0 нет, то граф (орграф) является связным (сильносвязным) в противном случае нет.

Матрица сильной связности может быть построена из матрицы достижимости по формуле

ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФАХ План лекции: Маршруты цепи и циклы. Связность графа и компоненты связности. Диаметр радиус и центр графа.

Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 8. Достижимость и связность в графах

Лекция 8. ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФАХ

План лекции:

1. Маршруты, цепи и циклы.
2. Связность графа и компоненты связности.
3. Диаметр, радиус и центр графа.
4. Матрицы достижимости и контрадостижимости.

1. Маршруты, цепи и циклы

Ориентированным маршрутом (или путем ) орграфа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. На рис. 1 последовательности дуг

, (1)

, (2)

(3)

являются путями.

Рис. 1.

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

Простой называется орцепь, в которой каждая вершина используется не более одн о го раза. Например, орцепь (3) является простой, а орцепь (2) – нет.

Маршрут есть неориентированный двойник пути, т. е. последовательность ребер, в которой каждое ребро, за исключением первого и последнего, связано концевыми вершинами с ребрами и. Черта над символом дуги означает, что ее рассматривают как ребро.

Аналогично тому, как мы определили орцепи и простые цепи, можно определить цепи и простые цепи.

Путь или маршрут можно изображать также последовательностью вершин. Напр и мер, путь (1) можно записать в виде: .

Путь называется замкнутым , если в нем начальная вершина дуги совпадает с коне ч ной вершиной дуги. Замкнутые орцепи (цепи) называются орциклами (циклами ). Орциклы называют также контурами . Замкнутые простые орцепи (цепи) наз ы ваются простыми орциклами (циклами ). Замкнутый маршрут является неориентирова н ным двойником замкнутого п у ти.

1. Связность графа и компоненты связности

Говорят, что вершина в орграфе достижима из вершины, если существует путь. Если при этом достижима из, то об этих вершинах говорят, что они взаимно достижимы.

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

° ° °

° ° ° ° ° °

° ° ° ° ° °

а б в

Рис. 2.

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

Орграф называется слабо связным или слабым , если в нем любые две вершины с о единены полупутем . Полупуть, в отличие от пути, может иметь противоположно напра в ленные дуги. Пример слабого орграфа приведен на рис. 2 в. Очевидно, что в графе нет п у ти между вершинами и, но существует полупуть, состоящий из противоположно н а правленных дуг и.

Если для некоторой пары вершин не существует маршрута, соединяющего их, то т а кой орграф называется несвязным .

Для орграфа определены три типа компонент связности: сильная компонента – ма к симально сильный подграф, односторонняя компонента – максимальный одност о ронний подграф и слабая компонента – максимально слабый подграф.

Понятие сильной компоненты иллюстрирует рис. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Рис. 3

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

Для неориентированного графа определим на множестве его вершин бина р ное отношение, полагая, если имеется цепь, связывающая с. Это отношение обл а дает свойствами рефлексивности, симметричности и транзитивности, то есть является о т ношением эквивалентности. Оно разбивает множество вершин на непересекающиеся классы: . Две вершины из одного класса эквивалентны, то есть в графе имеется цепь, соединяющая их, для вершин из разных классов такой цепи нет. Так как концы л ю бого ребра находятся в отношении, то множество ребер графа также разобьется на непересекающиеся классы: , где через обозначено множество всех ребер, концы которых принадлежат, .

Графы являются связными и в сумме дают граф. Эти графы называются компонентами связности графа. Число – еще одна числовая характеристика графа. Для связного графа, если граф несвязный, то.

Если данный граф не является связным и распадается на несколько компонент, то решение какого-либо вопроса относительно этого графа, как правило, можно свести к изучению отдельных компонент, которые связны. Поэтому в большинстве случаев имеет смысл предполагать, что заданный граф связный.

1. Диаметр, радиус и центр графа

Для связного графа определим расстояние между двумя его вершинами и как длину самой короткой цепи, соединяющей эти вершины, и обозначим через. Длина цепи – это количество ребер, составляющих цепь. Нетрудно проверить, что введе н ное расстояние удовлетворяет аксиомам метрики:

2) ;

3) .

Определим расстояние от каждой вершины графа до самой далекой от нее вершины

которое называется эксцентриситетом . Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – .

Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа. В полном графе имеем, а в простом цикле – .

Вершина называется центральной, если. Граф может иметь нескол ь ко таких вершин, а в некоторых графах все вершины являются центральными. В простой цепи при нечетном числе вершин только одна является центральной, а при четном их чи с ле таких вершин две. В полном графе и для простого цикла центральными являются все вершины. Множество центральных вершин называется центром графа.

Пример 1. Найти диаметр, радиус и центр графа, приведенного на рис. 4.

° °

° ° °

° °

° °

Рис. 4.

Для решения этой задачи удобно предварительно вычислить матрицу расстояний между вершин а ми графа. В данном случае это будет матрица размером, в которой на месте стоит расстояние от вершины до вершины:

Для каждой строки матрицы находим наибольший элемент и записываем его спр а ва от черточки. Наибольшее из этих чисел равно диаметру графа, наименьшее – р а диусу графа. Центр графа составляют центральные вершины и.

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

1. Матрицы достижимостей и контрадостижимостей

Матрица достижимостей определяется следующим образом:

Множество вершин графа, достижимых из заданной вершины, состоит из таких элементов, для которых -й элемент в матрице равен 1. Это множество можно представить в виде

Матрица контрадостижимостей (обратных достижимостей ) определ я ется следующим образом:

Аналогично построению достижимого множества можно сформировать мн о жество, используя следующее выражение:

Из определений следует, что -й столбец матрицы совпадает с -й строкой ма т рицы, т. е. , где – матрица, транспонированная к матрице.

Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, пр и веденного на рис. 5.

Рис. 5.

Определим множества достижимостей для вершин графа:

Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:

Так как – множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от к, то вершины этого множества назыв а ются существенными или неотъемлемыми относительно концевых вершин и. Все остальные вершины называются несущественными или избыточными , поскольку их удаление не влияет на пути от к.

Можно определить также матрицы ограниченных достижимостей и контрдостиж и мостей, если потребовать, чтобы длины путей не превышали некоторого заданного числа. Тогда будет верхней границей длины допустимых путей.

Граф называют транзитивным , если из существования дуг и след у ет существование дуги. Транзитивным замыканием графа является граф, где – минимально возможное множество дуг, необходимых для того, чтобы граф был транзитивным. Очевидно, что матрица достижимостей графа совпадает с матрицей смежности графа, если в матрице на главной диагонали поставить единицы.

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

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

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

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

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

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

Как видим, множество достижимых вершин R(x i) представляет собой прямое транзитивное замыкание вершины x i , т. е. R (x i) = T + (x i) . Следовательно, для построения матрицы достижимости находим достижимые множества R (x i) для всех вершин . Полагая, r ij =1 , если и r ij =0 в противном случае.

Рис. 4.1.

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

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

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

q ij =1 , если из вершины x j можно достичь вершину x i ,

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