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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

[1]

[2]

[3]

[4]

[5]

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

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

Генерация

Примечания

Ссылки

См. также