Матричный метод нахождения путей в графах

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А2 определяется по формуле
a(2) ik= n j=1aijajk
Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа aij и ajk равны 1, в противном случае оно равно 0. Поскольку из равенства aij = ajk = 1следует существование пути длины 2 из вершины xi в вершину хk , проходящего через вершину xj , то ( i -й, k -й) элемент матрицы А2 равен числу путей длины 2, идущих из xi в хk .
На таблице 4.1a представлена матрица смежности графа, изображенного на рис. 4.2. Результат возведения матрицы смежности в квадрат А2 показан на таблице 4.1б.
Таблица 4.1а.


X1
X2
X3
X4
X5
X6

X1







X2






A=
X3







X4







X5







X6







Таблица 4.1б.


X1
X2
X3
X4
X5
X6

X1







X2






A2=
X3







X4







X5







X6







Таблица 4.1в.


X1
X2
X3
X4
X5
X6

X1







X2






A3=
X3







X4







X5







X6







Таблица 4.1г.


X1
X2
X3
X4
X5
X6

X1







X2






A4=
X3







X4







X5







X6







Так "1", стоящая на пересечении второй строки и четвертого столбца, говорит о существовании одного пути длиной 2 из вершины х2 к вершине х4 . Действительно, как видим в графе на рис. 4.2, существует такой путь: a6, a5 . "2" в матрице A2 говорит о существовании двух путей длиной 2 от вершины х3 к вершине х6 : a8, a4 и a10, a3 .
Аналогично для матрицы смежности, возведенной в третью степень A3 (таблица 4.1в), a (3) ik равно числу путей длиной 3, идущих от xi к хk . Из четвертой строки матрицы A3 видно, что пути длиной 3 существуют: один из х4 в х4(a9, a8, a5), один из х4 в х5(a9, a10, a6) и два пути из х4 в х6(a9, a10, a3 и a9, a8, a4). Матрица A4 показывает существование путей длиной 4 (таблица 4.1г).
Таким образом, если a р ik является элементом матрицы Aр ,то a р ik равно числу путей (не обязательно орцепей или простых орцепей) длины р, идущих от xi к хk .