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

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

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

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

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

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

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

Теорема Шаблон:Нп5 гласит, что каждый k‑регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл.

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

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

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

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

Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с $J_{ij}=1$ находится в Шаблон:Нп5 графа.

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

$D\le \frac{\log (n-1)}{\log (k/\lambda )}+1$

где

$\lambda =\underset{i>0}{\max }\{|{\lambda }_i|\}$.

Генерация

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

См. также

• Случайный регулярный граф Шаблон:Ref-en
• Сильно регулярный граф
• Граф Мура Шаблон:Ref-en
• Клетка

Ссылки

• Шаблон:MathWorld
• Шаблон:MathWorld
• GenReg программа и данные Маркуса Мерингера.
• Шаблон:Citation