2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Пчму степень матрицы смежности графа вдаёт кол-во путей?
Сообщение26.03.2023, 18:26 
Аватара пользователя


20/02/12
167
Всем привет! Помогите разобраться, что я не так понимаю. В разных источниках пишут: "Если $\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)
. Что я упускаю?

 Профиль  
                  
 
 Re: Пчму степень матрицы смежности графа вдаёт кол-во путей?
Сообщение26.03.2023, 18:44 
Заслуженный участник
Аватара пользователя


11/03/08
10166
Москва
А что у Вас на диагонали?

 Профиль  
                  
 
 Re: Пчму степень матрицы смежности графа вдаёт кол-во путей?
Сообщение26.03.2023, 19:36 
Аватара пользователя


20/02/12
167
Евгений Машеров в сообщении #1586864 писал(а):
А что у Вас на диагонали?

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

 Профиль  
                  
 
 Re: Пчму степень матрицы смежности графа вдаёт кол-во путей?
Сообщение26.03.2023, 20:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Пчму степень матрицы смежности графа вдаёт кол-во путей?
Сообщение26.03.2023, 20:37 
Аватара пользователя


20/02/12
167
Евгений Машеров в сообщении #1586891 писал(а):
Единицы на диагонали - дозволен "бег на месте", путь из вершины в ту же вершину.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group