8. Матричные представления

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

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

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

Таким образом, матрица смежности графа, изображенного на рис. 1.8, имеет вид

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

Возведем матрицу смежности в квадрат. Пусть элемент матрицы определяется по формуле

Слагаемое в уравнении (1.14) равно 1 тогда и только тогда, когда оба числа равны 1, в противном случае оно равно 0.

Поскольку из равенств следует существование пути длины 2 из вершины к вершине проходящего через вершину то равно числу путей длины 2, идущих из

Рис. 1.8.

Аналогично если является элементом матрицы то равно числу путей (не обязательно орцепей или простых орцепей) длины идущих от