Перегляд вихідного коду сторінки Граф Хівуда

{{вичитати}}
{{Граф
 | name = Граф Хівуда
 | image = [[Image:Heawood_Graph.svg|180px]]
 | image_caption = 
 | namesake = [[Персі Джон Хівуд]]
 | vertices = 14
 | edges = 21
 | girth = 6
 | diameter = 3
 | radius = 3
 | automorphisms = 336 ([[Проєктивна група|PGL<sub>2</sub>(7)]])
 | chromatic_number = 2 
 | chromatic_index = 3
 | spectrum = <math>(-3)^1 (-\sqrt{2})^6 (\sqrt{2})^6 3^1 </math>
 | queue_number = 2
 | properties = [[Двочастковий граф|Двочастковий]]<br>[[Кубічний граф|Кубічний]]<br>[[Дистанційно-транзитивний граф|дистанційно-транзитивний]]<br>[[Дистанційно-регулярний граф|дистанційно-регулярний]]<br>[[Тороїдальний граф|тороїдальний]]<br>[[Гамільтонів граф|гамільтонів]]<br>[[Симетричний граф|Симетричний]]
}}'''Граф Хівуда''' — [[Граф (математика)|ненаправлений граф]] з 14 вершинами і 21 ребром, названий на честь {{Не перекладено|Персі Джон Хівуд|Персі Джона Хівуда.|en|Percy John Heawood}}<ref>{{MathWorld | urlname=HeawoodGraph | title=Heawood Graph}}</ref>

