Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




02.10.2022


01.10.2022


29.09.2022


29.09.2022


29.09.2022





Яндекс.Метрика

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

22.01.2021

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

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

  • Любые две смежные вершины имеют λ {displaystyle lambda } общих соседей.
  • Любые две несмежные вершины имеют μ {displaystyle mu } общих соседей.

Графы такого вида иногда обозначаются как s r g ( v , k , λ , μ ) {displaystyle srg(v,k,lambda ,mu )} .

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

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

Свойства

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

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

    • Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень 0 {displaystyle 0} . Тогда её k {displaystyle k} соседних вершин лежат на уровне 1 {displaystyle 1} , а все оставшиеся лежат на уровне 2 {displaystyle 2} .
    • Вершины уровня 1 {displaystyle 1} связаны непосредственно с корнем, а потому они должны иметь λ {displaystyle lambda } других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне 1 {displaystyle 1} . Поскольку каждая вершина имеет степень k {displaystyle k} , имеется k − λ − 1 {displaystyle k-lambda -1} рёбер, соединяющих каждую вершину уровня 1 {displaystyle 1} с уровнем 2 {displaystyle 2} .
    • Вершины уровня 2 {displaystyle 2} не связаны непосредственно с корнем, а потому они должны иметь μ {displaystyle mu } общих соседей с корнем, и все эти соседи должны лежать на уровне 1 {displaystyle 1} . Таким образом, μ {displaystyle mu } вершин уровня 1 {displaystyle 1} связаны с каждой вершиной уровня 2 {displaystyle 2} и каждая из k {displaystyle k} вершин на уровне 1 связана с k − λ − 1 {displaystyle k-lambda -1} вершин на уровне 2 {displaystyle 2} . Получаем, что число вершин на уровне 2 {displaystyle 2} равно k ( k − λ − 1 ) / μ {displaystyle k(k-lambda -1)/mu } .
    • Полное число вершин на всех трёх уровнях, таким образом, равно v = 1 + k + k ( k − λ − 1 ) / μ {displaystyle v=1+k+k(k-lambda -1)/mu } и после преобразования, получим ( v − k − 1 ) μ = k ( k − λ − 1 ) {displaystyle (v-k-1)mu =k(k-lambda -1)} .
  • Пусть I {displaystyle mathbf {I} } обозначает единичную матрицу (порядка v {displaystyle v} ) и пусть J {displaystyle mathbf {J} } обозначает матрицу, все элементы которой равны 1 {displaystyle 1} . Матрица смежности A {displaystyle mathbf {A} } сильно регулярного графа имеет следующие свойства:
    • A J = k J {displaystyle mathbf {A} mathbf {J} =kmathbf {J} }
      (Это тривиальное перефразирование требования равенства степени вершин числу k {displaystyle k} ).
    • A 2 + ( μ − λ ) A + ( μ − k ) I = μ J {displaystyle {mathbf {A} }^{2}+(mu -lambda ){mathbf {A} }+(mu -k){mathbf {I} }=mu {mathbf {J} }}
      (Первый член, A 2 {displaystyle {mathbf {A} }^{2}} , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, ( μ − λ ) A {displaystyle (mu -lambda ){mathbf {A} }} , соответствует непосредственно связанным рёбрам. Третий член, ( μ − k ) I {displaystyle (mu -k){mathbf {I} }} , соответствует тривиальным парам, когда вершины в паре те же самые).
  • Граф имеет в точности три собственных значения:
    • k {displaystyle k} , кратность которого равна 1
    • 1 2 [ ( λ − μ ) + ( λ − μ ) 2 + 4 ( k − μ ) ] {displaystyle {frac {1}{2}}left[(lambda -mu )+{sqrt {(lambda -mu )^{2}+4(k-mu )}} ight]} , кратность которого равна 1 2 [ ( v − 1 ) − 2 k + ( v − 1 ) ( λ − μ ) ( λ − μ ) 2 + 4 ( k − μ ) ] {displaystyle {frac {1}{2}}left[(v-1)-{frac {2k+(v-1)(lambda -mu )}{sqrt {(lambda -mu )^{2}+4(k-mu )}}} ight]}
    • 1 2 [ ( λ − μ ) − ( λ − μ ) 2 + 4 ( k − μ ) ] {displaystyle {frac {1}{2}}left[(lambda -mu )-{sqrt {(lambda -mu )^{2}+4(k-mu )}} ight]} , кратность которого равна 1 2 [ ( v − 1 ) + 2 k + ( v − 1 ) ( λ − μ ) ( λ − μ ) 2 + 4 ( k − μ ) ] {displaystyle {frac {1}{2}}left[(v-1)+{frac {2k+(v-1)(lambda -mu )}{sqrt {(lambda -mu )^{2}+4(k-mu )}}} ight]}
  • Сильно регулярные графы, для которых 2 k + ( v − 1 ) ( λ − μ ) = 0 {displaystyle 2k+(v-1)(lambda -mu )=0} , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — s r g ( v , v − 1 2 , v − 5 4 , v − 1 4 ) {displaystyle srgleft(v,{frac {v-1}{2}},{frac {v-5}{4}},{frac {v-1}{4}} ight)} .
  • Сильно регулярные графы, для которых 2 k + ( v − 1 ) ( λ − μ ) ≠ 0 {displaystyle 2k+(v-1)(lambda -mu ) eq 0} , имеют целочисленные собственные значения с неравными кратностями.
  • Дополнение s r g ( v , k , λ , μ ) {displaystyle srg(v,k,lambda ,mu )} также сильно регулярно — это s r g ( v , v − k − 1 , v − 2 − 2 k + μ , v − 2 k + λ ) {displaystyle srg(v,v-k-1,v-2-2k+mu ,v-2k+lambda )} .

