- Регулярный граф
-
Регулярный граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается . Для нерегулярных графов не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
Регулярный граф с вершинами степени k называется k‑регулярным, или регулярным графом степени k.
Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный — из изолированных рёбер, а 2-регулярный — из разрозненных циклов.
3-регулярный граф известен также как кубический.
Сильно регулярный граф есть регулярный граф, у которого каждая пара смежных вершин имеет одинаковое количество l общих соседей, и каждая пара несмежных вершин имеет одинаковое количество n общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.
Полный граф является сильно регулярным для любого .
Теорема Нэш-Вильямса гласит, что каждый k‑регулярный граф на 2k + 1вершинах имеет гамильтонов цикл.
Содержание
Алгебраические свойства
Пусть A есть матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда есть собственный вектор A.[1] Его собственное число будет постоянной степенью графа. Собственные вектора, соответствующие другим собственным числам, ортогональны , поэтому для собственных векторов мы имеем .
Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность.[1]
Другой критерий регулярности и связности графа: граф связен и регулярен только и только тогда, когда матрица J с находится в алгебре смежности графа.
Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности . Если G не двудолен:
то
.
Генерация
Регулярный граф можно сгенерировать программой GenReg.[2]
См. также
- Случайный регулярный граф (англ.)
- Сильно регулярный граф (англ.)
- Граф Мура (англ.)
- Клетка
Примечания
Ссылки
- 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
Категория:- Графы
Wikimedia Foundation. 2010.