== Комбінаторні властивості ==
Даний граф є [[Кубічний граф|кубічним]] і всі цикли в ньому містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є [[Клітка (теорія графів)|кліткою]]-(3,6) з [[Обхват (теорія графів)|обхватом]] 6. Він є також [[Дистанційно-транзитивний граф|дистанційно-транзитивним]] (дивіться [[Симетричний граф|список Фостера]]), а тому [[Дистанційно-регулярний граф|дистанційно-регулярним]].<ref name="brouwer">. {{cite web
| author= Brouwer, Andries E.
| authorlink= Andries Brouwer
| title= Heawood graph
| url= http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html
| work= [http://www.win.tue.nl/~aeb/drg/index.html Additions and Corrections to the book “Distance-Regular Graphs”] (Brouwer, Cohen, Neumaier; Springer; 1989)
| accessdate= 26 січня 2016
| archive-date= 1 серпня 2012
| archive-url= https://web.archive.org/web/20120801032828/http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html
}}</ref> У графі Хівуда мається 24 паросполучення і у всіх них ребра, що не входять у паросполучення, утворюють [[гамільтонів цикл]]. Наприклад, малюнок показує вершини графу, що поміщені на коло і утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами.<ref name="brouwer"/> Зважаючи на симетрію графу, будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше.<ref>{{статья
| автор = M. Abreu, R. E. L. Aldred, M. Funk, Bill Jackson,  D. Labbate,  J. Sheehan
| doi = 10.1016/j.jctb.2004.09.004
| mr = 2099150
| выпуск = 2
| издание = {{iw|Journal_of_Combinatorial_Theory|Journal of Combinatorial Theory|en|Journal_of_Combinatorial_Theory}} | series = Series B
| страницы = 395—404
| заглавие = Graphs and digraphs with all 2-factors isomorphic
| том = 92
| год = 2004}}.</ref>

У графі Хівуда 28 циклів, що містять по шість вершин. Кожен такий цикл не пов'язаний в точності з трьома іншими 6-вершинними циклами. Серед цих трьох циклів кожен є симетричною різницею двох інших. Граф в якому кожна вершина відповідає циклу з 6 вершин графу Хівуда, а дуги відповідають незв'язним парам — це [[Граф Коксетера|граф Коксетера]].<ref>{{статья
| автор =Italo J. Dejter
| заглавие =From the Coxeter graph to the Klein graph
| издание =Journal of Graph Theory
| год=2011
| doi=10.1002/jgt.20597
| arxiv=1002.1960}}.</ref>

== Геометричні та топологічні властивості ==
Граф Хівуда є тороїдальним графом, тобто його можна відобразити без перетинів на поверхні [[Тор (поверхня)|тора]]. Як результат утворюється [[регулярна карта]] {6,3}<sub>2,1</sub> з 7 гексагональними поверхнями. Кожна поверхня мапи суміжна до кожної іншої, а отже карта потребує 7 кольорів. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що не існує карти для тора яка потребує більше 7, а отже карта є максимальною.<ref>{{статья
| doi=10.2307/3219140
| автор = Ezra Brown 
| заглавие = The many names of (7,3,1)
| издание = [[Mathematics Magazine]]
| том =75
| выпуск =2
| год =2002
| страницы =83—94 
| url=http://www.math.vt.edu/people/brown/doc/731.pdf 
| jstor=3219140}}</ref><ref>{{статья
| автор = P. J. Heawood 
| заглавие =Map colouring theorems
| издание = Quarterly J. Math. Oxford Ser
| год =1890
| том =24 
| страницы =322—339}}</ref>

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

Граф Хівуда є також [[Граф Леві|графом Леві]] [[Площина Фано|поверхні Фано]], тобто графом, що представляє інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано, тобто [[Граф (математика)|графом]], представленим інцидентним точкам і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають [[Трикутник|трикутникам]] поверхні Фано. Граф Хівуда має [[число схрещень]] рівне 3 і є найменшим кубічним графом з таким числом схрещень<ref>{{OEIS|id=A110507}}</ref>. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещень 3. Граф Хівуда є графом одиничних відстаней&nbsp;— його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу.<ref>{{статья
| автор = Eberhard H., A. Gerbracht
| заглавие = Eleven unit distance embeddings of the Heawood graph
| год = 2009
| arxiv = 0912.5395}}.</ref>

== Алгебраїчні властивості ==
[[Група автоморфізмів]] графу Хівуда ізоморфна проективної лінійної групою PGL2<sub>2</sub>(7), групі порядку 336.<ref>{{книга-ру|автор               = J. A. Bondy, U. S. R. Murty
 |заглавие         = Graph Theory with Applications
 |место               = New York
 |издательство = North Holland
 |год                   = 1976
 |страницы         = 237
 |isbn                     = 0-444-19451-7
 |url                      = https://archive.org/details/graphtheorywitha0000bond
 |url-access               = registration
}}</ref> Він [[Дія групи|діє]] транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є [[Симетричний граф|симетричним]]. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі [[Фостер|списком Фостера]] граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами.<ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census «Кубические симметричные графы (список Фостера).»] {{Webarchive|url=https://web.archive.org/web/20080720005020/http://www.cs.uwa.edu.au/~gordon/remote/foster/#census |date=20 липня 2008 }}</ref><ref>{{не перекладено|Марстон Кондер|Марстон Кондер|en|Marston Conder}} и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.</ref> [[Характеристичний многочлен]] матриці графу Хівуда&nbsp;—  <math>(x-3) (x+3) (x^2-2)^6</math>. Спектр графу дорівнює <math>(-3)^1 (-\sqrt{2})^6 (\sqrt{2})^6 3^1 </math>. Це єдиний граф з таким многочленом, який визначається спектром.

[[Хроматичний многочлен]] графу дорівнює:
:<math>\pi_G(z) = z(z-1)(z^{12} -20z^{11} + 190z^{10} - 1140z^9 + 4845z^8 - 15476z^7 </math>
:: <math>+ 38340z^6 - 74587z^5 + 113433z^4 - 131700z^3+ 110794 z^2 - 60524z + 16161)</math>.

== Галерея ==
<gallery>
Image:Szilassi polyhedron.svg|{{не перекладено|Багатогранник Сілаші|Багатогранник Сілаші|ru|Многогранник Силаши}}.
Файл:3-crossing Heawood graph.svg|Граф Хівуда має число схрещень 3.
Файл: Heawood graph 3color edge.svg|[[Хроматичний індекс]] графу Хівуда дорівнює 3.
Файл: Heawood graph 2COL.svg|[[Хроматичне число]] графу Хівуда дорівнює 2.
Файл:7x-torus.svg|Вкладення графу Хівуда в тор(показаний у вигляді квадрата з {{не перекладено|Періодичні граничні умови|Періодичними граничними умовами|en|Periodic boundary conditions}}), розділяє його на сім взаємно-суміжних областей</gallery>

'''Примітки'''
{{reflist}}


[[Категорія:Регулярні графи]]
[[Категорія:Теорія графів]]
[[Категорія:Види графів]]
[[Категорія:Графи (теорія графів)]]
[[Категорія:Алгоритми на графах]]