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

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

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

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

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

В полный график ${ displaystyle K_ {m}}$ сильно регулярен для любого ${ displaystyle m}$ .

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

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 k}$ то количество ребер равно ${ displaystyle { dfrac {nk} {2}}}$ так ${ displaystyle nk}$ должен быть четным. В этом случае легко построить регулярные графы, учитывая соответствующие параметры для циркулянтные графики.

Алгебраические свойства

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

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

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

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

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

^[4]

Поколение

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

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

внешняя ссылка

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

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

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

[3] Куртин, Брайан (2005), "Алгебраические характеристики условий регулярности графов", Конструкции, коды и криптография, 34 (2–3): 241–248, Дои:10.1007 / s10623-004-4857-4, МИСТЕР 2128333.

[4] [1]^{[нужна цитата ]}

[5] Мерингер, Маркус (1999). «Быстрая генерация регулярных графиков и построение клеток» (PDF). Журнал теории графов. 30 (2): 137–146. Дои:10.1002 / (SICI) 1097-0118 (199902) 30: 2 <137 :: AID-JGT7> 3.0.CO; 2-G.

[1]

[2]

[3]

[4]

[5]

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