Отношение достижимости. Орграфы и бинарные отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть V - множество вершин ориентированного графа F , Е - множество его рёбер. Каждое ребро e ÎE имеет начало v’ ÎV и конец v’’ ÎV . Таким образом, заданы два отображения j 1 и j 2 , где v’ =j 1 (e ) - начало ребра е , v’’ =j 2 (e ) - конец ребра е .

Можно дать несколько определений пути в орграфе F .

1. Путь из вершин и рёбер - это последовательность L (v 0 ,e 1 ,v 1 ,e 2 ,...,e n ,v n ), где v i - 1 =j 1 (e i ), v i =j 2 (e i ). Вершина v 0 называется началом пути L ,вершина v n - концом пути L , число n рёбер - его длиной . Путь, состоящий из одной вершины, имеет нулевую длину.

2. Путь из рёбер - это последовательность (e 1 ,e 2 ,...,e n ). Это понятие пути - аналог понятия маршрута в неориентированном графе.

3. Путь из вершин - это последовательность (v 0 ,v 1 ,...,v n ). Путь из вершин определён для графов, не содержащих кратных рёбер.

На практике можно пользоваться тем определением пути, которое окажется удобнее в данной конкретной задаче.

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

Пример . Путь (e 5 ,e 6 ,e 7 ,e 1 ,e 4 ,e 3) (рис. 3.11) - ор.цепь, а путь (e 7 ,e 1 ,e 4 ,e 3) - простая ор. цепь.

Рис. 3.11.

Путь называется ориентированным циклом (или просто циклом , когда рассматриваются только орграфы), если он состоит более чем из одного элемента и его начало совпадает с его концом. Как и для неориентированного графа, начало цикла обычно не фиксируется. Цикл называется простым , если каждая принадлежащая ему вершина инцидентна ровно двум его рёбрам.

Пример . Путь (e 1 ,e 4 ,e 3 ,e 2 ,e 5 ,e 6 ,e 7) - цикл, путь (e 5 ,e 6 ,e 7) - простой цикл.

В связи с ориентированными цепями справедлива теорема, которую доказал Redei при изучении квадратичных полей.

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

ÿ Доказательство проведем методом МИ. Обозначим количество вершин графа через n .

· n =2: дуга, соединяющая две вершины графа F 2 , и есть простая ориентированная цепь, проходящая через все вершины графа.

· Предположим, что при n = m для графа F m теорема верна.

· Докажем, что при n = m +1 для графа F m +1 теорема верна.

Построим граф F m +1 , добавив к графу F m некоторую вершину v m +1 , в которой имеются ребра ко всем вершинам v i (i =1,2,...,m ) из F m . По предположению, существует простая ориентированная цепь, проходящая через все вершины графа F m : P m =(v 1 ,v 2 ,...,v m ). Для ребер, инцидентных вершине v m +1, имеется три возможности.

1. Существует дуга (v m +1, v 1). Добавив ее к цепи P m “слева”, получим искомую цепь, проходящую через все вершины графа F m +1: P m +1 =( v m +1 ,v 1 ,v 2 ,...,v m ).

2. Существует дуга (v m , v m +1). Добавив ее к цепи P m “справа”, получим искомую цепь, проходящую через все вершины графа F m +1: P m +1 =( v m +1 ,v 1 ,v 2 ,..., v m ,v m +1).

3. Если в графе F m +1 нет ни дуги (v m +1 ,v 1), ни дуги (v m ,v m +1), то при некотором k (k =2,3,...,m -1) в нем обязательно найдутся дуги (v k ,v m +1) и (v m +1 ,v k +1). Составим цепь

P m +1 =(v 1 ,v 2 ,...,v k ,v m +1 ,v k +1 ,...,v m ).

Эта цепь проходит через все вершины графа F m +1 .

На множестве вершин V зададим отношение достижимости R D следующим образом: Вершина v’ ÎV находится в отношении R D с вершиной v’’ ÎV (в этом случае говорят, что вершина v’’ достижима из вершины v’ ), если существует путь L (v’ ,... ,v’’ ) с началом v’ и концом v’’ .

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

С помощью отношения достижимости определяется разбиение множества вершин орграфа на классы эквивалентности: вершины v’ , v’’ принадлежат одному классу, если отношение симметрично, т.е. v’’ достижима из v’ , а v’ достижима из v’’ .

Пусть L 1 (v’ , ... ,v’’ ) и L 2 (v’’ , ... ,v’ ) - соответствующие пути, связывающие эти вершины. Тогда вместе они образуют цикл, проходящий через вершины v’ и v’’ . Таким образом, любые вершины одного и того же класса эквивалентности принадлежат некоторому циклу. Если циклы в графе отсутствуют, то каждый класс эквивалентности состоит из одной вершины.

Рис. 3.13.

Минимальный граф F B , индуцирующий на множестве вершин V то же отношение достижимости, что и данный ориентированный граф F , т.е. граф с неуменьшаемым далее множеством рёбер, называется базисным графом для графа F .

Если существует базисный граф, то он не обязательно единственный. Так, для графа на рис. 3.13, любое радиальное ребро и ориентированный многоугольный цикл определяют базисный граф.

