Регулярный граф
Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается . Для нерегулярных графов не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
Регулярный граф с вершинами степени называется регулярным графом степени , или ‑регулярным.
Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный — из изолированных рёбер, а 2-регулярный — из разрозненных циклов.
3-регулярный граф известен также как кубический.
Сильно регулярный граф есть регулярный граф, для которого существуют такие и , что любые две смежные вершины имеют общих соседей и любые две несмежные вершины имеют общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.
Полный граф является сильно регулярным для любого .
Теорема Нэш-Вильямса[англ.] гласит, что каждый k‑регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл.
-
0-регулярный граф
-
1-регулярный граф
-
2-регулярный граф
-
3-регулярный граф
-
Ещё один 3-регулярный граф — граф Петерсена
Алгебраические свойства
[править | править код]Пусть A есть матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда есть собственный вектор A[1]. Его собственное число будет постоянной степенью графа. Собственные векторы, соответствующие другим собственным числам, ортогональны , поэтому для собственных векторов мы имеем .
Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность[1].
Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с находится в алгебре смежности[англ.] графа[2].
Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности . Если G не двудолен:
где
.
Генерация
[править | править код]Регулярный граф можно сгенерировать программой GenReg.[5]
См. также
[править | править код]- Случайный регулярный граф (англ.)
- Сильно регулярный граф
- Граф Мура (англ.)
- Клетка
Примечания
[править | править код]- ↑ 1 2 Д. М. Цветкович, М. Дуб и Х. Сачс, «Спектр графов: теория и применение», 3-я редакция, Нью-Йорк: Уайли, 1998.
- ↑ 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
- ↑ Gregory Quenell. Spectral diameter estimates for k-regular graphs.
- ↑ Fan R.K. Chung. Spectral Graph Theory. — American Mathematical Society, 1997. — (CBMS). — ISBN 0821803158.
- ↑ М. Мерингер, "Теория графов", 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