Обычный график

Граф, в котором каждая вершина имеет одинаковое количество соседей

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

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

Регулярные графы степени не выше 2 легко классифицировать: 0-регулярный граф состоит из несвязных вершин, 1-регулярный граф состоит из несвязных ребер, 2-регулярный граф состоит из непересекающегося объединения циклов и бесконечных цепей.

3-регулярный граф известен как кубический граф .

Сильно регулярный граф — это регулярный граф, в котором каждая соседняя пара вершин имеет одинаковое количество общих соседей l , а каждая несмежная пара вершин имеет одинаковое количество общих соседей n . Наименьшими регулярными, но не сильно регулярными графами являются граф циклов и циркулянтный граф с 6 вершинами.

Полный граф Km сильно регулярен для _любого m .

• 
  0-регулярный граф
• 
  1-регулярный граф
• 
  2-регулярный граф
• 
  3-регулярный граф

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

Необходимые и достаточные условия существования регулярного графа порядка — то и то — четно. ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n\geq k+1}$ ${\displaystyle nk}$

Доказательство: В полном графе каждая пара различных вершин соединена друг с другом уникальным ребром. Таким образом, ребра максимальны в полном графе, а количество ребер и степень здесь равны . Так . Это минимум для конкретного . Также обратите внимание, что если любой регулярный граф имеет порядок , то количество ребер должно быть четным. В таком случае легко построить регулярные графы, рассмотрев соответствующие параметры циркулянтных графов . ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}}}$ ${\displaystyle n-1}$ ${\displaystyle k=n-1,n=k+1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle {\dfrac {nk}{2}}}$ ${\displaystyle nk}$

Характеристики

Теорема Нэша-Вильямса гласит, что каждый k - регулярный граф на 2k + 1 вершине имеет гамильтонов цикл .

Пусть A — матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда является собственным вектором A . ^[2] Его собственным значением будет постоянная степень графа. Собственные векторы, соответствующие другим собственным значениям, ортогональны , поэтому для таких собственных векторов мы имеем . ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ ${\displaystyle {\textbf {j}}}$ ${\displaystyle v=(v_{1},\dots ,v_{n})}$ ${\displaystyle \sum _{i=1}^{n}v_{i}=0}$

Регулярный граф степени k связен тогда и только тогда, когда собственное значение k имеет кратность единица. Направление «только если» является следствием теоремы Перрона-Фробениуса . ^[2]

Существует также критерий регулярных и связных графов: граф связен и регулярен тогда и только тогда, когда матрица единиц J , с , находится в алгебре смежности графа (то есть это линейная комбинация степеней A ). ^[3] ${\displaystyle J_{ij}=1}$

Пусть G — k -регулярный граф с диаметром D и собственными значениями матрицы смежности . Если G не двудольная, то ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}}$

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$^[4]

Поколение

Существуют быстрые алгоритмы, позволяющие генерировать с точностью до изоморфизма все регулярные графы с заданной степенью и количеством вершин. ^[5]

Смотрите также

• Случайный регулярный график
• Сильно регулярный граф
• Граф Мура
• Граф клетки
• Сильно нерегулярный график

Рекомендации

1. Чен, Вай-Кай (1997). Теория графов и ее инженерные приложения . Всемирная научная. стр. 29. ISBN 978-981-02-1859-1.
2. Цветкович, DM; Дуб, М.; и Сакс, Х. Спектры графов: теория и приложения, 3-е изд. англ. ред. Нью-Йорк: Уайли, 1998.
3. Кертин, Брайан (2005), «Алгебраические характеристики условий регулярности графа», Designs, Codes and Cryptography , 34 (2–3): 241–248, doi : 10.1007/s10623-004-4857-4, MR  2128333.
4. [1] ^{[ нужна ссылка ]}
5. Мерингер, Маркус (1999). «Быстрое построение регулярных графов и построение клеток» (PDF) . Журнал теории графов . 30 (2): 137–146. doi :10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

Внешние ссылки

• Вайсштейн, Эрик В. «Регулярный график». Математический мир .
• Вайсштейн, Эрик В. «Строго регулярный граф». Математический мир .
• Программное обеспечение GenReg и данные Маркуса Мерингера.
• Нэш-Уильямс, Криспин (1969), Валентные последовательности, которые заставляют графы иметь гамильтоновы схемы , Отчет об исследовании Университета Ватерлоо, Ватерлоо, Онтарио: Университет Ватерлоо