Любой ориентированный граф с вершинами v1, v2, …, vn и дугами a1, a2, …, am можно задать его матрицей инцидентности B=(bij), i = 1,2,…, n, j = 1,2,…, m, размера nm, в которой 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
1
A 1
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.
(k+1)
До каз а тельст во . Докажем теорему индукцией по k. При k = 1 имеем A1 = A, так что заключение теоремы верно, поскольку элемент aij(1) = (aij) равен числу дуг из i в j, то есть числу путей длины 1. Предположим теперь, что каждый элемент aij(k) матрицы Ak = (aij(k)) равен числу путей длины k из вершины i в вершину j и покажем, что каждый элемент aij матрицы Ak+1 = (aij(k+1)) равен числу путей длины k+1 из вершины i в вершину j. Так как Ak+1 = AkA, то
aij(k+1) = ai1(k)⋅a1j + ai2(k)⋅a2j +…+ ain(k)⋅anj . (1) Слагаемое ai1(k)⋅a1j равно числу путей из i в j длины k+1, в которых вершина 1 предпоследняя: пути длины k из вершины i в вершину 1 комбинируются с дугами из вершины 1 в вершину
j. Аналогично слагаемое ai2(k)⋅a2j равно числу путей из 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
A 1 1 1
0 0
дает число путей длины 1. Ее квадрат:
0 0 0
A2 1 1 3
0 0
– число путей длины 2. Легко видеть, что Ak = A2 при k ≥ 2.
Замечание.Утверждение предыдущей теоремы можно распространить и на случай k = 0. Для каждой вершины графа имеется ровно один путь длины 0 из этой вершины в нее саму. Других путей длины 0 на графе нет. Следовательно, элемент eij единичной матрицы E = A0 равен числу путей длины 0 из
вершины i в вершину j (eij = 0 при i ≠ j, eij = 1 при i = j).
Пусть G – ориентированный граф и A – его матрица смежности. Рассмотрим последовательность матриц
A0, A1, A2, …, 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) находится элемент, отличный от нуля, а во всех предшествующих матрицах A0, A1, A2, …, Ak–1 на месте (i,j) стоят нули, то k – это длина кратчайшего пути из i в j.
представленного на рис. 7.
1 2