Примеры

  • s r g ( 5 , 2 , 0 , 1 ) {displaystyle srg(5,2,0,1)} — Цикл длины 5;
  • s r g ( 10 , 3 , 0 , 1 ) {displaystyle srg(10,3,0,1)} — Граф Петерсена;
  • s r g ( 16 , 5 , 0 , 2 ) {displaystyle srg(16,5,0,2)} — Граф Клебша;
  • s r g ( 16 , 6 , 2 , 2 ) {displaystyle srg(16,6,2,2)} — Граф Шрикханде , который не является дистанционно-транзитивным;
  • s r g ( 27 , 10 , 1 , 5 ) {displaystyle srg(27,10,1,5)} — Рёберный граф обобщённого четырёхугольника G Q ( 2 , 4 ) {displaystyle GQ(2,4)} ;
  • s r g ( 27 , 16 , 10 , 8 ) {displaystyle srg(27,16,10,8)} — Граф Шлефли ;
  • s r g ( 28 , 12 , 6 , 4 ) {displaystyle srg(28,12,6,4)} — Графы Чанга;
  • s r g ( 50 , 7 , 0 , 1 ) {displaystyle srg(50,7,0,1)} — Граф Хоффмана-Синглтона;
  • s r g ( 56 , 10 , 0 , 2 ) {displaystyle srg(56,10,0,2)} — Граф Симса–Гевиртца;
  • s r g ( 77 , 16 , 0 , 4 ) {displaystyle srg(77,16,0,4)} — Граф M22;
  • s r g ( 81 , 20 , 1 , 6 ) {displaystyle srg(81,20,1,6)} — Граф Браувера–Хамерса;
  • s r g ( 100 , 22 , 0 , 6 ) {displaystyle srg(100,22,0,6)} — Граф Хигмана–Симса;
  • s r g ( 162 , 56 , 10 , 24 ) {displaystyle srg(162,56,10,24)} — Локальный граф МакЛафлина;
  • s r g ( q , q − 1 2 , q − 5 4 , q − 1 4 ) {displaystyle srg(q,{frac {q-1}{2}},{frac {q-5}{4}},{frac {q-1}{4}})} — Граф Пэли порядка q {displaystyle q} ;
  • s r g ( n 2 , 2 n − 2 , n − 2 , 2 ) {displaystyle srg(n^{2},2n-2,n-2,2)} — n × n {displaystyle n imes n} квадратный ладейный граф .

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

Графы Мура

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