Регулярный график

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

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

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

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

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

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

Полный граф K _m сильно регулярен для любого 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 -регулярный граф с нечетным k имеет четное число вершин.

Теорема Нэша-Вильямса гласит, что любой 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 имеет кратность 1. Направление «только если» является следствием теоремы Перрона–Фробениуса . ^[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). Теория графов и ее инженерные приложения . World Scientific. стр. 29. ISBN 978-981-02-1859-1.
2. Цветкович, Д.М.; Дуб, М.; и Сакс, Х. Спектры графов: теория и приложения, 3-е переиздание. Расширенное издание. Нью-Йорк: Wiley, 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.

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

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