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

{{Граф|name=Граф Голднера — Харарі|image=[[Файл:Goldner-Harary graph.svg|220px]]|namesake=А. Голднер, [[Френк Харарі|Ф. Харарі]]|vertices=11|edges=27|girth=3|radius=2|diameter=2|automorphisms=12 ([[Діедральна група|D<sub>6</sub>]])|chromatic_number=4|chromatic_index=8|properties=[[Багатогранний граф|поліедральний]]
<br>[[Планарний граф|планарний]]
<br>[[Хордальний граф|хордальний]]
<br>[[Досконалий граф|досконалий]]
<br>[[Деревна ширина (теорія графів)|деревна ширина = 3]]}}

У [[Теорія графів|теорії графів]] '''граф Голднера&nbsp;— Харарі'''&nbsp;— це простий [[Орієнтований граф|неорієнтований граф]] із 11 вершинами і 27 ребрами. Файл названо на честь А. Голднера і [[Френк Харарі|Ф. Харарі]], які 1975 року довели, що він є найменшим [[Гамільтонів граф|негамільтоновим]] [[Планарний граф|максимальним планарним графом]]<ref>{{Стаття|author=M. B. Dillencourt|title=Polyhedra of small orders and their Hamiltonian properties|видання=Journal of Combinatorial Theory, Series B|том=66|рік=1996|pages=87–122|doi=10.1006/jctb.1996.0008}}.</ref><ref>{{Книга
|автор = R. C. Read, R. J. Wilson
|заголовок = An Atlas of Graphs
|місце = Oxford, England
|видавництво = Oxford University Press
|сторінки = 285
|рік = 1998
}}.</ref>. [[Бранко Ґрюнбаум|Ґрюнбаум]] 1967 року вже наводив той самий граф як приклад негамільтонового [[Симпліційний многогранник|симпліційного многогранника]]<ref name="grun">{{Книга
|автор = Branko Grünbaum
|заголовок = Convex Polytopes
|видавництво = Wiley Interscience
|рік = 1967
|сторінки = 357
}}.</ref>.

== Властивості ==
Граф Голднера&nbsp;— Харарі [[Планарний граф|планарний]]&nbsp;— його можна намалювати на площині без схрещень ребер. При малюванні на площині всі грані графа трикутні, що робить його [[Планарний граф|максимальним планарним графом]]. Як і будь-який максимальний планарний граф, він також [[K-вершинно-зв'язний граф|3-вершинно-зв'язний]]&nbsp;— видалення будь-яких двох вершин залишає [[Словник термінів теорії графів|підграф]] зв'язним.

Граф Голднера&nbsp;— Харарі [[Гамільтонів граф|негамільтонів]]. Найменша кількість вершин для негамільтонових поліедральних графів дорівнює 11. Таким чином, граф Голднера&nbsp;— Харарі є прикладом мінімального графа цього типу. Однак [[граф Гершеля]], інший негамільтонів граф із 11 вершинами, має менше ребер.

Як максимальний планарний граф негамільтонів, граф Голднера&nbsp;— Харарі є прикладом планарного з [[Книжкове вкладення|книжковою товщиною]], більшою 2<ref>{{Книга
|автор = Frank R. Bernhart, Paul C. Kainen
|заголовок = The book thickness of a graph
|видання = Journal of Combinatorial Theory, Series B
|том = 27
|сторінки = 320–331
|рік = 1979
|doi = 10.1016/0095-8956(79)90021-2
}}.</ref>. Ґрунтуючись на існуванні таких прикладів, Бернгарт і Кайнен (Bernhart, Kainen) висловили гіпотезу, що книжкова товщина планарних графів може бути довільно великою, але потім було показано книжкова товщина планарних графів не перевищує 4<ref>{{Книга
|автор = Mihalis Yannakakis
|заголовок = Proc. 18th ACM Symp. Theory of Computing (STOC)
|рік = 1986
|сторінки = 104–108
|doi = 10.1145/12130.12141
}}.</ref>.

[[Книжкове вкладення|Книжкова товщина]] графа&nbsp;— 3, [[хроматичне число]]&nbsp;— 4, [[Розфарбовування ребер|хроматичний індекс]]&nbsp;— 8, [[Обхват (теорія графів)|обхват]]&nbsp;— 3, [[Відстань (теорія графів)|радіус]]&nbsp;— 2, [[Відстань (теорія графів)|діаметр]]&nbsp;— 2 і граф є [[K-реберно-зв'язний граф|3-реберно-зв'язним]].

Граф є також [[K-дерево|3-деревом]], а тому його [[Деревна ширина (теорія графів)|деревна ширина]] дорівнює 3. Подібно до будь-якого ''k''-дерева, граф є [[Хордальний граф|хордальним]]. Як планарне 3-дерево, граф є прикладом [[Граф Аполлонія|мережі Аполлонія]].

== Геометрія ==
За [[Теорема Штайніца|теоремою Штайніца]] граф Голднера&nbsp;— Харарі є [[Багатогранний граф|поліедральним графом]]&nbsp;— він планарний і 3-зв'язний, так що існує опуклий многогранник, для якого граф Голднера&nbsp;— Харарі є [[Симпліційний комплекс#Пов'язані визначення|кістяком]].

Геометрично подання графа Голднера&nbsp;— Харарі у вигляді многогранника можна утворити, приклеївши тетраедр до кожної грані [[Трикутна біпіраміда|трикутної біпіраміди]], так само, як [[триакістетраедр]] утворено приклеюванням тетраедра до кожної гранні [[октаедр]]а. Тобто це [[многогранник Клі]] трикутної дипіраміди<ref name="grun"/><ref name="ewald">{{Стаття|title=Hamiltonian circuits in simplicial complexes|author=Günter Ewald|видання=Geometriae Dedicata|том=2|issue=1|рік=1973|pages=115–125|doi=10.1007/BF00149287}}.</ref>. [[Двоїстий граф]] графа Голднера&nbsp;— Харарі геометрично подається [[зрізання]]м [[Трикутна призма|трикутної призми]].

== Алгебричні властивості ==
[[Автоморфізм графів|Група автоморфзмів]] графа Голднера&nbsp;— Харарі має порядок 12 і ізоморфна [[Діедральна група|діедральній групі]] D<sub>6</sub>, групі симетрій [[Шестикутник|правильного шестикутника]], що включає як обертання, так і відображення.

[[Характеристичний поліном|Характеристичний многочлен]] графа Голднера&nbsp;— Харарі дорівнює <math>-(x-1)^2 x^2 (x+2)^3 (x^2-3) (x^2-4 x-9)</math> .

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

== Посилання ==
* {{mathworld|title=Граф Голднера — Харарі|urlname=Goldner-HararyGraph}}
[[Категорія:Планарні графи]]
[[Категорія:Графи, що мають власну назву]]
[[Категорія:1975 у науці]]