В теории графов , А регулярный граф является графиком , где каждая вершина имеет такое же число соседей; т.е. каждая вершина имеет одинаковую степень или валентность. Регулярный ориентированный граф должен также удовлетворять более сильному условию, что степень и исходная степень каждой вершины равны друг другу. [1] регулярный граф с вершинами степени называется -регулярными графами или регулярным графом степени . Кроме того, согласно лемме о рукопожатии , регулярный граф содержит четное число вершин с нечетной степенью.
Регулярные графы степеней не более 2 легко классифицировать: 0-регулярный граф состоит из разъединенных вершин, 1-регулярный граф состоит из несвязанных ребер и 2-регулярный граф состоит из несвязного объединения из циклов и бесконечных цепей.
3-регулярный граф известен как кубический граф .
Сильно регулярный граф является регулярным графом , где каждая смежная пара вершин имеет такой же число л соседей в общем, и каждом несмежных паре вершин имеет одинаковое число п соседей общий. Наименьшие регулярные, но не сильно регулярные графы - это циклический граф и циркулянтный граф на 6 вершинах.
Полный граф является сильно регулярным для любого .
Теорема Нэша-Вильямса гласит, что каждый регулярный граф на 2 k + 1 вершине имеет гамильтонов цикл .
Существование [ править ]
Хорошо известно, что необходимые и достаточные условия для существования регулярного графа порядка - это то и это четное.
Доказательство. Как мы знаем, в полном графе каждая пара различных вершин соединена друг с другом уникальным ребром. Таким образом, рёбер максимальны в полном графе, а количество рёбер равно и порядок здесь такой . Итак . Это минимум для конкретного . Также отметим , что если какой - либо регулярный граф имеет порядок , то число ребер , так должно быть четным. В таком случае легко построить регулярные графы, учитывая соответствующие параметры для циркулянтных графов .
Алгебраические свойства [ править ]
Пусть A - матрица смежности графа. Тогда граф является регулярным тогда и только тогда является собственным вектором из A . [2] Его собственным значением будет постоянная степень графа. Собственные векторы, соответствующие другим собственным значениям , ортогональны , поэтому для таких собственных векторов мы имеем .
Регулярный граф степени k связен тогда и только тогда, когда собственное значение k имеет кратность один. Направление «только если» является следствием теоремы Перрона – Фробениуса . [2]
Также существует критерий для регулярных и связных графов: граф связан и регулярен тогда и только тогда, когда матрица единиц J , с , находится в алгебре смежности графа (то есть это линейная комбинация степеней A ). [3]
Пусть G - k -регулярный граф с диаметром D и собственными значениями матрицы смежности . Если G не двудольный, то
- [4]
Поколение [ править ]
Существуют быстрые алгоритмы для перечисления с точностью до изоморфизма всех регулярных графов с заданной степенью и числом вершин. [5]
См. Также [ править ]
- Случайный регулярный граф
- Сильно регулярный граф
- Граф Мура
- График клетки
- Сильно нерегулярный график
Ссылки [ править ]
- Перейти ↑ Chen, Wai-Kai (1997). Теория графов и ее инженерные приложения . World Scientific. С. 29 . ISBN 978-981-02-1859-1.
- ^ a b Цветкович, DM; Дуб, М .; и Сакс, Х. Спектры графов: теория и приложения, 3-е изд. enl. изд. Нью-Йорк: Wiley, 1998.
- ^ Кёртин, Брайан (2005), "Алгебраические характеризации условий регулярности графа", Designs, коды и Cryptography , 34 (2-3): 241-248, да : 10.1007 / s10623-004-4857-4 , МР 2128333 .
- ^ [1] [ необходима ссылка ]
- ^ Мерингер, Маркус (1999). «Быстрая генерация регулярных графиков и построение клеток» (PDF) . Журнал теории графов . 30 (2): 137–146. DOI : 10.1002 / (SICI) 1097-0118 (199902) 30: 2 <137 :: AID-JGT7> 3.0.CO; 2-G .
Внешние ссылки [ править ]
Викискладе есть медиафайлы, связанные с регулярными графами . |
- Вайсштейн, Эрик В. «Регулярный граф» . MathWorld .
- Вайсштейн, Эрик В. "Сильно регулярный граф" . MathWorld .
- Программное обеспечение GenReg и данные Маркуса Мерингера.
- Нэш-Вильямс, Криспин (1969), Последовательности валентности, которые заставляют графы иметь гамильтоновы схемы , Отчет об исследованиях Университета Ватерлоо, Ватерлоо, Онтарио: Университет Ватерлоо