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

[[Файл:Shrikhande graph square.svg |thumb|right| [[Граф Шрикханде]] — дистанционно-регулярный граф, не являющийся дистанционно-транзитивным]]
'''Дистанционно-регулярный граф''' ({{lang-en|distance-regular graph}}) — такой [[регулярный граф]], у которого для двух любых вершин <math>v</math> и <math>w</math>, расположенных на одинаковом расстоянии <math>j</math> друг от друга, справедливо, что количество вершин, инцидентных к <math>v</math> и при этом находящихся на расстоянии <math>j-1</math> от вершины <math>w</math>, зависит только от расстояния <math>j</math> между вершинами <math>v</math> и <math>w</math>; более того, количество вершин, инцидентных к <math>v</math> и находящихся на расстоянии <math>j+1</math> от вершины <math>w</math>, также зависит только от расстояния <math>j</math>.

Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде{{sfn|Biggs|1971|}}, хотя сам термин появился гораздо позже{{sfn|Brouwer, Cohen and Neumaier|1989|p=128}}.

== Определение ==
''Определение дистанционно-регулярного графа''{{sfn|Biggs|1993|p=159}}{{sfn| Brouwer, Cohen and Neumaier|1989|p=126}}:
{{начало цитаты}}
''Дистанционно-регулярный граф'' — это неориентрированный, связанный, ограниченный, регулярный граф <math>\Gamma=(V,E)</math> валентности <math>k</math> и диаметром <math>D</math>, для которого справедливо следующее. Существуют натуральные числа
: <math>b_0 = k \quad b_1, \, \dots \, , \, b_{D-1}\ , \quad c_1=1, \quad c_2, \, \dots , \, c_D</math>

такие, что для каждой пары вершин <math>(u,v)</math>, отстоящих друг от друга на расстоянии <math>d(u,v)=j</math>, справедливо:

: (1) число вершин, инцидентных <math>u</math> и находящихся на расстоянии <math>j-1</math> от <math>v</math>, есть <math>c_j</math> (<math>1\leqslant j \leqslant D </math>)
: (2) число вершин, инцидентных <math>u</math> и находящихся на расстоянии <math>j+1</math> от <math>v</math>, есть <math>b_j</math> (<math>0\leqslant j \leqslant D-1 </math>).

{{конец цитаты}}

