Регулярный граф

Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается ${\displaystyle r(G)}$. Для нерегулярных графов ${\displaystyle r(G)}$ не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

Регулярный граф с вершинами степени ${\displaystyle k}$ называется регулярным графом степени ${\displaystyle k}$, или ${\displaystyle k}$‑регулярным.

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

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

Сильно регулярный граф есть регулярный граф, для которого существуют такие ${\displaystyle \lambda }$ и ${\displaystyle \mu }$, что любые две смежные вершины имеют ${\displaystyle \lambda }$ общих соседей и любые две несмежные вершины имеют ${\displaystyle \mu }$ общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.

Полный граф ${\displaystyle K_{m}}$ является сильно регулярным для любого ${\displaystyle m}$.

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

• 
  0-регулярный граф
• 
  1-регулярный граф
• 
  2-регулярный граф
• 
  3-регулярный граф
• 
  Ещё один 3-регулярный граф — граф Петерсена

Алгебраические свойства

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

Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность[1].

Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с ${\displaystyle J_{ij}=1}$ находится в алгебре смежности^[англ.] графа[2].

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

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(k/\lambda )}}+1}$[3] [4]

где

${\displaystyle \lambda =\max _{i>0}\{|\lambda _{i}|\}}$.

Генерация

Регулярный граф можно сгенерировать программой GenReg.[5]

См. также

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

Примечания

1. Д. М. Цветкович, М. Дуб и Х. Сачс, «Спектр графов: теория и применение», 3-я редакция, Нью-Йорк: Уайли, 1998.
2. Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2–3): 241—248, doi:10.1007/s10623-004-4857-4, MR 2128333
3. Gregory Quenell. Spectral diameter estimates for k-regular graphs.
4. Fan R.K. Chung. Spectral Graph Theory. — American Mathematical Society, 1997. — (CBMS). — ISBN 0821803158.
5. М. Мерингер, "Теория графов", 1999, 30, 137.

Ссылки

• Weisstein, Eric W. Regular Graph (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Strongly Regular Graph (англ.) на сайте Wolfram MathWorld.
• GenReg программа и данные Маркуса Мерингера.
• Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo