Введение

Граф, где у каждой вершины одинаковое количество соседей.

В теории графов, регулярный граф — это граф, в котором у каждой вершины одинаковое количество соседей, то есть каждая вершина имеет одинаковую степень или валентность. Регулярный ориентированный граф также должен удовлетворять более строгому условию: входящая и исходящая степени каждой вершины должны быть равны. Регулярный граф, вершины которого имеют степень k, называется k-регулярным графом или регулярным графом степени k.

Особые случаи

Регулярные графы степени не более 2 легко классифицировать: 0-регулярный граф состоит из изолированных вершин, 1-регулярный граф состоит из изолированных ребер, а 2-регулярный граф состоит из непересекающихся циклов и бесконечных путей. 3-регулярный граф известен как кубический граф. Строго регулярный граф — это регулярный граф, в котором каждая пара смежных вершин имеет одинаковое количество l общих соседей, а каждая пара несмежных вершин имеет одинаковое количество n общих соседей. Наименьшие графы, которые являются регулярными, но не строго регулярными, — это цикл и циркулянт на 6 вершинах. Полный граф является строго регулярным для любого m.

Существование

Необходимые и достаточные условия для существования регулярного графа порядка *n* – это *n* и то, что *n* является четным. Доказательство: полный граф имеет каждую пару различных вершин, соединенных друг с другом единственным ребром. Следовательно, количество ребер максимально в полном графе и равно *n(n-1)/2*, а степень каждой вершины равна *n-1*. Это минимальное значение степени для данного порядка *n*. Также заметим, что если любой регулярный граф имеет порядок *n*, то количество ребер равно *kn/2*, где *k* – степень вершины. Следовательно, *kn* должно быть четным. В таком случае легко построить регулярные графы, рассматривая подходящие параметры для циркулянтных графов.

Свойства

Из леммы о рукопожатиях следует, что k-регулярный граф с нечетным k имеет четное число вершин. Теорема Нэша-Уильямса утверждает, что любой граф на 2k + 1 вершинах имеет гамильтонов цикл. Пусть A — матрица смежности графа. Тогда граф является регулярным тогда и только тогда, когда является собственным вектором A. Его собственное значение будет равно постоянной степени графа. Собственные векторы, соответствующие другим собственным значениям, ортогональны к , поэтому для таких собственных векторов выполняется условие . K-регулярный граф связен тогда и только тогда, когда собственное значение k имеет кратность один. Направление "только если" является следствием теоремы Перрона — Фробениуса. Пусть G — k-регулярный граф с диаметром D и собственными значениями матрицы смежности. Если G не является двудольным, то

Поколение

Быстрые алгоритмы существуют для генерации, с точностью до изоморфизма, всех регулярных графов с заданной степенью и числом вершин.