WikiSort.ru - Не сортированное

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

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

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

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

Числа пересечений

Обычно используются следующие обозначения для дистанционно-регулярного графа G. Число вершин равно n. Число соседей w (то есть вершины, смежные w), чьё расстояние от v равно i, i + 1, и i − 1 обозначается как a_i, b_i, и c_i, соответственно. Они называются числами пересечений графа G. Очевидно, что a₀ = 0, c₀ = 0, и b₀ = k, степени вершины. Если G имеет конечный диаметр, то d обозначает диаметр и мы получим b_d = 0.

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

${\displaystyle \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. Их можно также представить в виде трёхдиагональной матрицы

${\displaystyle 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, мы можем образовать граф G_i, в котором вершины смежны, если расстояние между ними в графе G равно i. Пусть A_i — матрица смежности графа G_i. Например, A₁ — это матрица смежности A графа G. Пусть также, A₀ = I — единичная матрица. Это даёт нам d + 1 матриц A₀, A₁, …, A_d, называемых матрицами расстояний графа G. Их сумма — это матрица J, в которой каждое значение равно 1. Имеется важная формула:

${\displaystyle AA_{i}=a_{i}A_{i}+b_{i}A_{i+1}+c_{i}A_{i-1}.}$

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

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

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

${\displaystyle A_{i}A_{j}=\sum _{k=0}^{d}p_{ij}^{k}A_{k}.}$

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

Примеры

• Полные графы являются дистанционно-регулярными графами с диаметром 1 и степенью v−1.
• Циклы C_2d+1 нечётной длины являются дистанционно-регулярными графами с k = 2 и диаметром d. Числами пересечений a_i = 0, b_i = 1, и c_i = 1, за исключением специальных случаев (смотрите выше) и c_d = 2.
• Все Графы Мура, в частности граф Петерсена и граф Хофмана — Синглтона^[en], являются дистанционно-регулярными.
• Сильно регулярные графы являются дистанционно-регулярными.
• Нечётные графы являются дистанционно-регулярными.

Примечания

Литература

• Andries Brouwer^[en], A.M. Cohen, and A. Neumaier. Distance Regular Graphs. — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.
• C. D. Godsil. Algebraic combinatorics. — N. Y.: Chapman and Hall, 1993. — С. xvi+362. — (Chapman and Hall Mathematics Series). — ISBN 0-412-04131-6.

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Проверить качество перевода с иностранного языка. Оформить математические формулы