Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
Граф Хівуда — ненаправлений граф з 14 вершинами і 21 ребром, названий на честь [en]
Граф Хівуда | |
---|---|
![]() | |
Названо на честь | |
Вершин | 14 |
Ребер | 21 |
Радіус | 3 |
Діаметр | 3 |
Обхват | 6 |
Автоморфізм | 336 (PGL2(7)) |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
Спектр | |
(Число черг) | 2 |
Властивості | Двочастковий Кубічний дистанційно-транзитивний дистанційно-регулярний (тороїдальний) гамільтонів Симетричний |
Комбінаторні властивості
Граф є кубічним і всі цикли в графі містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є (3,6)-кліткою, найменшим кубічним графом з обхватом 6. Він є також дистанційно-транзитивним (дивіться список Фостера), а тому дистанційно-регулярним. У графі Хівуда мається 24 паросполучення, і у всіх паросполучень ребра, що не входять у паросполучення, утворюють гамільтонів цикл. Наприклад, малюнок показує вершини графу, поміщені на окружність і що утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами. Зважаючи симетрії графу будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше.
У графі Хівуда 28 циклів, що містять по шість вершин. Кожен такий цикл не пов'язаний в точності з трьома іншими 6-вершинними циклами. Серед цих трьох циклів кожен є симетричною різницею двох інших. Граф в якому кожна вершина відповідає циклу з 6 вершин графу Хівуда, а дуги відповідають незв'язним парам — це граф Коксетера.
Геометричні та топологічні властивості
Граф Хівуда є тороїдальним графом, тобто його можна відобразити без перетинів на поверхні тора. Як результат утворюється {6,3}2,1 з 7 гексагональними поверхнями. Кожна поверхня мапи суміжна до кожної іншої, а отже карта потребує 7 кольорів. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що не існує карти для тора яка потребує більше 7, а отже карта є максимальною.
Ця карта також може бути вірно реалізована як , єдиний відомий полігон, окрім тетраедра, в якому кожна пара граней сусідні.
Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано, тобто графом, представленим інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано. Граф Хівуда має (число схрещень) рівне 3 і є найменшим кубічним графом з таким числом схрещень. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещень 3. Граф Хівуда є графом одиничних відстаней — його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу.
Алгебраїчні властивості
Група автоморфізмів графу Хівуда ізоморфна проективної лінійної групою PGL22(7), групі порядку 336. Він діє транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є симетричним. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі списком Фостера граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами. Характеристичний многочлен матриці графу Хівуда — . Спектр графу дорівнює
. Це єдиний граф з таким многочленом, який визначається спектром.
Хроматичний многочлен графу дорівнює:
.
Галерея
- [ru].
- Граф Хівуда має число схрещень 3.
- Хроматичний індекс графу Хівуда дорівнює 3.
- Хроматичне число графу Хівуда дорівнює 2.
- Вкладення графу Хівуда в тор(показаний у вигляді квадрата з [en]), розділяє його на сім взаємно-суміжних областей
Примітки
- Weisstein, Eric W. Heawood Graph(англ.) на сайті Wolfram MathWorld.
- . . Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989). Архів оригіналу за 1 серпня 2012. Процитовано 26 січня 2016.
- M. Abreu, R. E. L. Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Graphs and digraphs with all 2-factors isomorphic // [en]. — 2004. — Т. 92, вип. 2. — С. 395—404. — DOI:10.1016/j.jctb.2004.09.004..
- Italo J. Dejter. From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. — arXiv:1002.1960. — DOI:10.1002/jgt.20597..
- Ezra Brown. The many names of (7,3,1) // . — 2002. — Т. 75, вип. 2. — С. 83—94. — DOI:10.2307/3219140. — JSTOR 3219140.
- P. J. Heawood. Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322—339.
- послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. — arXiv:0912.5395..
- J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York : North Holland, 1976. — С. 237. — .
- Royle, G. «Кубические симметричные графы (список Фостера).» [ 20 липня 2008 у Wayback Machine.]
- [en] и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет