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

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

В теории графов дистанционно-регулярным графом называется регулярный граф такой, что для любых двух вершин 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[2]. Массив целых, определяющих дистанционно-регулярный граф, известен как массив пересечений.

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

Дистанционно-регулярный граф с диаметром 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 часто показываются в виде массива из трёх строк

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

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

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

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

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

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

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

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

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

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

Литература[править | править вики-текст]

Дальнейшее чтение[править | править вики-текст]

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