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

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

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

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

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

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

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

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

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

Необходимые и достаточные условия для $k$ -регулярный график порядка $n$ существовать - это то, что $n\geq k+1$ и это $nk$ четный.

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

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

По лемме о согласовании -регулярный граф $k$ с нечетным $k$ имеет четное число вершин.

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

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

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

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

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

D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.

^[4]

Поколение

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

См. также

Ссылки

^ Чен, Вай-Кай (1997). Теория графов и ее инженерные приложения . Всемирная научная. стр. 29 . ISBN 978-981-02-1859-1 .
^ Jump up to: ^а ^б Цветкович, Д.М.; Дуб, М.; и Сакс, Х. Спектры графов: теория и приложения, 3-е изд. англ. ред. Нью-Йорк: Уайли, 1998.
^ Кертин, Брайан (2005), «Алгебраические характеристики условий регулярности графа», Designs, Codes and Cryptography , 34 (2–3): 241–248, doi : 10.1007/s10623-004-4857-4 , MR 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 .

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

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

[1] Чен, Вай-Кай (1997). Теория графов и ее инженерные приложения . Всемирная научная. стр. 29 . ISBN 978-981-02-1859-1 .

[Cvetkovic-2] Jump up to: ^а ^б Цветкович, Д.М.; Дуб, М.; и Сакс, Х. Спектры графов: теория и приложения, 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 .

[1]

[2]

[3]

[4]

[5]

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, $t \geq 2$		кососимметричный
↓
_{(если подключен)} вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	_{(если двусторонний)} бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный