WikiSort.ru - Не сортированное

В теории графов сильно регулярным графом называется граф, обладающий следующими свойствами:

Пусть G = (V,E) — регулярный граф с v вершинами и степенью k. Говорят, что G является сильно регулярным, если существуют целые λ и μ такие, что:

• Любые две смежные вершины имеют λ общих соседей.

• Любые две несмежные вершины имеют μ общих соседей.

Графы такого вида иногда обозначаются как srg(v,k,λ,μ).

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

Сильно регулярный граф является дистанционно-регулярным с диаметром 2, но только в том случае, когда μ не равно нулю.

Свойства

• Четыре параметра в srg(v,k,λ,μ) не являются независимыми и должны удовлетворять следующему условию:

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

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

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

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

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

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

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

• Дополнение 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).
• Граф Шрикханде — это 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).
• Граф Пэли порядка q — это srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).
• n × n квадратный ладейный граф — это srg(n², 2n − 2, n − 2, 2).

Сильно регулярный граф называется простым, если и граф, и его дополнение связны. Все вышеприведённые графы просты, так как в противном случае μ=0 или μ=k.

См. также

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

Примечания

Литература

• 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.