Меню Главная Случайная статья Настройки Граф Голднера — Харари Материал из https://ru.wikipedia.org В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом[1][2][3]. Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.[4] Содержание 1 Свойства 2 Геометрия 3 Алгебраические свойства 4 Примечания 5 Ссылки Свойства Граф Голднера — Харари планарен — его можно нарисовать на плоскости без пересечения рёбер. При рисовании на плоскости все грани графа треугольны, что делает его максимальным планарным графом. Как и любой максимальный планарный граф, он также вершинно 3-связен — удаление любых двух вершин оставляет подграф связным. Граф Голднера — Харари негамильтонов. Наименьшее возможное число вершин для негамильтоновых полиэдральных графов равно 11. Таким образом, граф Голднера — Харари является примером минимального графа этого типа. Однако Граф Хершеля, другой негамильтонов многогранник с 11 вершинами, имеет меньше рёбер. Как максимальный планарный негамильтонов граф, граф Голднера — Харари даёт пример планарного с книжной толщиной, большей двух[5]. Основываясь на существовании таких примеров, Бернхарт и Кайнен (Bernhart, Kainen) высказали гипотезу, что книжная толщина планарных графов может быть произвольно большой, но затем было показано, что все планарные графы имеют книжную толщину, не превосходящую четырёх[6]. Книжная толщина графа равна 3, хроматическое число равно 4, хроматический индекс равен 8, обхват равен 3, радиус равен 2, диаметр равен 2 и граф является рёберно 3-связным. Граф является также 3-деревом, а потому его древесная ширина равно 3. Подобно любому k-дереву, граф является хордальным. Как планарное 3-дерево, граф даёт пример сети Аполлония. Геометрия По теореме Штейница граф Голднера — Харари является полиэдральным графом — он планарен и 3-связен, так что существует выпуклый многогранник, имеющий граф Голднера — Харари в качестве его скелета. Геометрически представление графа Голднера — Харари в виде многогранника может быть образовано путём склеивания тетраэдра к каждой грани треугольной бипирамиды, таким же образом, как триакистетраэдр образован склеиванием тетраэдра с каждой гранью октаэдра. То есть это многогранник Кли треугольной дипирамиды[4][7]. Двойственный граф графа Голднера — Харари геометрически представляется усечением треугольной призмы. Алгебраические свойства Группа автоморфмзмов графа Голднера — Харари имеет порядок 12 и изоморфна диэдрической группе D6, группе симметрий правильного шестиугольника, включающей как вращения, так и отражения. Характеристический многочлен графа Голднера — Харари равен ${\displaystyle -(x-1)^{2}x^{2}(x+2)^{3}(x^{2}-3)(x^{2}-4x-9)}$. Примечания A. Goldner, F. Harary. {{{заглавие}}} // Bull. Malaysian Math. Soc.. — 1975. — Т. 6, вып. 1. — С. 41–42.. См. также номера 6(2):33 (1975) и 8:104-106 (1977). Ссылки с сайта список публикаций Харари Архивная копия от 2 января 2013 на Wayback Machine. M. B. Dillencourt. Polyhedra of small orders and their Hamiltonian properties // Journal of Combinatorial Theory, Series B. — 1996. — Т. 66. — С. 87–122. — doi:10.1006/jctb.1996.0008.. R. C. Read, R. J. Wilson. An Atlas of Graphs. — Oxford, England: Oxford University Press, 1998. — С. 285.. 1 2 Gnter Ewald. Hamiltonian circuits in simplicial complexes // Geometriae Dedicata. — 1973. — Т. 2, вып. 1. — С. 115–125. — doi:10.1007/BF00149287.. Ссылки Weisstein, Eric W. Goldner-Harary graph (англ.) на сайте Wolfram MathWorld.