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

Дистанционно-регулярный граф (англ. distance-regular graph) — такой регулярный граф, у которого для двух любых вершин $v$$v$ и $w$$w$, расположенных на одинаковом расстоянии $j$$j$ друг от друга, справедливо, что количество вершин, инцидентных к $v$$v$ и при этом находящихся на расстоянии $j-<!--\; -\; -->1$$j-1$ от вершины $w$$w$, зависит только от расстояния $j$$j$ между вершинами $v$$v$ и $w$$w$; более того, количество вершин, инцидентных к $v$$v$ и находящихся на расстоянии $j+1$$j+1$ от вершины $w$$w$, также зависит только от расстояния $j$$j$.

Граф Шрикханде — дистанционно-регулярный граф, не являющийся дистанционно-транзитивным

Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде, хотя сам термин появился гораздо позже.

ОпределениеПравить

Определение дистанционно-регулярного графа:

Дистанционно-регулярный граф — это неориентрированный, связанный, ограниченный, регулярный граф $\mathrm{\Gamma <!--\; \Gamma \; -->}=(V,E)$$\Gamma =(V,E)$  валентности $k$$k$  и диаметром $D$$D$ , для которого справедливо следующее. Существуют натуральные числа

$b_0=k{b}_1,\dots <!--\; \dots \; -->,b_{D-<!--\; -\; -->1},c_1=1,c_2,\dots <!--\; \dots \; -->,c_D$$b_{0}=k\quad b_{1},\,\dots \,,\,b_{D-1}\ ,\quad c_{1}=1,\quad c_{2},\,\dots ,\,c_{D}$ 

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

(1) число вершин, инцидентных $u$$u$  и находящихся на расстоянии $j-<!--\; -\; -->1$$j-1$  от $v$$v$ , есть $c_j$$c_{j}$  ($1⩽<!--\; ⩽\; -->j⩽<!--\; ⩽\; -->D$$1\leqslant j\leqslant D$ )

(2) число вершин, инцидентных $u$$u$  и находящихся на расстоянии $j+1$$j+1$  от $v$$v$ , есть $b_j$$b_{j}$  ($0⩽<!--\; ⩽\; -->j⩽<!--\; ⩽\; -->D-<!--\; -\; -->1$$0\leqslant j\leqslant D-1$ ).

Тогда

$\mathrm{\iota <!--\; \iota \; -->}(\mathrm{\Gamma <!--\; \Gamma \; -->})=\left\{\begin{array}{c}k,b_1,\dots <!--\; \dots \; -->,b_{D-<!--\; -\; -->1};1,c_2,\dots <!--\; \dots \; -->,c_D\end{array}\right\}$$\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2},\,\dots ,\,c_{D}\end{Bmatrix}}$ 

есть массив пересечений графа $\mathrm{\Gamma <!--\; \Gamma \; -->}$$\Gamma$  (см. § Массив пересечений), а $a_j,b_j,c_j$$a_{j},\,b_{j},\,c_{j}$  — числа пересечений, где $a_j=k-<!--\; -\; -->b_j-<!--\; -\; -->c_j$$a_{j}=k-b_{j}-c_{j}$ .

Массив пересеченийПравить

Изначально термины «массив пересечений» и «числа пересечений» были введены для описания дистанционно-транзитивных графов.

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

$\left\{w\in <!--\; \in \; -->A:<!--\; :\; -->d(v,w)=j\right\},\left\{w\in <!--\; \in \; -->B:<!--\; :\; -->d(v,w)=j+1\right\},\left\{w\in <!--\; \in \; -->C:<!--\; :\; -->d(v,w)=j-<!--\; -\; -->1\right\}$$\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\}$ 

Если граф $\mathrm{\Gamma <!--\; \Gamma \; -->}$$\Gamma$  дистанционно-транзитивный, то мощности (кардинальные числа) множеств $|A|,|B|,|C|$$|A|,\,|B|,\,|C|$  не зависят от вершин $u,v$$u,v$ , а зависят только от расстояния $j=d(u,v)$$j=d(u,v)$ . Пусть $a_j=|A|,b_j=|B|,c_j=|C|$$a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ , где $a_j,b_j,c_j$$a_{j},\,b_{j},\,c_{j}$  есть числа пересечений.

Определим массив пересечений дистанционно-транзитивного графа $\mathrm{\Gamma <!--\; \Gamma \; -->}$$\Gamma$  как:

$\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}}$ 

Если $k$$k$  — валентность графа, то $b_0=k$$b_{0}=k$  , $c_0=0$$c_{0}=0$  а $c_1=1$$c_{1}=1$ . Более того, $a_i+b_i+c_i=k$$a_{i}+b_{i}+c_{i}=k$ , тогда компактная форма записи массива пересечений есть:

