Граф регулярных блужданий (Ijgs jyirlxjud] Qlr';gunw)

Перейти к навигации Перейти к поиску

Граф регулярных блужданийпростой граф, в котором число замкнутых блужданий любой длины от вершины в неё же не зависит от выбора вершины.

Эквивалентные определения

[править | править код]

Предположим, что является простым графом. Пусть означает матрицу смежности графа , означает множество вершин графа , а означает характеристический многочлен подграфа с удалённой вершиной Следующие утверждения эквивалентны:

  • является графом регулярных блужданий.
  • является диагональной матрицей с константой по диагонали для всех
  • для всех


Примечания

[править | править код]
  1. Farrell, Mark Distinct Eigenvalues and Walk-Regular Graphs – In Search of Structure. Дата обращения: 21 июля 2017.