Граф Хивуда
Граф Хивуда | |
---|---|
Назван в честь | Перси Джон Хивуд |
Вершин | 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]. Характеристический многочлен матрицы графа Хивуда — . Спектр графа равен Это единственный граф с таким многочленом, который определяется спектром.
Хроматический многочлен графа равен:
-
- .
Галерея
[править | править код]-
Граф Хивуда имеет число скрещиваний 3.
-
Хроматический индекс графа Хивуда равен 3.
-
Хроматическое число графа Хивуда равно 2.
-
Вложение графа Хивуда в тор (показан в виде квадрата с периодическими граничными условиями[англ.]), разделяющий его на семь взаимно-смежных областей
Примечания
[править | править код]- ↑ Weisstein, Eric W. Heawood Graph (англ.) на сайте Wolfram MathWorld.
- ↑ 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 года.
- ↑ 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..
- ↑ Italo J. Dejter. From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. — doi:10.1002/jgt.20597. — arXiv:1002.1960..
- ↑ Ezra Brown. The many names of (7,3,1) // Mathematics Magazine. — 2002. — Т. 75, вып. 2. — С. 83—94. — doi:10.2307/3219140. — .
- ↑ P. J. Heawood. Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322—339.
- ↑ последовательность A110507 в OEIS
- ↑ Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. — arXiv:0912.5395..
- ↑ J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York: North Holland, 1976. — С. 237. — ISBN 0-444-19451-7. Архивировано 13 апреля 2010 года.
- ↑ Royle, G. «Кубические симметричные графы (список Фостера).» Архивировано 20 июля 2008 года.
- ↑ Марстон Кондер[англ.] и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
Для улучшения этой статьи желательно:
|