$\mathrm{\iota <!--\; \iota \; -->}(\mathrm{\Gamma <!--\; \Gamma \; -->})=\left\{\begin{array}{c}k,b_1,\dots <!--\; \dots \; -->,b_{D-<!--\; -\; -->1};1,c_2,\dots <!--\; \dots \; -->,c_D\end{array}\right\}$$\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2},\,\dots ,\,c_{D}\end{Bmatrix}}$ 

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

На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности.

Следствием автоморфизма дистанционно-транзитивного графа является его регулярность. Соответственно, для регулярного графа можно определить числа пересечений. С другой стороны для дистанционно-регулярного графа существует комбинаторная регулярность, и для него также определены числа пересечений (см. § Массив пересечений), однако автоморфизм из этого не следует.

Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно. Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков (Г. М. Адельсон-Вельский, Б. Ю. Вейсфелер, А. А. Леман, И. А. Фараджев). Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами.

СвойстваПравить

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

Свойства массива пересечений дистанционно-регулярного графаПравить

Массив пересечений дистанционно-регулярного графа обладает следующими свойствами:

• Каждая вершина имеет постоянное число вершин $k_j$$k_j$ , отстоящих от нее на расстояние $j$$j$ , причем $k_0=1$$k_{0}=1$  и $k_{j+1}=\frac{b_j{k}_j}{c_{j+1}}$$k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$  для всех $j=0,1,\dots <!--\; \dots \; -->,D-<!--\; -\; -->1$$j=0,\,1,\,\dots ,\,D-1$ ;
• Порядок графа $n$$n$  равен $n=k_0+k_1+\dots <!--\; \dots \; -->+k_D$$n=k_{0}+k_{1}+\,\dots \,+k_{D}$ ;
• Число вершин, отстоящих от каждой вершины на расстоянии $j+1$$j+1$ , выражается через числа пересечений как $k_{j+1}=\frac{b_0{b}_1\dots <!--\; \dots \; -->b_j}{c_1{c}_2\dots <!--\; \dots \; -->c_{j+1}}$$k_{j+1}={\frac {b_{0}b_{1}\dots b_{j}}{c_{1}c_{2}\dots c_{j+1}}}$  для всех $j=0,1,\dots <!--\; \dots \; -->,D-<!--\; -\; -->1$$j=0,\,1,\,\dots ,\,D-1$ ;
• Произведение $k_j\cdot <!--\; \cdot \; -->n$$k_{j}\cdot n$  числа вершин, отстоящих от произвольной вершины на расстоянии $j$$j$ , на порядок графа есть четная величина для всех $j=1,2,\dots <!--\; \dots \; -->,D$$j=1,\,2,\,\dots ,\,D$ ;
• Произведение $k_j\cdot <!--\; \cdot \; -->a_j$$k_{j}\cdot a_{j}$  числа вершин, отстоящих от произвольной вершины на расстоянии $j$$j$ , на число пересечений $a_j$$a_{j}$  на есть четная величина для всех $j=1,2,\dots <!--\; \dots \; -->,D$$j=1,\,2,\,\dots ,\,D$ ;
• Произведение $a_1\cdot <!--\; \cdot \; -->n\cdot <!--\; \cdot \; -->k$$a_{1}\cdot n\cdot k$  числа пересечений $a_1$$a_{1}$  на порядок графа и на его валентность делится на 6;
• Для чисел пересечений $c_j$$c_{j}$  справедливо $1⩽<!--\; ⩽\; -->c_1⩽<!--\; ⩽\; -->c_2⩽<!--\; ⩽\; -->\cdots <!--\; \cdots \; -->⩽<!--\; ⩽\; -->c_D$$1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D}$ ;
• Для чисел пересечений $b_j$$b_{j}$  справедливо $k=b_0⩾<!--\; ⩾\; -->b_1⩾<!--\; ⩾\; -->b_2\cdots <!--\; \cdots \; -->⩾<!--\; ⩾\; -->b_{D-<!--\; -\; -->1}$$k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1}$ ;
• Если $i+j⩽<!--\; ⩽\; -->D$$i+j\leqslant D$ , то $c_i⩽<!--\; ⩽\; -->b_j$$c_{i}\leqslant b_{j}$ ;
• Есть такое $i$$i$ , что $k_0⩽<!--\; ⩽\; -->k_1⩽<!--\; ⩽\; -->\cdots <!--\; \cdots \; -->⩽<!--\; ⩽\; -->k_i$$k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i}$  и $k_{i+1}⩾<!--\; ⩾\; -->k_{i+2}⩾<!--\; ⩾\; -->\cdots <!--\; \cdots \; -->⩾<!--\; ⩾\; -->k_D$$k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D}$ .

