Сильно регулярный граф

Сильно регулярный граф — вариация понятия регулярный граф.

Граф Пэли 13-го порядка, сильно регулярный граф с параметрами srg(13,6,2,3).

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

Пусть $G=(V,E)$$G=(V,E)$  — регулярный граф с $v$$v$  вершинами и степенью $k$$k$ . Говорят, что $G$$G$  является сильно регулярным, если существуют целые $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  и $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  такие, что:

• Любые две смежные вершины имеют $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  общих соседей.

• Любые две несмежные вершины имеют $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  общих соседей.

ЗамечанияПравить

• Графы описанного типа иногда обозначаются как $srg(v,k,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\mu <!--\; \mu \; -->})$$srg(v,k,\lambda ,\mu )$ .

• Некоторые авторы исключают графы, которые удовлетворяют условиям тривиально, а именно графы, являющиеся несвязным объединением одного или более полных графов одного размера , и их дополнения, графы Турана.

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

• Сильно регулярный граф $srg(v,k,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\mu <!--\; \mu \; -->})$$srg(v,k,\lambda ,\mu )$  является дистанционно-регулярным с диаметром $2$$2$ , только в том случае, когда $\mathrm{\mu <!--\; \mu \; -->}\ne <!--\; \ne \; -->0$$\mu \neq 0$ .

• Четыре параметра в $srg(v,k,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\mu <!--\; \mu \; -->})$$srg(v,k,\lambda ,\mu )$  не являются независимыми и должны удовлетворять следующему условию:

$(v-<!--\; -\; -->k-<!--\; -\; -->1)\mathrm{\mu <!--\; \mu \; -->}=k(k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1)$$(v-k-1)\mu =k(k-\lambda -1)$ 

Это условие можно получить очень просто, если подсчитать аргументы следующим образом:

• Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень $0$$0$ . Тогда её $k$$k$  соседних вершин лежат на уровне $1$$1$ , а все оставшиеся лежат на уровне $2$$2$ .
• Вершины уровня $1$$1$  связаны непосредственно с корнем, а потому они должны иметь $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне $1$$1$ . Поскольку каждая вершина имеет степень $k$$k$ , имеется $k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1$$k-\lambda -1$  рёбер, соединяющих каждую вершину уровня $1$$1$  с уровнем $2$$2$ .
• Вершины уровня $2$$2$  не связаны непосредственно с корнем, а потому они должны иметь $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  общих соседей с корнем, и все эти соседи должны лежать на уровне $1$$1$ . Таким образом, $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  вершин уровня $1$$1$  связаны с каждой вершиной уровня $2$$2$  и каждая из $k$$k$  вершин на уровне 1 связана с $k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1$$k-\lambda -1$  вершин на уровне $2$$2$ . Получаем, что число вершин на уровне $2$$2$  равно $k(k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1)/\mathrm{\mu <!--\; \mu \; -->}$$k(k-\lambda -1)/\mu$ .
• Полное число вершин на всех трёх уровнях, таким образом, равно $v=1+k+k(k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1)/\mathrm{\mu <!--\; \mu \; -->}$$v=1+k+k(k-\lambda -1)/\mu$  и после преобразования, получим $(v-<!--\; -\; -->k-<!--\; -\; -->1)\mathrm{\mu <!--\; \mu \; -->}=k(k-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->1)$$(v-k-1)\mu =k(k-\lambda -1)$ .

• Пусть $\mathbf{I}$$\mathbf {I}$  обозначает единичную матрицу (порядка $v$$v$ ) и пусть $\mathbf{J}$$\mathbf {J}$  обозначает матрицу, все элементы которой равны $1$$1$ . Матрица смежности $\mathbf{A}$${\mathbf A}$  сильно регулярного графа имеет следующие свойства:
  • $\mathbf{A}\mathbf{J}=k\mathbf{J}$$\mathbf {A} \mathbf {J} =k\mathbf {J}$ 
    (Это тривиальное перефразирование требования равенства степени вершин числу $k$$k$ ).
  • ${\mathbf{A}}^2+(\mathrm{\mu <!--\; \mu \; -->}-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})\mathbf{A}+(\mathrm{\mu <!--\; \mu \; -->}-<!--\; -\; -->k)\mathbf{I}=\mathrm{\mu <!--\; \mu \; -->}\mathbf{J}$${\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf {J} }$ 
    (Первый член, ${\mathbf{A}}^2$${\mathbf {A} }^{2}$ , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, $(\mathrm{\mu <!--\; \mu \; -->}-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})\mathbf{A}$$(\mu -\lambda ){\mathbf {A} }$ , соответствует непосредственно связанным рёбрам. Третий член,$(\mathrm{\mu <!--\; \mu \; -->}-<!--\; -\; -->k)\mathbf{I}$$(\mu -k){\mathbf {I} }$ , соответствует тривиальным парам, когда вершины в паре те же самые).

