8.1. Матрица смежности
Пусть дан граф G, его матрица смежности обозначается через 
и определяется следующим образом:
, если в G существует дуга 
,
если в G нет дуги .
Таким образом, матрица смежности графа, изображенного на рис. 1.8, имеет вид
Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки 
матрицы дает полустепень исхода вершины , а сумма элементов столбца — полустепень захода вершины . Множество столбцов, имеющих 1 в строке ,. есть множество 
, а множество строк, которые имеют 1 столбце , совпадает с множеством 
.
Возведем матрицу смежности в квадрат. Пусть элемент 
матрицы А2 определяется по формуле
(1.14)
Слагаемое в уравнении (1.14) равно 1 тогда и только тогда, когда оба числа 
и 
равны 1, в противном случае оно равно 0.
Поскольку из равенств 
следует существование пути длины 2 из вершины к вершине 
, проходящего через вершину 
, то равно числу путей длины 2, идущих из в .
Рис. 1.8.
Аналогично если 
является элементом матрицы 
, то равно числу путей (не обязательно орцепей или простых орцепей) длины р, идущих от к .