Матрицы расстояний транзитивно-регулярного графаПравить

Пусть граф $\mathrm{\Gamma <!--\; \Gamma \; -->}(V,E)$$\Gamma (V,E)$  — транзитивно-регулярный диаметра $D$$D$ , $n=|V|$$n=|V|$  есть число его вершин, а $k$$k$  — валентность графа. Определим множество матриц расстояний (англ. distance matrices) размера $n\times <!--\; \times \; -->n$$n\times n$  $\left\{{\mathbf{A}}_0,{\mathbf{A}}_1,\dots <!--\; \dots \; -->,{\mathbf{A}}_D\right\}$$\left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\}$  как :

$\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}}$ 

Свойства матриц расстоянийПравить

Матрицы расстояния обладают следующими свойствами:

• ${\mathbf{A}}_0={\mathbf{I}}_n$$\mathbf {A} _{0}=\mathbf {I} _{n}$ , где ${\mathbf{I}}_n$$\mathbf {I} _{n}$  есть единичная матрица ;
• ${\mathbf{A}}_1=\mathbf{A}$$\mathbf {A} _{1}=\mathbf {A}$  есть обычная матрица смежности графа $\mathrm{\Gamma <!--\; \Gamma \; -->}(V,E)$$\Gamma (V,E)$ ;
• ${\mathbf{A}}_0+{\mathbf{A}}_1+{\mathbf{A}}_2+\cdots <!--\; \cdots \; -->+{\mathbf{A}}_D={\mathbf{J}}_n$$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J} _{n}$ , где ${\mathbf{J}}_n$$\mathbf {J} _{n}$  есть матрица единиц
• $\mathbf{A}{\mathbf{A}}_i=b_{i-<!--\; -\; -->1}{\mathbf{A}}_{i-<!--\; -\; -->1}+a_i{\mathbf{A}}_i+c_{i+1}{\mathbf{A}}_{i+1}$$\mathbf {A} \mathbf {A} _{i}=b_{i-1}\mathbf {A} _{i-1}+a_{i}\mathbf {A} _{i}+c_{i+1}\mathbf {A} _{i+1}$ , где $\left\{\begin{array}{c}k,b_1,\dots <!--\; \dots \; -->,b_{d-<!--\; -\; -->1};1,c_2,\dots <!--\; \dots \; -->,c_d\end{array}\right\}$${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}$  — массив пересечений дистанционно-регулярного графа и $a_i=k-<!--\; -\; -->b_i-<!--\; -\; -->c_i$$a_{i}=k-b_{i}-c_{i}$ 
• существуют такие действительные числа $p_{i,j}^h,(i,j,h=0,1,\dots <!--\; \dots \; -->,D)$$p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\dots ,\,D)$ , что ${\mathbf{A}}_i{\mathbf{A}}_j=\underset{h=0}{\overset{D}{\sum <!--\; \sum \; -->}}{p}_{i,j}^h{\mathbf{A}}_h$$\mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}$  для всех $(i,j=0,1,\dots <!--\; \dots \; -->,D)$$(i,\,j=0,\,1,\,\dots ,\,D)$ , причем $p_{i,j}^h$$p_{i,j}^{h}$  есть число пересечений, то есть количество вершин, находящихся на расстоянии $j$$j$  от вершины $v$$v$  и на расстоянии $i$$i$  от вершины $w$$w$  при условии расстояния $h$$h$  между вершинами $v$$v$  и $w$$w$ . Отметим, что $p_{1,i-<!--\; -\; -->1}^i=c_i$$p_{1,i-1}^{i}=c_{i}$ , $p_{1,i}^i=a_i$$p_{1,i}^{i}=a_{i}$ , $p_{1,i+1}^i=b_i$$p_{1,i+1}^{i}=b_{i}$ .

ЛитератураПравить

• Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
• Biggs N. L. Intersection Matrices for Linear Graphs (англ.) // Combinatorial mathematics and its applications : proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 / edited by D.J.A. Welsh. — London: Academic press, 1971. — P. 15-23.
• Biggs N. L. Algebraic Graph Theory (англ.). — 2nd edition. — Cambridge University Press, 1993. — 205 p.
• 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.
• Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (англ.) / edited by L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Vol. 102. — P. 222—249. — (Encyclopedia of Mathematics and its Applications).
• van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (англ.) // The Electronic Journal of Combinatorics : Dynamic surveys. — 2006. — No. DS22.
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd edition. — Combridge: Combridge University Press, 2016. — 188 p.