Перегляд вихідного коду сторінки Сильно регулярний граф

{{Види графів за їхніми автоморфізмами}}
У [[Теорія графів|теорії графів]] '''сильно регулярний граф'''&nbsp;— граф, що має такі властивості: Нехай <math>G=(V,E)</math>&nbsp;— [[регулярний граф]] з <math>v</math> вершинами і степенем <math>k</math>. <math>G</math> називають '''сильно регулярним''', якщо існують [[Цілі числа|цілі]] <math>\lambda</math> і <math>\mu</math> такі, що:

* будь-які дві [[Окіл (теорія графів)|суміжні вершини]] мають <math>\lambda</math> спільних сусідів;
* будь-які дві несуміжні вершини мають <math>\mu</math> спільних сусідів.

Графи такого виду іноді позначають як <math>srg(v,k,\lambda, \mu)</math>.

Деякі автори виключають графи, які задовольняють умовам тривіально, а саме графи, які є незв'язним об'єднанням одного або більше [[Повний граф|повних графів]] одного розміру{{Sfn|Brouwer|2012|c=101}}{{Sfn|Godsil|2001|c=218}}, і їх [[Доповнення графа|доповнення]], [[Граф Турана|графи Турана]].

Сильно регулярний граф є [[Дистанційно-регулярний граф|дистанційно-регулярним]] з діаметром <math>2</math>, але тільки в тому випадку, коли <math>\mu</math> не дорівнює нулю.

== Властивості ==
* Чотири параметри в <math>srg(v,k,\lambda, \mu)</math> не є незалежними і мають задовольняти такій умові:

: <math>(v-k-1)\mu = k(k-\lambda-1)</math>

Цю умову можна отримати дуже просто, якщо підрахувати аргументи так:

:* Уявімо, що вершини графа лежать на трьох рівнях. Виберемо будь-яку вершину як корінь, рівень <math>0</math>. Тоді її <math>k</math> сусідніх вершин лежать на рівні <math>1</math>, а решта лежать на рівні <math>2</math>.
:* Вершини рівня <math>1</math> пов'язані безпосередньо з коренем, а тому вони повинні мати <math>\lambda</math> інших сусідів, які є сусідами кореня, і ці сусіди повинні також лежати на рівні <math>1</math>. Оскільки кожна вершина має степінь <math>k</math>, є <math>k-\lambda-1</math> ребер, що з'єднують кожну вершину рівня <math>1</math> з рівнем <math>2</math>.
:* Вершини рівня <math>2</math> не пов'язані безпосередньо з коренем, а тому вони повинні мати <math>\mu</math> спільних сусідів з коренем, і всі ці сусіди повинні лежати на рівні <math>1</math>. Таким чином, <math>\mu</math> вершин рівня <math>1</math> пов'язані з кожною вершиною рівня <math>2</math> і кожна з <math>k</math> вершин на рівні 1 пов'язана з <math>k-\lambda-1</math> вершин на рівні <math>2</math>. Отримуємо, що число вершин на рівні <math>2</math> дорівнює <math>k(k-\lambda-1)/\mu</math>.
:* Повне число вершин на всіх трьох рівнях, таким чином, дорівнює <math>v = 1 + k + k(k-\lambda-1)/\mu</math> і, після перетворення, маємо <math>(v-k-1)\mu = k(k-\lambda-1)</math>.
* Нехай <math>\mathbf I</math> позначає одиничну матрицю (порядку <math>v</math>) і нехай <math>\mathbf J</math> позначає матрицю, всі елементи якої рівні <math>1</math>. [[Матриця суміжності]] <math>\mathbf A</math> сильно регулярного графа має такі властивості:
** <math>\mathbf A \mathbf J = k \mathbf J</math><br/>(Це тривіальне перефразування вимоги рівності степеня вершин числу <math>k</math>).
** <math>{\mathbf A}^{2} + (\mu-\lambda){\mathbf A} + (\mu-k){\mathbf I} = \mu {\mathbf J}</math><br/>(Перший член, <math>{\mathbf A}^{2}</math>, дає число двокрокових шляхів з будь-якої вершини до всіх вершин. Другий член, <math>(\mu-\lambda){\mathbf A}</math>, відповідає безпосередньо пов'язаним ребрам. Третій член,<math>(\mu-k){\mathbf I}</math>, відповідає тривіальним парам, коли вершини в парі ті ж самі).
* Граф має рівно три [[Власні вектори та власні значення|власних значень]]:
** <math>k</math>, [[Кратність (математика)|кратність]] якого дорівнює 1
** <math>\frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]</math>, кратність якого дорівнює <math>\frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]</math>
** <math>\frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]</math>, кратність якого дорівнює <math>\frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]</math>
* Сильно регулярні графи, для яких <math>2k+(v-1)(\lambda-\mu) = 0</math>, називають [[Конференсний граф|конференсними]] зважаючи на їх зв'язки зі симетричними [[Конференс-матриця|конференсними матрицями]]. Число незалежних параметрів цих графів скорочується до одного&nbsp;— <math>srg\left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right)</math>.
* Сильно регулярні графи, для яких <math>2k+(v-1)(\lambda-\mu) \ne 0</math>, мають цілочисельні власні значення з нерівними кратностями.
* [[Доповнення графа|Доповнення]] <math>srg(v,k, \lambda, \mu)</math> також сильно регулярне&nbsp;— це <math>srg(v,v-k-1,v-2-2k+\mu,v-2k+\lambda)</math>.