Тогда
: <math>\iota(\Gamma) = \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{D-1} \, ; \, 1, \, c_2, \, \dots, \, c_D \end{Bmatrix}</math>
есть ''массив пересечений'' графа <math>\Gamma</math> (см. {{ссылка на раздел|#Массив пересечений}}), а <math> a_j, \, b_j, \, c_j</math> — ''числа пересечений'', где <math> a_j = k -b_j - c_j </math>{{sfn|Biggs|1993|p=159}}{{sfn| Brouwer, Cohen and Neumaier|1989|p=126}}.

== Массив пересечений ==
Изначально термины ''«массив пересечений»'' и ''«числа пересечений»'' были введены для описания дистанционно-транзитивных графов{{sfn|Biggs|1971|p=18}}{{sfn|Lauri and Scapelatto|2016|p=33}}{{sfn|Biggs|1993|p=157}}.

Пусть <math>\Gamma=(V,E)</math> есть неориентированный, связанный, ограниченный граф, а две его вершины <math>u,v \in V(\Gamma)</math> находятся на расстоянии <math>j=d(u,v)</math> друг от друга. Все вершины <math>w</math>, инцидентные к вершине <math>u</math>, можно разбить на три множества <math>A</math>, <math>B</math> и <math>C</math> в зависимости от их расстояния <math>d(v,w)</math> до вершины <math>v</math> :
: <math> \left \{ w \in A\colon d(v,w) = j \right \}, \quad  \left \{ w \in B \colon d(v,w) = j+1 \right \}, \quad \left \{ w \in C \colon d(v,w) = j-1 \right \}</math>

Если граф <math>\Gamma</math> дистанционно-транзитивный, то [[Мощность множества|мощности (кардинальные числа)]] множеств <math>|A|, \, |B|, \, |C|</math> не зависят от вершин <math>u,v</math>, а зависят только от расстояния <math>j=d(u,v)</math>. Пусть <math>a_j = |A|, \, b_j = |B|, \, c_j = |C|</math>, где <math> a_j, \, b_j, \, c_j</math> есть '''числа пересечений'''.

Определим '''массив пересечений''' дистанционно-транзитивного графа <math>\Gamma</math> как:
: <math>\iota(\Gamma) = \begin{Bmatrix}
\ast & c_1 & c_2 & \dots & c_{d-1} & c_d \\
a_0 & a_1 & a_2 & \dots & a_{d-1} & a_d \\
b_0 & b_1 & b_2 & \dots & b_{d-1} & \ast \\ 
\end{Bmatrix}
</math>

Если <math>k</math> — валентность графа, то <math>b_0 = k</math> , <math>c_0=0</math> а <math>c_1=1</math>. Более того, <math>a_i + b_i +c_i = k</math>, тогда компактная форма записи массива пересечений есть:
: <math>\iota(\Gamma) = \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{D-1} \, ; \, 1, \, c_2, \, \dots, \, c_D \end{Bmatrix}</math>

== Дистанционно-регулярный и дистанционно-транзитивный графы ==
На первый взгляд [[дистанционно-транзитивный граф]] и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности{{sfn|Biggs|1993|p=159}}.

Следствием автоморфизма дистанционно-транзитивного графа является его регулярность. Соответственно, для регулярного графа можно определить [[Дистанционно-транзитивный граф#Массив пересечений|числа пересечений]]. С другой стороны для дистанционно-регулярного графа существует комбинаторная регулярность, и для него также определены числа пересечений (см. {{ссылка на раздел|#Массив пересечений}}), однако автоморфизм из этого не следует{{sfn| Brouwer, Cohen and Neumaier|1989|p=136}}{{sfn|Cohen|2004|p=232}}.

Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно{{sfn| Brouwer, Cohen and Neumaier|1989|p=136}}.
Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков ([[Адельсон-Вельский, Георгий Максимович|Г. М. Адельсон-Вельский]], [[Вейсфейлер, Борис Юльевич|Б. Ю. Вейсфелер]], А. А. Леман, И. А. Фараджев){{sfn|Адельсон-Вельский, Вейсфелер, Леман и Фараджев|1969|}}{{sfn| Brouwer, Cohen and Neumaier|1989|p=136}}. Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это [[граф Шрикханде]]. Единственный тривалентный граф этого типа — это [[12-клетка Татта]], граф с 126 вершинами{{sfn| Brouwer, Cohen and Neumaier|1989|p=136}}.

== Свойства ==
* Дистанционно-регулярный граф с диаметром 2 является [[Сильно регулярный граф|сильно регулярным]], и обратное тоже верно (при условии, что граф является [[Связный граф|связным]]){{sfn|Biggs|1993|p=159}}.

==== Свойства массива пересечений дистанционно-регулярного графа ====
Массив пересечений дистанционно-регулярного графа обладает следующими свойствами{{sfn|van Dam, Koolen and Tanaka|2006|p=8}}{{sfn|van Dam, Koolen and Tanaka|2006|p=11}}:
* Каждая вершина имеет постоянное число вершин <math>k_j</math>, отстоящих от нее на расстояние <math>j</math>, причем <math>k_0=1</math> и <math>k_{j+1}=\frac{b_j k_j}{c_{j+1}}</math> для всех <math>j=0, \, 1, \, \dots , \, D-1 </math>;
* Порядок графа <math>n</math> равен <math> n = k_0 + k_1 + \, \dots \, + k_D</math>;
* Число вершин, отстоящих от каждой вершины на расстоянии <math>j+1</math>, выражается через числа пересечений как <math>k_{j+1} = \frac{b_0 b_1 \dots b_j}{c_1 c_2 \dots c_{j+1}}</math> для всех <math>j=0, \, 1, \, \dots , \, D-1 </math>;
* Произведение <math>k_j \cdot n</math> числа вершин, отстоящих от произвольной вершины на расстоянии <math>j</math>, на порядок графа есть четная величина для всех <math>j=1, \, 2, \, \dots , \, D </math>;
* Произведение <math>k_j \cdot a_j</math> числа вершин, отстоящих от произвольной вершины на расстоянии <math>j</math>, на число пересечений <math>a_j</math> на есть четная величина для всех <math>j=1, \, 2, \, \dots , \, D </math>;
* Произведение <math>a_1 \cdot n \cdot k</math> числа пересечений <math>a_1</math> на порядок графа и на его валентность делится на 6;
* Для чисел пересечений <math>c_j</math> справедливо <math>1 \leqslant c_1 \leqslant c_2 \leqslant \dots \leqslant c_D</math>;
* Для чисел пересечений <math>b_j</math> справедливо <math>k=b_0 \geqslant b_1 \geqslant b_2 \dots \geqslant b_{D-1}</math>;
* Если <math>i+j \leqslant D</math>, то <math>c_i \leqslant b_j</math>;
* Есть такое <math>i</math>, что <math>k_0 \leqslant k_1 \leqslant \dots \leqslant k_i</math> и <math>k_{i+1} \geqslant k_{i+2} \geqslant \dots \geqslant k_D</math>.

== Матрицы расстояний транзитивно-регулярного графа ==
Пусть граф <math>\Gamma(V,E)</math> — транзитивно-регулярный диаметра <math>D</math>, <math> n=|V|</math> есть число его вершин, а <math>k</math> — валентность графа. Определим множество ''матриц расстояний'' ({{lang-en|distance matrices}}) размера <math>n \times n</math> <math>\left \{ \mathbf A_0, \, \mathbf A_1, \, \dots , \, \mathbf A_D  \right \}</math> как{{sfn|Biggs|1993|p=159}} :
: <math>\left ( \mathbf A_h  \right )_{r,s} =  \begin{cases}
  1  & : \, d(v_r , v_s) = h ,\\
  0 & :  \, d(v_r , v_s) \neq h
\end{cases}  </math>

==== Свойства матриц расстояний ====
Матрицы расстояния обладают следующими свойствами{{sfn|Biggs|1993|p=159}}:
* <math>\mathbf A_0 = \mathbf I_n </math>, где <math>\mathbf I_n</math> есть [[единичная матрица]] ;
* <math>\mathbf A_1 = \mathbf A </math> есть обычная [[матрица смежности]] графа <math>\Gamma(V,E)</math>;
* <math>\mathbf A_0 + \mathbf A_1 +\mathbf A_2 + \dots + \mathbf A_D = \mathbf J_n</math>, где <math>\mathbf J_n</math> есть [[матрица единиц]]
* <math>\mathbf A \mathbf A_i = b_{i-1}  \mathbf A_{i-1} + a_i \mathbf A_{i} + c_{i+1} \mathbf A_{i+1} </math>, где <math> \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{d-1} \, ; \, 1, \, c_2, \, \dots, \, c_d \end{Bmatrix}</math> — массив пересечений дистанционно-регулярного графа и <math>a_i =k-b_i -c_i</math>
* существуют такие действительные числа <math>p_{i,j}^h,\ ( i, \, j, \, h = 0, \, 1, \, \dots, \, D)</math>, что <math>\mathbf A_i \mathbf A_j = \sum^{D}_{h=0} {p_{i,j}^h \mathbf A_h}</math> для всех <math> ( i, \, j = 0, \, 1, \, \dots, \, D)</math>, причем <math>p_{i,j}^h</math> есть число пересечений, то есть количество вершин, находящихся на расстоянии <math>j</math> от вершины <math>v</math> и на расстоянии <math>i</math> от вершины <math>w</math> при условии расстояния <math>h</math> между вершинами <math>v</math> и <math>w</math>. Отметим, что <math>p_{1,i-1}^i = c_i</math>, <math>p_{1,i}^i = a_i</math>, <math>p_{1,i+1}^i = b_i</math>.

== Примечания ==
{{примечания}}

== Литература ==
* {{статья
 | автор =Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. 
 | заглавие = Об одном примере графа, не имеющего транзитивной группы автоморфизмов
 | издание = [[Доклады Академии наук]] 
 | том = 185
 | номер = 5
 | страницы = 975—976
 | год = 1969
 | ref = Адельсон-Вельский, Вейсфелер, Леман и Фараджев
 | ссылка        = http://mi.mathnet.ru/dan34546
 | mr = 0244107}}
* {{статья
 | автор         = Biggs N. L.
 | заглавие      = Intersection Matrices for Linear Graphs
 | оригинал      = 
 | ссылка        = 
 | язык          = en
 | ответственный = edited by D.J.A. Welsh
 | автор издания = 
 | издание       = Combinatorial mathematics and its applications : proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 
 | тип           = 
 | место         = London
 | издательство  = Academic press
 | год           = 1971
 | месяц         = 
 | число         = 
 | том           = 
 | выпуск        = 
 | номер         = 
 | страницы      = 15-23
 | isbn          = 
 | issn          = 
 | doi           = 
 | bibcode       = 
 | arxiv         = 
 | pmid          = 
 | ref           = Biggs
 | archiveurl    = 
 | archivedate   = 
}}
* {{книга
 | автор = Biggs N. L.
 | заглавие = Algebraic Graph Theory
 | издание = 2nd edition
 | издательство = [[Cambridge University Press]]
 | страниц = 205
 | язык = en
 | ref = Biggs
 | год = 1993
}}
* {{книга
 | автор         = Brouwer A., Cohen A. M., Neumaier A.
 | заглавие      = Distance Regular Graphs
 | место         = Berlin, New York
 | издательство  = [[Springer Verlag]]
 | год           = 1989
 | isbn          = 3-540-50619-5, 0-387-50619-5
 | ref           = Brouwer, Cohen and Neumaier
 |язык = en
}}
* {{книга
 | автор = Cohen A. M.
 |часть = Distance-transitive graphs
 | ответственный = edited by L. W. Beineke, R. J. Wilson
 | заглавие = Topics in Algebraic Graph Theory
 | серия = Encyclopedia of Mathematics and its Applications
 | том = 102
 | издательство = Cambridge University Press
 | год = 2004
 | язык = en
 | страницы = 222—249
| ref = Cohen
}}
* {{статья
 | автор    =  van Dam E. R., Koolen J. H., Tanaka H.
 | заглавие = Distance-regular graphs
 | ссылка   = https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS22
 | язык     = en
 | издание  = The Electronic Journal of Combinatorics
 | тип      = Dynamic surveys
 | год      = 2006
 | месяц    = 
 | число    = 
 | том      = 
 | номер    =DS22 
 | страницы = 
 | ref = van Dam, Koolen and Tanaka
 | issn     = 
}}
* {{книга 
|автор=Lauri J., Scapelatto R.
|заглавие=Topics in Graph Automorphisms and Reconstruction 
|язык=en 
|место=Combridge
|издательство=Combridge University Press
|год=2016
|издание = 2nd edition
|страниц=188
|isbn=
|ref= Lauri and Scapelatto
}}

{{Добротная статья|Математика}}

[[Категория:Алгебраическая теория графов]]
[[Категория:Регулярные графы]]