Граф Шрікханде — граф, знайдений [en] 1959 року. Граф сильно регулярний, має 16 вершин і 48 ребер і кожна вершина має степінь 6. Кожна пара вузлів має рівно двох спільних сусідів, незалежно від того, пов'язана ця пара ребром чи ні.
Граф Шрікханде | |
---|---|
Названо на честь | Ш. Ш. Шрікханде |
(Вершин) | 16 |
(Ребер) | 48 |
(Радіус) | 2 |
(Діаметр) | 2 |
(Обхват) | 3 |
(Автоморфізм) | 192 |
Хроматичне число | 4 |
Хроматичний індекс | 6 |
Число черг | 3 |
Властивості | гамільтонів симетричний ейлерів цілий |
Побудова
Граф Шрікханде можна побудувати як граф Келі, в якому множина вершин — це , а дві вершини пов'язані тоді й лише тоді, коли різниця міститься в .
Властивості
У графі Шрікханде будь-які дві вершини I і J мають двох різних спільних сусідів (за винятком самих вершин I і J), що виконується незалежно від того, суміжні I і J, чи ні. Іншими словами, граф сильно регулярний та його параметрами є: {16,6,2,2}, тобто . З цієї рівності випливає, що граф асоційований із симетричними зрівноваженими неповними блок-схемами (англ. Balanced Incomplete Block Designs, BIBD). Такі ж параметри має 4×4 туровий граф, тобто реберний граф L(K4,4) повного двочасткового графа K4,4. Останній граф є єдиним реберним графом L(Kn, n), якого параметри сильної регулярності не визначають єдиним чином, і граф ділить їх з іншим графом, а саме графом Шрікханде (який не є туровим графом).
Граф Шрікханде локально шестикутний. Тобто сусіди кожної вершини утворюють цикл із шести вершин. Як і будь-який локально циклічний граф, граф Шрікханде є 1-вимірним кістяком тріангуляції Вітні деякої поверхні. У разі графа Шрікханде ця поверхня — тор, у якому кожна вершина оточена шістьма трикутниками. Таким чином, граф Шрікханде — це тороїдальний граф. Вкладення утворює регулярне відображення в тор з 32 трикутними гранями. Кістяк дуального графа цього відображення (як вкладеного в тор) — граф Діка, кубічний симетричний граф.
Граф Шрікханде не є дистанційно-транзитивним. Це найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним.
Група автоморфізмів графа Шрікханде має порядок 192. Вона діє транзитивно на вершини, на ребра та дуги графа. Тому граф Шрікханде є симетричним графом.
Характеристичний многочлен графа Шрікханде дорівнює . Отже, граф Шрікханде є цілим графом — його спектр складається повністю з цілих чисел.
Граф має книжкову товщину 4 та число черг 3 .
Галерея
- Граф Шрікханде є .
- графа Шрікханде дорівнює 4.
- графа Шрікханде дорівнює 6.
- Граф Шрікханде, намальований симетрично.
- Граф Шрікханде .
Див. також
Примітки
- Weisstein, Eric W. Граф Шрікханде(англ.) на сайті Wolfram MathWorld.
- Shrikhande, 1959, с. 781–798.
- Harary, 1972, с. 79.
- Brouwer, Cohen, Neumaier, 1989, с. 104–105, 136.
- Wolz, 2018.
Література
- Shrikhande S. S. The uniqueness of the L2 association scheme // Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 781–798. — DOI: .
- Frank Harary. Graph Theory. — Massachusetts : Addison-Wesley, 1972.
- Харари Ф. Теория графов. — М. : Мир, 1973.
- , Cambridge University Press, ISBN
{{}}
: Пропущений або порожній|title=
() - Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. — New York : Springer-Verlag, 1989. — С. 104–105, 136.
- Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis)
Посилання
- The Shrikhande Graph Пітер Кемерон (Peter Cameron), серпень 2010. Архівовано листопад 24, 2010 на сайті Wayback Machine.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Graf Shrikhande graf znajdenij en 1959 roku Graf silno regulyarnij maye 16 vershin i 48 reber i kozhna vershina maye stepin 6 Kozhna para vuzliv maye rivno dvoh spilnih susidiv nezalezhno vid togo pov yazana cya para rebrom chi ni Graf ShrikhandeNazvano na chest Sh Sh ShrikhandeVershin 16Reber 48Radius 2Diametr 2Obhvat 3Avtomorfizm 192Hromatichne chislo 4Hromatichnij indeks 6Chislo cherg 3Vlastivosti gamiltoniv simetrichnij ejleriv cilijPobudovaGraf Shrikhande mozhna pobuduvati yak graf Keli v yakomu mnozhina vershin ce Z 4 Z 4 displaystyle mathbb Z 4 times mathbb Z 4 a dvi vershini pov yazani todi j lishe todi koli riznicya mistitsya v 1 0 0 1 1 1 displaystyle pm 1 0 pm 0 1 pm 1 1 VlastivostiU grafi Shrikhande bud yaki dvi vershini I i J mayut dvoh riznih spilnih susidiv za vinyatkom samih vershin I i J sho vikonuyetsya nezalezhno vid togo sumizhni I i J chi ni Inshimi slovami graf silno regulyarnij ta jogo parametrami ye 16 6 2 2 tobto l m 2 displaystyle lambda mu 2 Z ciyeyi rivnosti viplivaye sho graf asocijovanij iz simetrichnimi zrivnovazhenimi nepovnimi blok shemami angl Balanced Incomplete Block Designs BIBD Taki zh parametri maye 4 4 turovij graf tobto rebernij graf L K4 4 povnogo dvochastkovogo grafa K4 4 Ostannij graf ye yedinim rebernim grafom L Kn n yakogo parametri silnoyi regulyarnosti ne viznachayut yedinim chinom i graf dilit yih z inshim grafom a same grafom Shrikhande yakij ne ye turovim grafom Graf Shrikhande lokalno shestikutnij Tobto susidi kozhnoyi vershini utvoryuyut cikl iz shesti vershin Yak i bud yakij lokalno ciklichnij graf graf Shrikhande ye 1 vimirnim kistyakom triangulyaciyi Vitni deyakoyi poverhni U razi grafa Shrikhande cya poverhnya tor u yakomu kozhna vershina otochena shistma trikutnikami Takim chinom graf Shrikhande ce toroyidalnij graf Vkladennya utvoryuye regulyarne vidobrazhennya v tor z 32 trikutnimi granyami Kistyak dualnogo grafa cogo vidobrazhennya yak vkladenogo v tor graf Dika kubichnij simetrichnij graf Graf Shrikhande ne ye distancijno tranzitivnim Ce najmenshij distancijno regulyarnij graf yakij ne ye distancijno tranzitivnim Grupa avtomorfizmiv grafa Shrikhande maye poryadok 192 Vona diye tranzitivno na vershini na rebra ta dugi grafa Tomu graf Shrikhande ye simetrichnim grafom Harakteristichnij mnogochlen grafa Shrikhande dorivnyuye x 6 x 2 6 x 2 9 displaystyle x 6 x 2 6 x 2 9 Otzhe graf Shrikhande ye cilim grafom jogo spektr skladayetsya povnistyu z cilih chisel Graf maye knizhkovu tovshinu 4 ta chislo cherg 3 GalereyaGraf Shrikhande ye grafa Shrikhande dorivnyuye 4 grafa Shrikhande dorivnyuye 6 Graf Shrikhande namalovanij simetrichno Graf Shrikhande Div takozhGrafi ChanaPrimitkiWeisstein Eric W Graf Shrikhande angl na sajti Wolfram MathWorld Shrikhande 1959 s 781 798 Harary 1972 s 79 Brouwer Cohen Neumaier 1989 s 104 105 136 Wolz 2018 LiteraturaShrikhande S S The uniqueness of the L2 association scheme Annals of Mathematical Statistics 1959 T 30 S 781 798 DOI 10 1214 aoms 1177706207 Frank Harary Graph Theory Massachusetts Addison Wesley 1972 Harari F Teoriya grafov M Mir 1973 Cambridge University Press ISBN 0 521 43594 3 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Propushenij abo porozhnij title dovidka Brouwer A E Cohen A M Neumaier A Distance Regular Graphs New York Springer Verlag 1989 S 104 105 136 Jessica Wolz Engineering Linear Layouts with SAT University of Tubingen 2018 Master Thesis PosilannyaThe Shrikhande Graph Piter Kemeron Peter Cameron serpen 2010 Arhivovano listopad 24 2010 na sajti Wayback Machine