== Приклади ==
[[Файл:Paley13.svg|міні|240x240пкс|[[Граф Пелі]] 13-го порядку, сильно регулярний граф із параметрами srg(13,6,2,3).]]
* <math>srg(5,2,0,1) </math>&nbsp;— [[Циклічний граф|цикл]] довжини 5;
* <math>srg(10,3,0,1)</math>&nbsp;— [[граф Петерсена]];
* <math>srg(16,5,0,2)</math>&nbsp;— [[граф Клебша]];
* <math>srg(16,6,2,2)</math>&nbsp;— [[граф Шрікханде]], який не є [[Дистанційно-транзитивний граф|дистанційно-транзитивним]];
* <math>srg(27,10,1,5)</math>&nbsp;— [[реберний граф]] [[Узагальнений чотирикутник|узагальненого чотирикутника]] <math>GQ(2,4)</math>;
* <math>srg(27,16,10,8)</math>&nbsp;— [[граф Шлефлі]]<ref>{{MathWorld|urlname=SchlaefliGraph|title=Schläfli graph}}</ref>;
* <math>srg(28,12,6,4)</math>&nbsp;— [[графи Чана]];
* <math>srg(50,7,0,1)</math>&nbsp;— [[граф Гофмана — Синглтона]];
* <math>srg(56,10,0,2)</math>&nbsp;— [[граф Гевірца]];
* <math>srg(77,16,0,4)</math>&nbsp;— [[Граф M22|граф M<sub>22</sub>]];
* <math>srg(81,20,1,6)</math>&nbsp;— [[граф Брауера — Хемерса]];
* <math>srg(100,22,0,6)</math>&nbsp;— [[граф Гіґмана — Сімса]];
* <math>srg(162,56,10,24)</math>&nbsp;— {{Не перекладено|локальний граф Маклафліна||en|Local McLaughlin graph}};
* <math>srg(q,\frac{q-1}{2},\frac{q-5}{4},\frac{q-1}{4})</math>&nbsp;— [[граф Пелі]] порядку <math>q</math>;
* <math>srg(n^2,2n-2,n-2,2)</math>&nbsp;— <math>n \times n</math> квадратний [[туровий граф]].

Сильно регулярний граф називається '''простим''', якщо і граф, і його доповнення зв'язні. Всі наведені вище графи прості, оскільки в іншому випадку <math>\mu=0</math> або <math>\mu=k</math>.

=== Графи Мура ===
{{Докладніше|Граф Мура}}
Сильно регулярні графи з <math>\lambda=0</math> [[Граф без трикутників|не містять трикутників]]. Крім повних графів з числом вершин менше 3 і всіх повних [[Двочастковий граф|двочасткових графів]] сім наведених вище&nbsp;— це всі відомі графи цього виду. Сильно регулярні графи з <math>\lambda=0</math> і <math>\mu=1</math>&nbsp;— це [[Клітка (теорія графів)|графи Мура]] з [[Обхват (теорія графів)|обхватом]] 5. Знову ж, три графи, наведені вище, з параметрами <math>srg(5,2,0,1)</math>, <math>srg(10,3,0,1)</math> і <math>srg(50,7,0,1)</math>— це єдині відомі графи цього виду. Єдина інша можлива множина параметрів, відповідна графам Мура&nbsp;— це <math>srg(3250,57,0,1)</math>. Невідомо, чи існує такий граф, і якщо існує, чи єдиний він.

== Див. також ==
* {{Не перекладено|Матриця суміжності Зайделя||en|Seidel adjacency matrix}}
* [[Два-граф]]
* [[Граф Геймса]]
* [[Конференційний граф]]

== Примітки ==
{{Reflist}}

== Література ==
* {{Книга
|автор = Brouwer A.E., Cohen A.M., Neumaier A.
|заголовок = Distance Regular Graphs
|мова = en
|посилання = 
|відповідальний = 
|місце = Berlin, New York
|видавництво = Springer-Verlag
|рік = 1989
|том = 
|сторінок = 
|сторінки = 
|ISBN = 3-540-50619-5
|doi = 
|ref = Brouwer
}}
* {{Книга
|автор = Brouwer A.E., Haemers W.H.
|частина = 
|посилання частина = 
|заголовок = Spectra of Graphs
|оригінал = 
|мова = en
|посилання = 
|відповідальний = 
|видання = 
|місце = New York
|видавництво = Springer-Verlag
|рік = 2012
|том = 418
|сторінки = 
|сторінок = 
|серія = Universitext
|ISBN = 978-1-4614-1938-9
|doi = 
|тираж = 
|ref = Brouwer
}}
* {{Книга
|автор = Godsil C., Royle G
|заголовок = Algebraic Graph Theory
|мова = en
|посилання = 
|відповідальний = 
|місце = New York
|видавництво = Springer-Verlag
|рік = 2001
|том = 
|сторінок = 
|сторінки = 
|ISBN = 0-387-95241-1
|doi = 
|ref = Godsil
}}

== Посилання ==
* ''[[Ерік Вайсстайн|Eric W. Weisstein]]'', [http://mathworld.wolfram.com/StronglyRegularGraph.html Стаття Mathworld з багатьма прикладами.]
* {{Не перекладено|Гордон Ройл||en|Gordon Royle}}, [https://web.archive.org/web/20080503090520/http://people.csse.uwa.edu.au/gordon/remote/srgs/ Список великих графів і сімейств.]
* {{Не перекладено|Андрес Еверт Брауер|Andries E. Brouwer|en|Andries E. Brouwer}}, [http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html Параметри сильно регулярних графів.]
* {{Не перекладено|Бренден Дамін Маккай|Brendan McKay|en|Brendan McKay}}, [http://cs.anu.edu.au/~bdm/data/graphs.html Колекція графів.]
* Ted Spence, [http://www.maths.gla.ac.uk/~es/srgraphs.php Strongly regular graphs on at most 64 vertices.]
[[Категорія:Регулярні графи]]
[[Категорія:Види графів]]
[[Категорія:Алгебраїчна теорія графів]]