2014 dxdy logo

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

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


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


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



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


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

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


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

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

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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