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

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

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

Пусть регулярный граф с вершинами и степенью . Говорят, что является сильно регулярным, если существуют целые и такие, что:

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

Графы такого вида иногда обозначаются как .

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

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

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

  • Четыре параметра в   не являются независимыми и должны удовлетворять следующему условию:
 

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

    • Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень  . Тогда её   соседних вершин лежат на уровне  , а все оставшиеся лежат на уровне  .
    • Вершины уровня   связаны непосредственно с корнем, а потому они должны иметь   других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне  . Поскольку каждая вершина имеет степень  , имеется   рёбер, соединяющих каждую вершину уровня   с уровнем  .
    • Вершины уровня   не связаны непосредственно с корнем, а потому они должны иметь   общих соседей с корнем, и все эти соседи должны лежать на уровне  . Таким образом,   вершин уровня   связаны с каждой вершиной уровня   и каждая из   вершин на уровне 1 связана с   вершин на уровне  . Получаем, что число вершин на уровне   равно  .
    • Полное число вершин на всех трёх уровнях, таким образом, равно   и после преобразования, получим  .
  • Пусть   обозначает единичную матрицу (порядка  ) и пусть   обозначает матрицу, все элементы которой равны  . Матрица смежности   сильно регулярного графа имеет следующие свойства:
    •  
      (Это тривиальное перефразирование требования равенства степени вершин числу  ).
    •  
      (Первый член,  , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член,  , соответствует непосредственно связанным рёбрам. Третий член, , соответствует тривиальным парам, когда вершины в паре те же самые).
  • Граф имеет в точности три собственных значения:
    •  , кратность[en] которого равна 1
    •  , кратность которого равна  
    •  , кратность которого равна  
  • Сильно регулярные графы, для которых  , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного —  .
  • Сильно регулярные графы, для которых  , имеют целочисленные собственные значения с неравными кратностями.
  • Дополнение   также сильно регулярно — это  .

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

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

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

Сильно регулярные графы с   не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с   и   являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами  ,   и  , являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это  . Неизвестно, существует ли такой граф, и если существует, единственный ли он.

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

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

  1. Brouwer, 2012, с. 101.
  2. Godsil, 2001, с. 218.
  3. Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

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

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

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