Обычный график

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, t ≥ 2		кососимметричный
↓
(если подключен) вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	(если двусторонний) бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный

В теории графов — регулярный граф это граф , каждая вершина которого имеет одинаковое количество соседей; т.е. каждая вершина имеет одинаковую степень или валентность. Регулярный ориентированный граф также должен удовлетворять более сильному условию, согласно которому входящая и исходящая степени каждой внутренней вершины равны друг другу. Регулярный граф с вершинами степени k называется k -регулярным графом или регулярным графом степени k .

Особые случаи

не выше 2 легко классифицировать: 0-регулярный граф состоит из несвязных вершин, 1-регулярный граф состоит из несвязных ребер, 2-регулярный граф состоит из непересекающегося объединения циклов Регулярные графы степени и бесконечных цепей.

3 -регулярный граф известен как кубический граф .

Сильно регулярный граф — это регулярный граф, в котором каждая соседняя пара вершин имеет одинаковое количество общих соседей l , а каждая несмежная пара вершин имеет одинаковое количество n общих соседей . Наименьшими регулярными, но не сильно регулярными графами являются граф циклов и циркулянтный граф с 6 вершинами.

Полный граф Km _m сильно регулярен для любого .

• 
  0-регулярный граф
• 
  1-регулярный граф
• 
  2-регулярный граф
• 
  3-регулярный граф

Существование

Необходимые и достаточные условия для $k$-регулярный график порядка $n$ существовать - это то, что $n\geq k+1$ и это $nk$ даже.

Доказательство: В полном графе каждая пара различных вершин соединена друг с другом уникальным ребром. Таким образом, ребра максимальны в полном графе, а количество ребер равно ${\binom {n}{2}}={\dfrac {n(n-1)}{2}}$ и степень вот $n-1$. Так $k=n-1,n=k+1$. Это минимум $n$ для конкретного $k$. Также обратите внимание, что если какой-либо регулярный граф имеет порядок $n$ тогда количество ребер равно ${\dfrac {nk}{2}}$ так $nk$должно быть ровным. В таком случае легко построить регулярные графы, рассмотрев соответствующие параметры циркулянтных графов .

Свойства

Согласно лемме о согласовании , k -регулярный граф с нечетным k имеет четное число вершин.

Теорема Нэша-Вильямса что каждый k -регулярный граф на 2k гласит , + 1 вершине имеет гамильтонов цикл .

Пусть A — матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда ${\textbf {j}}=(1,\dots ,1)$ является вектором собственным A . Его собственным значением будет постоянная степень графа. Собственные векторы, соответствующие другим собственным значениям , ортогональны ${\textbf {j}}$, поэтому для таких собственных векторов $v=(v_{1},\dots ,v_{n})$, у нас есть $\sum _{i=1}^{n}v_{i}=0$.

Регулярный граф степени k связен тогда и только тогда, когда собственное значение k имеет кратность единица. Направление «только если» является следствием теоремы Перрона – Фробениуса .

Существует также критерий регулярных и связных графов: граф связен и регулярен тогда и только тогда, когда матрица единиц J с $J_{ij}=1$, находится в алгебре смежности графа (то есть представляет собой линейную комбинацию степеней A ).

Пусть G — k -регулярный граф с диаметром D и собственными значениями матрицы смежности $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$. Если G не двудольная, то

$D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.$

Поколение

Существуют быстрые алгоритмы, позволяющие генерировать с точностью до изоморфизма все регулярные графы с заданной степенью и количеством вершин.

См. также

• Случайный регулярный график
• Сильно регулярный граф
• Граф Мура
• Граф клетки
• Сильно нерегулярный график

Внешние ссылки

• Вайсштейн, Эрик В. «Регулярный граф» . Математический мир .
• Вайсштейн, Эрик В. «Строго регулярный граф» . Математический мир .
• Программное обеспечение GenReg и данные Маркуса Мерингера.
• Нэш-Уильямс, Криспин (1969), Валентные последовательности, которые заставляют графы иметь гамильтоновы схемы , Отчет об исследовании Университета Ватерлоо, Ватерлоо, Онтарио: Университет Ватерлоо