Граф Хивуда

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Граф Хивуда
Назван в честь Перси Джон Хивуд
Вершин 14
Рёбер 21
Радиус 3
Диаметр 3
Обхват 6
Автоморфизмы 336 (PGL2(7))
Хроматическое число 2
Хроматический индекс 3
Свойства двудольный
кубический
клетка
дистанционно-транзитивный
дистанционно-регулярный
тороидальный
гамильтонов
симметричный
Логотип Викисклада Медиафайлы на Викискладе

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

Комбинаторные свойства

[править | править код]

Граф является кубическим и все циклы в графе содержат шесть и более рёбер. Любой меньший кубический граф содержит меньшие циклы, так что этот граф является (3,6)-клеткой, наименьшим кубическим графом с обхватом 6. Он является также дистанционно-транзитивным (смотрите список Фостера), а потому дистанционно-регулярным[2]. В графе Хивуда имеется 24 паросочетания, и во всех паросочетаниях рёбра, не входящие в паросочетание, образуют гамильтонов цикл. Например, рисунок показывает вершины графа, помещённые на окружность и образующие цикл, а диагонали внутри окружности образуют паросочетание. Если разделить рёбра цикла на два паросочетания, мы получим три совершенных паросочетания (то есть, 3-цветную раскраску рёбер) восемью различными способами[2]. Ввиду симметрии графа любые два совершенных паросочетания и любые два гамильтоновых цикла можно преобразовать из одного в другое[3].

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

Геометрические и топологические свойства

[править | править код]

Граф Хивуда является тороидальным графом, то есть его можно вложить без пересечений в тор. Одно из вложений такого типа размещает вершины и рёбра графа в трёхмерном евклидовом пространстве в виде множества вершин и рёбер невыпуклого многогранника с топологией тора, многогранника Силаши. Граф назван в честь Перси Джона Хивуда, доказавшего в 1890 году, что для раскраски любого разбиения тора на многоугольники достаточно семи цветов[5][6]. Граф Хивуда образует разбиение тора на семь взаимно смежных областей, что показывает, что граница точна. Граф Хивуда является также графом Леви плоскостью Фано, то есть графом, представляющим инцидентность точек и прямых в этой геометрии. В этой интерпретации циклы длины 6 в графе Хивуда соответствуют треугольникам поверхности Фано. Граф Хивуда имеет число скрещиваний равное 3 и является наименьшим кубическим графом с таким числом скрещиваний[7]. Вместе с графом Хивуда существует 8 различных графов порядка 14 с числом скрещиваний 3. Граф Хивуда является графом единичных расстояний — его можно вложить в плоскость так, что смежные вершины окажутся в точности на расстоянии единица, при этом никакие две вершины не попадут на одно и то же место плоскости и никакая точка не окажется внутри ребра. Однако у известных вложений этого типа отсутствует симметрия, присущая графу[8].

Алгебраические свойства

[править | править код]

Группа автоморфизмов графа Хивуда изоморфна проективной линейной группе PGL2(7), группе порядка 336[9]. Он действует транзитивно на вершины, на рёбра и на дуги графа, поэтому граф Хивуда является симметричным. Имеются автоморфизмы, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно списку Фостера граф Хивуда, обозначенный как F014A, является единственным кубическим графом с 14 вершинами[10][11]. Характеристический многочлен матрицы графа Хивуда — . Спектр графа равен Это единственный граф с таким многочленом, который определяется спектром.

Хроматический многочлен графа равен:

.

Примечания

[править | править код]
  1. Weisstein, Eric W. Heawood Graph (англ.) на сайте Wolfram MathWorld.
  2. 1 2 Brouwer, Andries E. Heawood graph. Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989). Дата обращения: 2 января 2014. Архивировано 1 августа 2012 года.
  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. — doi:10.1002/jgt.20597. — arXiv:1002.1960..
  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. Архивировано 13 апреля 2010 года.
  10. Royle, G. «Кубические симметричные графы (список Фостера).» Архивировано 20 июля 2008 года.
  11. Марстон Кондер[англ.] и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.