YaChudo

Граф Хівуда

Переглядів: 0. Оновлено 28.10.2026.

Граф Хівуда
Названо на честьПерсі Джон Хівуд
Вершин14
Ребер21
Радіус3
Діаметр3
Обхват6
Автоморфізм336 (PGL2(7))
Хроматичне число2
Хроматичний індекс3
Спектр ( − 3 ) 1 ( − 2 ) 6 ( 2 ) 6 3 1 {\displaystyle (-3)^{1}(-{\sqrt {2}})^{6}({\sqrt {2}})^{6}3^{1}}
Число черг2
ВластивостіДвочастковий
Кубічний
дистанційно-транзитивний
дистанційно-регулярний
тороїдальний
гамільтонів
Симетричний

Граф Хівуда — ненаправлений граф з 14 вершинами і 21 ребром, названий на честь Персі Джона Хівуда.[1]

Комбінаторні властивості

Даний граф є кубічним і всі цикли в ньому містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є кліткою-(3,6) з обхватом 6. Він є також дистанційно-транзитивним (дивіться список Фостера), а тому дистанційно-регулярним.[2] У графі Хівуда мається 24 паросполучення та у всіх них ребра, що не входять у паросполучення, утворюють гамільтонів цикл. Наприклад, малюнок показує вершини графу, що поміщені на коло й утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами.[2] Зважаючи на симетрію графу, будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше.[3]

У графі Хівуда 28 циклів, що містять по шість вершин. Кожен такий цикл не пов'язаний в точності з трьома іншими 6-вершинними циклами. Серед цих трьох циклів кожен є симетричною різницею двох інших. Граф в якому кожна вершина відповідає циклу з 6 вершин графу Хівуда, а дуги відповідають незв'язним парам — це граф Коксетера.[4]

Геометричні та топологічні властивості

Граф Хівуда є тороїдальним графом, тобто його можна відобразити без перетинів на поверхні тора. Як результат утворюється регулярна карта {6,3}2,1 з 7 гексагональними поверхнями. Кожна поверхня мапи суміжна до кожної іншої, а отже карта потребує 7 кольорів. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що не існує карти для тора яка потребує більше 7, а отже карта є максимальною.[5][6]

Ця карта також може бути вірно реалізована як многогранник Сілашші, єдиний відомий полігон, окрім тетраедра, в якому кожна пара граней є сусідніми.

Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє інцидентність точок і прямих у цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано, тобто графом, представленим інцидентним точкам і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано. Граф Хівуда має число схрещень рівне 3 і є найменшим кубічним графом з таким числом схрещень[7]. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещень 3. Граф Хівуда є графом одиничних відстаней — його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу.[8]

Алгебраїчні властивості

Група автоморфізмів графу Хівуда ізоморфна проективної лінійної групою PGL22(7), групі порядку 336.[9] Він діє транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є симетричним. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі списком Фостера граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами.[10][11] Характеристичний многочлен матриці графу Хівуда — ( x − 3 ) ( x + 3 ) ( x 2 − 2 ) 6 {\displaystyle (x-3)(x+3)(x^{2}-2)^{6}} . Спектр графу дорівнює ( − 3 ) 1 ( − 2 ) 6 ( 2 ) 6 3 1 {\displaystyle (-3)^{1}(-{\sqrt {2}})^{6}({\sqrt {2}})^{6}3^{1}} . Це єдиний граф з таким многочленом, який визначається спектром.

Хроматичний многочлен графу дорівнює:

π G ( z ) = z ( z − 1 ) ( z 12 − 20 z 11 + 190 z 10 − 1140 z 9 + 4845 z 8 − 15476 z 7 {\displaystyle \pi _{G}(z)=z(z-1)(z^{12}-20z^{11}+190z^{10}-1140z^{9}+4845z^{8}-15476z^{7}}
+ 38340 z 6 − 74587 z 5 + 113433 z 4 − 131700 z 3 + 110794 z 2 − 60524 z + 16161 ) {\displaystyle +38340z^{6}-74587z^{5}+113433z^{4}-131700z^{3}+110794z^{2}-60524z+16161)} .

Галерея

  • Багатогранник Сілаші[ru].
    Багатогранник Сілаші.
  • Граф Хівуда має число схрещень 3.
    Граф Хівуда має число схрещень 3.
  • Хроматичний індекс графу Хівуда дорівнює 3.
    Хроматичний індекс графу Хівуда дорівнює 3.
  • Хроматичне число графу Хівуда дорівнює 2.
    Хроматичне число графу Хівуда дорівнює 2.
  • Вкладення графу Хівуда в тор(показаний у вигляді квадрата з Періодичними граничними умовами[en]), розділяє його на сім взаємно-суміжних областей
    Вкладення графу Хівуда в тор(показаний у вигляді квадрата з Періодичними граничними умовами), розділяє його на сім взаємно-суміжних областей

Примітки

  1. ↑ Weisstein, Eric W. Heawood Graph(англ.) на сайті Wolfram MathWorld.
  2. ↑ а б . Brouwer, Andries E. Heawood graph. Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989). Архів оригіналу за 1 серпня 2012. Процитовано 26 січня 2016. {{cite web}}: Зовнішнє посилання в |work= (довідка)
  3. ↑ M. Abreu, R. E. L. Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Graphs and digraphs with all 2-factors isomorphic // Journal of Combinatorial Theory. — 2004. — Т. 92, вип. 2. — С. 395—404. — doi:10.1016/j.jctb.2004.09.004..
  4. ↑ Italo J. Dejter. From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. — arXiv:1002.1960. — doi:10.1002/jgt.20597..
  5. ↑ Ezra Brown. The many names of (7,3,1) // Mathematics Magazine. — 2002. — Т. 75, вип. 2. — С. 83—94. — doi:10.2307/3219140. — JSTOR 3219140.
  6. ↑ P. J. Heawood. Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322—339.
  7. ↑ послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
  8. ↑ Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. — arXiv:0912.5395..
  9. ↑ J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York : North Holland, 1976. — С. 237. — ISBN 0-444-19451-7.
  10. ↑ Royle, G. «Кубические симметричные графы (список Фостера).» [Архівовано 20 липня 2008 у Wayback Machine.]
  11. ↑ Марстон Кондер и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.

Джерело: стаття у Вікіпедії та історія редагувань (автори).