Дистанционно-регулярный граф

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

В теории графов дистанционно-регулярным графом называется регулярным граф, такой, что для любых двух вершин v и w, число вершин с расстоянием j от v и расстоянием k от w зависят только от j и k и i = d(v, w).

В частности, это выполняется для k = 1 — в дистанционно-регулярных графах для любых двух вершин v и w, находящихся на расстоянии i, число вершин, смежных с w и находящихся на расстоянии j от v, одно и то же. Оказывается, что и обратное верно, это свойство влечёт определение дистанционной регулярности, данное выше.[1] Таким образом, получаем эквивалентное определение дистанционно-регулярного графа — это граф, для которого существуют целые bi,ci,i=0,...,d, такие что для любых двух вершин x,y графа G и расстояния i=d(x,y), существует в точности ci соседей y в Gi-1(x) и bi соседей y в Gi+1(x), где Gi(x) — множество вершин y графа G с d(x,y)=i (Brouwer и др., стр. 434). Массив целых, определяющих дистанционно-регулярный граф, известен как массив пересечений.

Любой дистанционно-транзитивный граф является дистанционно регулярным. Более того, дистанционно-регулярные графы были введены как комбинаторное обобщение дистанционно-транзитивных графов, имеющих свойство численной регулярности последних без необходимости иметь большую группу автоморфизмов.

Дистанционно-регулярный граф с диаметром 2 является сильно регулярным, и обратное тоже верно (при условии, что граф является связным).

Числа пересечений[править | править исходный текст]

Обычно используются следующие обозначения для дистанционно-регулярного графа G. Число вершин равно n. Число соседей w (то есть вершины, смежные w), чьё расстояние от v равно i, i + 1, и i − 1 обозначается как ai, bi, и ci, соответственно. Они называются числами пересечений графа G. Очевидно, что a0 = 0, c0 = 0, и b0 равно k, степени вершины. Если G имеет конечный диаметр, то d обозначает диаметр и мы получим bd = 0.

Также мы имеем ai+bi+ci= k Числа ai, bi, и ci часто показываются в виде массива из трёх строк

\left\{\begin{matrix} - & c_1 & \cdots & c_{d-1} & c_d \\ a_0 & a_1 & \cdots & a_{d-1} & a_d \\ b_0 & b_1 & \cdots & b_{d-1} & - \end{matrix}\right\},

который называется массивом пересечений графа G. Их можно также представить в виде трёхдиагональной матрицы

B:= \begin{pmatrix} a_0 & b_0 & 0 & \cdots & 0 & 0 \\
c_1 & a_1 & b_1 & \cdots & 0 & 0 \\
0 & c_2 & a_2 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots &  & \vdots & \vdots \\
0 & 0 & 0 & \cdots & a_{d-1} & b_{d-1} \\
0 & 0 & 0 & \cdots & c_d & a_d \end{pmatrix} ,

называемой матрицей пересечений.

Матрицы дистанционной связности[править | править исходный текст]

Предположим, что G — связный дистанционно-регулярный граф. Для любого расстояния i = 1, ..., d, мы можем образовать граф Gi, в котором вершины смежны, если расстояние между ними в графе G равно i. Пусть Aiматрица смежности графа Gi. Например, A1 — это матрица смежности A графа G. Пусть также, A0 = I — единичная матрица. Это даёт нам d + 1 матриц A0, A1, ..., Ad, называемых матрицами расстояний графа G. Их сумма — это матрица J, в которой каждое значение равно 1. Имеется важная формула:

A A_i = a_i A_i + b_i A_{i+1} + c_i A_{i-1} .

Из формулы следует, что для каждая Ai является полиномиальной функцией от A степени i, и что A является корнем многочлена степени d + 1.

Более того, A имеет в точности d + 1 различных собственных значений, а именно, собственных значений матрицы пересечений B, из которых максимальным является k, степень.

Множество матриц расстояний является векторным подпространством векторного пространства всех n × n вещественных матриц. Замечателен факт, что произведение Ai Aj любых двух матриц расстояний является линейной комбинацией матриц расстояний:

A_i A_j = \sum_{k=0}^d p_{ij}^k A_k .

Это означает, что матрицы расстояний порождают схему ассоциаций[en]. Теория схем ассоциаций является центральным моментом для изучения дистанционно-регулярных графов. Например, свойство, что Ai является многочленом от A, есть свойство схем ассоциаций.

Примеры[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Andries Brouwer[en], A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5

Дальнейшее чтение[править | править исходный текст]

  • C. D. Godsil Algebraic combinatorics. — New York: Chapman and Hall, 1993. — С. xvi+362. — (Chapman and Hall Mathematics Series). — ISBN 0-412-04131-6