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

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

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

Пусть 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).

    • (Первый член, , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, , соответствует непосредственно связанным рёбрам. Третий член,, соответствует тривиальным парам, когда вершины в паре те же самые).
  • Граф имеет в точности три собственных значения:
    • , кратность[en] которого равна 1
    • , кратность которого равна
    • , кратность которого равна
  • Сильно регулярные графы, для которых , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — .
  • Сильно регулярные графы, для которых , имеют целочисленные собственные значения с неравными кратностями.
  • Дополнение 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. — New York: Springer-Verlag, 2001. — С. 218.
  3. Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

Литература[править | править вики-текст]

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