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

В теории графов сильно регулярным графом называется граф, обладающий следующими свойствами:
Пусть G = (V,E) — регулярный граф с v вершинами и степенью k. Говорят, что G является сильно регулярным, если существуют целые λ и μ такие, что:
- Любые две смежные вершины имеют λ общих соседей.
- Любые две несмежные вершины имеют μ общих соседей.
Графы такого вида иногда обозначаются как srg(v,k,λ,μ).
Некоторые авторы исключают графы, которые удовлетворяют условиям тривиально, а именно графы, являющиеся несвязным объединением одного или более полных графов одного размера[1][2], и их дополнения, графы Турана.
Сильно регулярный граф является дистанционно-регулярным с диаметром 2, но только в том случае, когда μ не равно нулю.
Свойства[править | править код]
- Четыре параметра в srg(v,k,λ,μ) не являются независимыми и должны удовлетворять следующему условию:
Это условие можно получить очень просто, если подсчитать аргументы следующим образом:
- Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень 0. Тогда её k соседних вершин лежат на уровне 1, а все оставшиеся лежат на уровне 2.
- Вершины уровня 1 связаны непосредственно с корнем, а потому они должны иметь других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне 1. Поскольку каждая вершина имеет степень k, имеется рёбер, соединяющих каждую вершину уровня 1 с уровнем 2.
- Вершины уровня 2 не связаны непосредственно с корнем, а потому они должны иметь общих соседей с корнем, и все эти соседи должны лежать на уровне 1. Таким образом, вершин уровня 1 связаны с каждой вершиной уровня 2 и каждая из k вершин на уровне 1 связана с вершин на уровне 2. Получаем, что число вершин на уровне 2 равно .
- Полное число вершин на всех трёх уровнях, таким образом, равно и после преобразования, получим .
- Пусть I обозначает единичную матрицу (порядка v) и пусть J обозначает матрицу, все элементы которой равны 1. Матрица смежности A сильно регулярного графа имеет следующие свойства:
(Это тривиальное перефразирование требования равенства степени вершин числу k).
(Первый член, , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, , соответствует непосредственно связанным рёбрам. Третий член,, соответствует тривиальным парам, когда вершины в паре те же самые).
- Граф имеет в точности три собственных значения:
- Сильно регулярные графы, для которых , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — .
- Сильно регулярные графы, для которых , имеют целочисленные собственные значения с неравными кратностями.
- Дополнение srg(v,k,λ,μ) также сильно регулярно — это srg(v, v−k−1, v−2−2k+μ, v−2k+λ).
Примеры[править | править код]
- Цикл длины 5 — это srg(5,2,0,1).
- Граф Петерсена — это srg(10,3,0,1).
- Граф Клебша — это srg(16,5,0,2).
- Граф Шрикханде[en] — это srg(16,6,2,2), который не является дистанционно-транзитивным.
- Рёберный граф обобщённого четырёхугольника GQ(2,4) — это srg(27,10,1,5).
- Граф Шлефли — это srg(27,16,10,8)[3]
- Графы Чанга[en] — это srg(28,12,6,4).
- Граф Хоффмана–Синглтона — это srg(50,7,0,1).
- Граф Симса–Гевиртца[en] — это (56,10,0,2).
- Граф M22[en] — это srg(77,16,0,4).
- Граф Браувера–Хамерса[en] — это srg(81,20,1,6).
- Граф Хигмана–Симса[en] — это srg(100,22,0,6).
- Локальный граф МакЛафлина[en] — это srg(162,56,10,24).
- Граф Пейли of order q — это srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).
- n × n квадратный ладейный граф — это srg(n2, 2n − 2, n − 2, 2).
Сильно регулярный граф называется простым если и граф, и его дополнение связны. Все вышеприведённые графы просты, так как в противном случае μ=0 или μ=k.
Графы Мура[править | править код]
Сильно регулярные графы с λ=0 не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с λ=0 и μ=1 являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами (5,2,0,1), (10,3,0,1) и (50,7,0,1), являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это (3250,57,0,1). Неизвестно, существует ли такой граф, и если существует, единственный ли он.
Смотрите также[править | править код]
Примечания[править | править код]
- ↑ Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101 Архивировано 16 марта 2012 года.
- ↑ Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — С. 218.
- ↑ Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.
Литература[править | править код]
- A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
- Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1
Ссылки[править | править код]
- Эрик В. Вайсштайн[en], Статья Mathworld с большим числом примеров.
- Гордон Ройл[en], Список больших графов и семейств.
- Andries E. Brouwer[en], Параметры сильно регулярных графов.
- Brendan McKay[en], Коллекция графов.
- Ted Spence, Strongly regular graphs on at most 64 vertices.
Для улучшения этой статьи желательно:
|