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

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

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

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

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

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

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

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

Свойства[править | править вики-текст]

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

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

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

Примеры[править | править вики-текст]

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

Графы Мура[править | править вики-текст]

Сильно регулярные графы с λ=0 не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с λ=0 и μ=1 являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами (5,2,0,1), (10,3,0,1) и (50,7,0,1), являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это (3250,57,0,1). Неизвестно, существует ли такой граф, и если существует, единственный ли он.

Смотрите также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101
  2. Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag New York, 2001, p. 218.
  3. Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

Ссылки[править | править вики-текст]

Внешние ссылки[править | править вики-текст]