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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Регулярный граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

Регулярный граф с вершинами степени k называется k‑регулярным, или регулярным графом степени k.

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

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

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

Полный граф K_m является сильно регулярным для любого m.

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

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

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

Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность.[1]

Другой критерий регулярности и связности графа: граф связен и регулярен только и только тогда, когда матрица J с J_{ij}=1 находится в алгебре смежности графа. [2]


Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности k=\lambda_0 >\lambda_1\geq \dots\geq\lambda_{n-1}. Если G не двудолен:

D\leq \frac{\log{(n-1)}}{\log(k/\lambda)}+1[3] [4]

где

 \lambda=\max_{i>0}\{\mid \lambda_i \mid \}.

Генерация[править | править вики-текст]

Регулярный граф можно сгенерировать программой GenReg.[5]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Д. М. Цветкович, М. Дуб и Х. Сачс, "Спектр графов: теория и применение", 3-я редакция, Нью-Йорк: Уайли, 1998.
  2. {{ | автор = Brian Curtin | год = 2005 | заглавие = Algebraic characterizations of graph regularity conditions | серия = Designs, Codes and Cryptography | выпуск = 34 | страницы = 241–248 | doi = 10.1007/s10623-004-4857-4 | MR= 2128333. }}
  3. Gregory Quenell Spectral diameter estimates for k-regular graphs.
  4. Fan R.K. Chung Spectral Graph Theory. — American Mathematical Society, 1997. — (CBMS). — ISBN 0821803158
  5. М. Мерингер, "Теория графов", 1999, 30, 137.

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

  • Weisstein, Eric W. Regular Graph (англ.) на сайте Wolfram MathWorld.
  • Weisstein, Eric W. Strongly Regular Graph (англ.) на сайте Wolfram MathWorld.
  • GenReg программа и данные Маркуса Мерингера.
  • Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", «University of Waterloo Research Report», Waterloo, Ontario: University of Waterloo