Русская Википедия:Регулярный граф
Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается <math>r(G)</math>. Для нерегулярных графов <math>r(G)</math> не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
Регулярный граф с вершинами степени <math>k</math> называется регулярным графом степени <math>k</math>, или <math>k</math>‑регулярным.
Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный — из изолированных рёбер, а 2-регулярный — из разрозненных циклов.
3-регулярный граф известен также как кубический.
Сильно регулярный граф есть регулярный граф, для которого существуют такие <math>\lambda</math> и <math>\mu</math>, что любые две смежные вершины имеют <math>\lambda</math> общих соседей и любые две несмежные вершины имеют <math>\mu</math> общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.
Полный граф <math>K_m</math> является сильно регулярным для любого <math>m</math>.
Теорема Шаблон:Нп5 гласит, что каждый k‑регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл.
-
0-регулярный граф
-
1-регулярный граф
-
2-регулярный граф
-
3-регулярный граф
-
Ещё один 3-регулярный граф — граф Петерсена
Алгебраические свойства
Пусть A есть матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда <math>\textbf{j}=(1, \dots ,1)</math> есть собственный вектор A[1]. Его собственное число будет постоянной степенью графа. Собственные векторы, соответствующие другим собственным числам, ортогональны <math>\textbf{j}</math>, поэтому для собственных векторов <math>v=(v_1,\dots,v_n)</math> мы имеем <math>\sum_{i=1}^n v_i = 0</math>.
Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность[1].
Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с <math>J_{ij}=1</math> находится в Шаблон:Нп5 графа[2].
Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности <math>k=\lambda_0 >\lambda_1\geq \dots\geq\lambda_{n-1}</math>. Если G не двудолен:
<math>D\leq \frac{\log{(n-1)}}{\log(k/\lambda)}+1</math>[3] [4]
где
<math> \lambda=\max_{i>0}\{|\lambda_i|\}</math>.
Генерация
Регулярный граф можно сгенерировать программой GenReg.[5]
См. также
Примечания
Ссылки
- Шаблон:MathWorld
- Шаблон:MathWorld
- GenReg программа и данные Маркуса Мерингера.
- Шаблон:Citation
- ↑ 1,0 1,1 Д. М. Цветкович, М. Дуб и Х. Сачс, «Спектр графов: теория и применение», 3-я редакция, Нью-Йорк: Уайли, 1998.
- ↑ Шаблон:Citation
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ М. Мерингер, "Теория графов", 1999, 30, 137.
