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

Граф называется регулярным (или однородным), если степени всех его вершин равны; степенью регулярного графа называется степень его вершин. Степень регулярного графа G обозначается через deg G.

Все полные графы регулярны. Графы платоновых тел также регулярны. Регулярным графом степени n является n -мерный куб Q_n.

Из леммы о рукопожатиях вытекает, что не существует регулярного графа, порядок и степень которого нечетны.

Утверждение 7.1. Пусть натуральные числа n и d, среди которых есть четное, удовлетворяют неравенствам 0<= d <= n -1. Тогда существует регулярный граф порядка n и степени d.

> Для d = 0 утверждение очевидно. Кроме того, если G — регулярный граф порядка n степени d, то дополнительный граф также регулярен и deg =n- 1- d. Поэтому достаточно рассмотреть случай, когда 0 < d <= (n -1)/2.

Пусть Z_n — аддитивная группа классов целых чисел по модулю n, A Ì Z _n, 0Ï A и для x Î A класс – x также принадлежит множеству A. Определим граф G порядка n c множеством вершин Z_n следующим условием: вершины x и y смежны, если x — y Î A. Очевидно, что граф G регулярен и степень его равна | A|. Остается доказать, что для любого числа d, удовлетворяющего указанным выше условиям, существует подходящее d -элементное множество A. При d = 2k можно взять A = {±1, ±2,..., ±k }, а при d= 2k+ 1оказывается четным n, и можно взять A = { ±1, ±2,..., ±k, n /2} (см. рис. 7.1, где n = 8, d = 3). <

Утверждение 7.2. Если G = (X, Y, E) —непустой регулярный двудольный граф, то |X| = |Y|.

> Так как доле X принадлежит только один из концов каждого ребра графа G, то число m его ребер равно |Х| deg G. Аналогично m = |Y| deg G. Следовательно, | X| deg G = | Y| deg G. Поскольку deg G ¹0, то | X |= | Y |. <

Иногда, хотя и редко, граф определяется степенями своих вершин. Например, только O_n является регулярным графом порядка n нулевой степени. Регулярный граф первой степени имеет четный порядок 2т и является дизъюнктным объединением m ребер. Этот граф обозначается символом тK₂. Все связные компоненты регулярного графа второй степени являются простыми циклами. Однако уже кубические графы, т. е. регулярные графы степени 3, устроены сложно и не определяются степенями своих вершин. Примером кубического графа является граф Петерсена (рис. 1.6). Отметим любопытное свойство спектра регулярного графа.

Теорема 7.3. Пусть G — регулярный граф степени d. Тогда:

1) число d является корнем характеристического полинома графа G;

2) если G — связный граф, то кратность корня d равна 1;

3) d >= |l| для любого корня l характеристического полинома графа G.

> 1) Пусть VG = {1, 2 ,..., n }, A (G) = A — матрица смежности графа G, u —столбец высоты n, все элементы которого равны 1. Поскольку в каждой строке матрицы A ровно d единиц, то Au = du и, следовательно, u — собственный вектор, а d — собственное значение линейного оператора A. Но каждое собственное значение является корнем характеристического полинома. Тем самым доказано, что d — корень характеристического полинома графа G.

2) Для произвольного собственного вектора x = (x ₁, x ₂ ,..., x_n) с собственным значением d имеем

Ax = dx x ¹0. (1)

Пусть x_j — координата вектора x с максимальным модулем, N_j = N (j) –окружение вершины j в графе G. Из равенства (1) для j -й координаты вектора Ax вытекает

и, далее,

(3)

Поскольку | N_j| = d, то из соотношений (2) и (3) следует, что x_i = x_j для всех i из N_j.. Для связного графа G теперь получаем, что все координаты вектора x равны между собой, т. е. размерность подпространства собственных векторов линейного оператора A, относящихся к собственному значению d, равна 1. Следовательно, и кратность корня d характеристического полинома матрицы A равна 1.

3) Пусть l — произвольный корень характеристического полинома матрицы A, x — соответствующий собственный вектор. Тогда Ах = l х, и в тех же обозначениях, что и выше, имеем

откуда |l| <= d. <