Матрицы смежности и инцидентности

Любой ориентированный граф с вершинами v 1, v 2, …, vn и дугами a 1, a 2, …, am можно задать его матрицей инцидентности B =(bij), i = 1,2,…, n, j = 1,2,…, m, размера n  m, в которой bij = 1, если дуга aj исходит из вершины vi; bij = –1, если дуга aj заходит в вершину vi; bij = 0, если дуга aj не инцидентна вершине vi.

Матрицу инцидентности можно использовать и для задания неориентированного графа. В этом случае bij = 1, если дуга aj инцидентна вершине vi, и bij = 0, если дуга aj не инцидентна вершине vi. Например, граф на рис. 2 (с. 107) можно задать следующей матрицей инцидентности (дуги упорядочены в алфавитном порядке):

 1 1



0 0 −1



 −1 0 1

0 0 

B   0



 0

0 −1 1

−1 0 −1

0 .



0 

Графы без параллельных дуг удобно представлять при помощи матриц смежности. Для графа с n вершинами матрица смежности – это квадратная матрица A =(aij) порядка n, состоящая из нулей и единиц. Элемент aij равен 1, если имеется дуга, соединяющая вершины i и j, и равен 0 в противном случае. Впрочем, если в графе имеются параллельные дуги, то и тогда можно использовать матрицу смежности: можно полагать aij равным числу дуг, соединяющих вершины i и j.

Матрица смежности неориентированного графа симметрична. Например, матрицей смежности графа,

представленного на рис. 7.

служит матрица

Рис. 7

1 

 

0 

 

0 

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

верхней вершины, мы получим матрицу смежности

 1 1



A ′   1 0

 0 1



 1 1

0 1 



1 1 

0 1 .



1 0 

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

Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например, следующая матрица является матрицей смежности ориентированного графа на

рис. 2 (с. 107):

 0 1



A   0 0

 1 0



 0 0

0 1 



1 0 

0 1 .



0 0 

Теорема. Пусть G – ориентированный граф с вершинами 1,

2, …, n, и A = (aij) – его матрица смежности. Тогда элемент aij(k) матрицы Ak равен числу путей длины k из вершины i в вершину j.

aij (k +1) = ai 1(k)⋅ a 1 j + ai 2(k)⋅ a 2 j +…+ ain (k)⋅ anj. (1) Слагаемое ai 1(k)⋅ a 1 j равно числу путей из i в j длины k +1, в которых вершина 1 предпоследняя: пути длины k из вершины i в вершину 1 комбинируются с дугами из вершины 1 в вершину

j. Аналогично слагаемое ai 2(k)⋅ a 2 j равно числу путей из i в j длины k +1, в которых вершина 2 предпоследняя, и т. д. Каждый путь из i в j длины k +1 получается из некоторого пути длины k, начинающегося в вершине i, присоединением к нему некоторой дуги, заканчивающейся в вершине j. Поэтому сумма в правой части равенства (1) равна числу путей из i в j длины k +1.

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

1 2

Матрица смежности:

Рис. 8

0 0 2 

 

дает число путей длины 1. Ее квадрат:

0 0 0 

 

– число путей длины 2. Легко видеть, что Ak = A 2 при k ≥ 2.

Замечание. Утверждение предыдущей теоремы можно распространить и на случай k = 0. Для каждой вершины графа имеется ровно один путь длины 0 из этой вершины в нее саму. Других путей длины 0 на графе нет. Следовательно, элемент eij единичной матрицы E = A 0 равен числу путей длины 0 из

вершины i в вершину j (eij = 0 при i ≠ j, eij = 1 при i = j).

Пусть G – ориентированный граф и A – его матрица смежности. Рассмотрим последовательность матриц

A 0, A 1, A 2, …, An –1. (2) Зафиксируем пару вершин i и j. Если существует какой-нибудь путь из i в j, то существует и путь длины меньше n. В самом деле, если длина пути превосходит n – 1, то такой путь проходит через более чем n вершин, и, значит, на таком пути хотя бы одна вершина, скажем, v, встретится более одного раза. Отбросив часть пути, ведущую из вершины v в нее саму, получаем более короткий путь из i в j. Повторив подобную операцию несколько раз, можно получить путь из i в j, длина которого не превосходит n – 1. Таким образом, если из i в j имеется некоторый путь, то в одной из матриц (2) на месте (i, j)

встретится элемент, отличный от нуля. Если в матрице Ak на месте (i, j) находится элемент, отличный от нуля, а во всех предшествующих матрицах A 0, A 1, A 2, …, Ak –1 на месте (i, j) стоят нули, то k – это длина кратчайшего пути из i в j.

Не нашли, что искали? Воспользуйтесь поиском: