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

---

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

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

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

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

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

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

---