Если F - конечный орграф, то базисные графы существуют; они могут быть получены при последовательном удалении “излишних” рёбер (v 0 ,v n ), для которых найдётся не содержащая ребра (v 0 ,v n ) ориентированная цепь Р (v 0 ,v n ).

Пусть G = (X , Г) - граф модульной структуры, х г, х-. - вершины, принадлежащие X. Если в графе G существует ориентированная цепь от х, к Хр то вершина х,- - достижима из вершины х,-. Справедливо следующее утверждение: если вершина Xj достижима из х, ах (- из Хр то X/ достижима из х^ Доказательство этого факта очевидно. Рассмотрим бинарное отношение на множестве X, которое определяет достижимость между вершинами графа. Введем обозначение х, -> х, для достижимости вершины х,- из Xj. Отношение транзитивно. Обозначим через Я(х,) множество вершин графа G, достижимых из х; . Тогда равенство

определяет транзитивное замыкание х, по отношению к достижимости.

Докажем следующую теорему.

Теорема 1.1. Для выбранного компонента связности графа модульной структуры любая вершина достижима из корневой, соответствующей данному компоненту, т.е. выполняется равенство (х/- корневая вершина)

Доказательство. Предположим, вершинах, (х,е X) недостижима из Xj. Тогда х, ё X/ и множество X" = X х), непусто. Поскольку выбранный компонент графа связанный, то существуют вершина х,- е х, и цепь /7(х; , xj), ведущая от х, к х,-. Исходя из ацикличности графа G, в X" должна существовать простая цепь Н(х/, xj), где в вершину x f не входят дуги (данная цепь может быть пустой, если X" состоит только из х,). Рассмотрим цепь Я(х/, xj) = Н (х/, х,) U Я (х, xj). Это означает, что модуль х. достижим из вершин х, и Xj и обе вершины не содержат входящих дуг. А это противоречит определению графа модульной структуры с единственной корневой вершиной. Теорема доказана.

Основное требование для обеспечение достижимости - это отсутствие неориентированных циклов в графе. Исходя из графа на рис. 1.4, отмечаем, что граф содержит ориентированный цикл и модули, соответствующие вершинам х 4 , х 5 , ж 6 , никогда выполняться не будут. Таким образом, результаты теоремы 1.1 усиливают требование отсутствия ориентированных циклов в графе модулей.

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

Коэффициент а,у= 1, если модуль, соответствующий индексу /, достижим из модуля, соответствующего индексу i. Следующие результаты основаны на известной теореме из теории графов.

Рис. 1.4.

Теорема 1.2. Коэффициент ту l-й степени матрицы смежности Доопределяет количество различных маршрутов, содержащих / дуг и связывающих вершину X/ с вершиной ^-ориентированного графа.

Рассмотрим следующие три следствия из этой теоремы .

Следствие 1.1. Матрица М = "? J M t , где М - матрица смежности ориен-

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

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

я, определяет количество всех возможных путей в графе с количеством дуг п. Пусть коэффициент т 1} матрицы М отличен от нуля. Это означает, что существует степень матрицы М>, у которой соответствующий коэффициент т {} также отличен от нуля. Следовательно, существует путь, идущий от вершины Xj к Хр т.е. вершина ^ достижима из х г Данное следствие определяет связь матрицы вызовов графа модульной структуры, совпадающей с матрицей смежности А/, с матрицей достижимости А и определяет алгоритм построения последней.

Следствие 1.2. Пусть для некоторого i в последовательности степеней матрицы смежности М* существует коэффициент т Х1 > 0. Тогда в исходном графе существует ориентированный цикл.

Доказательство. Пусть m (i > 0 для некоторого I. Следовательно, Xj достижима из x v т.е. существует цикл. Согласно теореме 1.2 данный цикл имеет / дуг (в общем случае повторяющихся).

Следствие 1.3. Пусть п-я степень матрицы смежности М п ациклического графа совпадает с нулевой матрицей (все коэффициенты равны нулю).

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

Для ациклических графов отношение достижимости эквивалентно частичному строгому порядку. Транзитивность отношения достижимости рассмотрена выше. Антисимметричность следует из отсутствия ориентированных циклов: если вершина х } достижима из x v то обратное неверно. Введем обозначение х х > Хр если вершина Xj достижима из вершины x v

Пусть G = (X, Г) - ациклический граф, соответствующий некоторой модульной структуре. Рассмотрим убывающую цепь элементов частично упорядоченного множества X:

где через знак «>» обозначено отношение достижимости. Поскольку X конечно, то цепь обрывается х п > x i2 > ... > x in . Вершина x jn не имеет исходящих дуг, т.е. элемент x in минимальный (ему соответствует модуль, который не содержит обращения к другим модулям). Максимальный элемент во множестве X - корневая вершина.

• Доказательство этой теоремы приводится в работе (книга): Лаврищева Е. М., Грищенко В. Н. Сборочное программирование. Киев: Наукова думка, 1991. 287 с.

Задач, в которых используется понятие достижимости , довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х 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 , в противном случае.

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

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

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

Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лицах 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 .