• Граф имеет в точности три собственных значения:
  • $k$$k$ , кратность^[en] которого равна 1
  • $\frac{1}{2}\left[(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})+\sqrt{(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}{)}^2+4(k-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}\right]$${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ , кратность которого равна $\frac{1}{2}\left[(v-<!--\; -\; -->1)-<!--\; -\; -->\frac{2k+(v-<!--\; -\; -->1)(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}{\sqrt{(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}{)}^2+4(k-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}}\right]$${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$ 
  • $\frac{1}{2}\left[(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})-<!--\; -\; -->\sqrt{(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}{)}^2+4(k-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}\right]$${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ , кратность которого равна $\frac{1}{2}\left[(v-<!--\; -\; -->1)+\frac{2k+(v-<!--\; -\; -->1)(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}{\sqrt{(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}{)}^2+4(k-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})}}\right]$${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$ 

• Сильно регулярные графы, для которых $2k+(v-<!--\; -\; -->1)(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})=0$$2k+(v-1)(\lambda -\mu )=0$ , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — $srg\left(v,\frac{v-<!--\; -\; -->1}{2},\frac{v-<!--\; -\; -->5}{4},\frac{v-<!--\; -\; -->1}{4}\right)$$srg\left(v,{\frac {v-1}{2}},{\frac {v-5}{4}},{\frac {v-1}{4}}\right)$ .

• Сильно регулярные графы, для которых $2k+(v-<!--\; -\; -->1)(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->})\ne <!--\; \ne \; -->0$$2k+(v-1)(\lambda -\mu )\neq 0$ , имеют целочисленные собственные значения с неравными кратностями.

• Дополнение $srg(v,k,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\mu <!--\; \mu \; -->})$$srg(v,k,\lambda ,\mu )$  также сильно регулярно — это $srg(v,v-<!--\; -\; -->k-<!--\; -\; -->1,v-<!--\; -\; -->2-<!--\; -\; -->2k+\mathrm{\mu <!--\; \mu \; -->},v-<!--\; -\; -->2k+\mathrm{\lambda <!--\; \lambda \; -->})$$srg(v,v-k-1,v-2-2k+\mu ,v-2k+\lambda )$ .

ПримерыПравить

• $srg(5,2,0,1)$$srg(5,2,0,1)$  — Цикл длины 5;
• $srg(10,3,0,1)$$srg(10,3,0,1)$  — Граф Петерсена;
• $srg(16,5,0,2)$$srg(16,5,0,2)$  — Граф Клебша;
• $srg(16,6,2,2)$$srg(16,6,2,2)$  — Граф Шрикханде , который не является дистанционно-транзитивным;
• $srg(27,10,1,5)$$srg(27,10,1,5)$  — Рёберный граф обобщённого четырёхугольника $GQ(2,4)$$GQ(2,4)$ ;
• $srg(27,16,10,8)$$srg(27,16,10,8)$  — Граф Шлефли ;
• $srg(28,12,6,4)$$srg(28,12,6,4)$  — Графы Чана;
• $srg(50,7,0,1)$$srg(50,7,0,1)$  — Граф Хоффмана-Синглтона;
• $srg(56,10,0,2)$$srg(56,10,0,2)$  — Граф Гевирца;
• $srg(77,16,0,4)$$srg(77,16,0,4)$  — Граф M22;
• $srg(81,20,1,6)$$srg(81,20,1,6)$  — Граф Брауэра — Хемерса;
• $srg(100,22,0,6)$$srg(100,22,0,6)$  — Граф Хигмана — Симса;
• $srg(162,56,10,24)$$srg(162,56,10,24)$  — Локальный граф МакЛафлина^[en];
• $srg(q,\frac{q-<!--\; -\; -->1}{2},\frac{q-<!--\; -\; -->5}{4},\frac{q-<!--\; -\; -->1}{4})$$srg(q,{\frac {q-1}{2}},{\frac {q-5}{4}},{\frac {q-1}{4}})$  — Граф Пэли порядка $q$$q$ ;
• $srg(n^2,2n-<!--\; -\; -->2,n-<!--\; -\; -->2,2)$$srg(n^{2},2n-2,n-2,2)$  — $n\times <!--\; \times \; -->n$$n\times n$  квадратный ладейный граф .

Сильно регулярный граф называется простым, если и граф, и его дополнение связны. Все вышеприведённые графы просты, так как в противном случае $\mathrm{\mu <!--\; \mu \; -->}=0$$\mu =0$  или $\mathrm{\mu <!--\; \mu \; -->}=k$$\mu =k$ .

Графы МураПравить

Сильно регулярные графы с $\mathrm{\lambda <!--\; \lambda \; -->}=0$$\lambda =0$  не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с $\mathrm{\lambda <!--\; \lambda \; -->}=0$$\lambda =0$  и $\mathrm{\mu <!--\; \mu \; -->}=1$$\mu =1$  являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами $srg(5,2,0,1)$$srg(5,2,0,1)$ , $srg(10,3,0,1)$$srg(10,3,0,1)$  и $srg(50,7,0,1)$$srg(50,7,0,1)$ , являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это $srg(3250,57,0,1)$$srg(3250,57,0,1)$ . Неизвестно, существует ли такой граф, и если существует, единственный ли он.

См. такжеПравить

• Матрица смежности Зайделя^[en]

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

• Brouwer A.E., Cohen A.M., Neumaier A. Distance Regular Graphs (англ.). — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5.
• Brouwer A.E., Haemers W.H. Spectra of Graphs (англ.). — New York: Springer-Verlag, 2012. — Vol. 418. — (Universitext). — ISBN 978-1-4614-1938-9.
• Godsil C., Royle G. Algebraic Graph Theory (англ.). — New York: Springer-Verlag, 2001. — ISBN 0-387-95241-1.

СсылкиПравить

• Eric W. Weisstein, Статья Mathworld с большим числом примеров.
• Гордон Ройл^[en], Список больших графов и семейств.
• Andries E. Brouwer^[en], Параметры сильно регулярных графов.
• Brendan McKay^[en], Коллекция графов.
• Ted Spence, Strongly regular graphs on at most 64 vertices.