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

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

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

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

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

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

Полный граф является сильно регулярным для любого . ${\ displaystyle K_ {m}}$ ${\ displaystyle m}$

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

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

Существование [ править ]

Хорошо известно ^{[ цитата ],} что необходимые и достаточные условия для существования регулярного графа порядка таковы и это четно. ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ Displaystyle п \ geq k + 1}$ ${\ displaystyle nk}$

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

Алгебраические свойства [ править ]

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

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

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

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

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

^[4]

Поколение [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

^ Чен, Вай-Кай (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), Последовательности валентности, которые заставляют графы иметь гамильтоновы схемы , Отчет об исследованиях Университета Ватерлоо, Ватерлоо, Онтарио: Университет Ватерлоо

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

[Cvetkovic-2] Цветкович, DM; Дуб, М .; и Сакс, Х. Спектры графов: теория и приложения, 3-е изд. enl. изд. Нью-Йорк: Wiley, 1998.

[3] Кёртин, Брайан (2005), "Алгебраические характеризации условий регулярности графа", Designs, коды и Cryptography , 34 (2-3): 241-248, да : 10.1007 / s10623-004-4857-4 , МР 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]