Пчму степень матрицы смежности графа вдаёт кол-во путей?

[Verbery]

Всем привет! Помогите разобраться, что я не так понимаю. В разных источниках пишут: "Если $\mathbf A$ — матрица смежности графа $G$, то матрица $\displaystyle \mathbf {A} ^{m}$ обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер"

Возвожу матрицу для графа-треугольника (в каждой ячейке единица) в степень 2 ($A_3 \times A_3$) и получаю число 3 в каждой ячейке матрицы, но ума не приложу откуда там целых 3 пути длины 2? Я максимум могу один такой путь найти: 1-2-3 (из 1 в 3). Дальше возвожу эту же матрицу в степень 3 ($A_3 \times A_3 \times A_3$) и получаю уже 9 в каждой ячейке, так же вижу только 1-3-1-3 (из 1 в 3)
. Что я упускаю?

[Евгений Машеров]

А что у Вас на диагонали?

[Verbery]

Евгений Машеров в сообщении #1586864 писал(а):

А что у Вас на диагонали?

Единицы. Действительно слона то я и не заметил! Спасибо, с нулями всё хорошо

[Евгений Машеров]

Даже с единицами можно оправдать. Единицы на диагонали - дозволен "бег на месте", путь из вершины в ту же вершину. С учётом этого путей 3 (напрямую, и с переходом из себя в себя в начале или конце пути).
Просто обычно такой путь не имеет смысла и не рассматривается, а на диагональ ставятся нули.

[Verbery]

Евгений Машеров в сообщении #1586891 писал(а):

Единицы на диагонали - дозволен "бег на месте", путь из вершины в ту же вершину.

Либо ещё можно сказать "во всех вершинах есть петля"