Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
График Хивуда
Heawood Graph.svg
Названный в честьПерси Джон Хивуд
Вершины14
Края21 год
Радиус3
Диаметр3
Обхват6
Автоморфизмы336 ( PGL 2 (7) )
Хроматическое число2
Хроматический индекс3
Род1
Толщина книги3
Номер очереди2
ХарактеристикиДвудольная
кубическая
клетка,
дистанционно-транзитивная,
дистанционно-регулярная,
тороидальный
гамильтониан,
симметричный,
ориентированно простой
Таблица графиков и параметров

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

Комбинаторные свойства [ править ]

Граф кубический , и все его циклы имеют шесть или более ребер. Каждый меньший кубический граф имеет более короткие циклы, поэтому этот граф является 6- клеточным , наименьшим кубическим графом обхвата 6. Это дистанционно-транзитивный граф (см. Перепись Фостера ) и, следовательно, дистанционно регулярный . [2]

Есть 24 совершенные паросочетания в графе работе Хивуда; для каждого сопоставления набор ребер, не входящих в сопоставление, образует гамильтонов цикл . Например, на рисунке показаны вершины графа, помещенные в цикл, причем внутренние диагонали цикла образуют совпадение. Подразделяя ребра цикла на два сопоставления, мы можем разделить граф Хивуда на три идеальных сопоставления (то есть трехкратным цветом его ребра ) восемью различными способами. [2] Каждые два идеальных паросочетания и каждые два гамильтоновых цикла можно преобразовать друг в друга с помощью симметрии графа. [3]

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

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

Граф Хивуда - это тороидальный граф ; то есть его можно вложить без пересечений на тор . Одно вложение этого типа помещает свои вершины и ребра в трехмерное евклидово пространство как множество вершин и ребер невыпуклого многогранника с топологией тора, многогранника Силасси .

Граф назван в честь Перси Джона Хивуда , который в 1890 году доказал, что при каждом подразделении тора на многоугольники многоугольные области можно раскрасить не более чем в семь цветов. [5] [6] Граф Хивуда образует подразделение тора с семью смежными областями, показывая, что эта граница жесткая.

График работе Хивуда является графиком Леви в плоскости Фано , граф , представляющий случаи между точками и линиями в этой геометрии. При такой интерпретации 6-циклы в графе Хивуда соответствуют треугольникам на плоскости Фано. Также граф Хивуда является построением Титса группы SL 3 (F 2 ) .

Граф Хивуда имеет номер пересечения 3 и является наименьшим кубическим графом с этим номером пересечения (последовательность A110507 в OEIS ). Включая граф Хивуда, есть 8 различных графов порядка 14 с пересечением номер 3.

Граф Хивуда - это наименьший кубический граф с инвариантом графа Колена де Вердьера μ = 6. [7]

Граф Хивуда - это граф единичных расстояний : он может быть вложен в плоскость таким образом, чтобы смежные вершины находились на расстоянии одного друг от друга, без двух вершин, вложенных в одну и ту же точку, и ни одной вершины, вложенной в точку внутри ребра. [8]

Алгебраические свойства [ править ]

Группа автоморфизмов графа Хивуда изоморфна проективной линейной группе PGL 2 (7), группе порядка 336. [9] Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Хивуда является симметричным графом . Он имеет автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Более того, граф Хивуда является 4-дуговым транзитивным . [10] Согласно переписи населения Фостера , граф Хивуда, обозначенный как F014A, является единственным кубическим симметричным графом с 14 вершинами. [11] [12]

Он имеет книжную толщину 3 и номер очереди 2. [13]

Характеристический полином графа является работе Хивуда . Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром.

Галерея [ править ]

  • Szilassi многогранник .

  • График Хивуда имеет перекресток номер  3.

  • Хроматической индекс из граф хивуда равен 3.

  • Хроматическое число из граф хивуда 2.

  • Вложение графа Хивуда в тор (показанный в виде квадрата с периодическими граничными условиями ), разбивающий его на семь взаимно смежных областей

  • Граф Хивуда и связанное с ним отображение, вложенное в тор.

  • Воспроизвести медиа

    Видео графа Хивуда на торусе

Ссылки [ править ]

  1. ^ Вайсштейн, Эрик В. "График Хивуда" . MathWorld .
  2. ^ a b Брауэр, Андрис Э. «Граф Хивуда» . CS1 maint: discouraged parameter (link) Дополнения и исправления к книге Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)
  3. ^ Abreu, M .; Олдред, REL; Функ, М .; Джексон, Билл; Labbate, D .; Sheehan, J. (2004), "Графики и орграфы со всеми 2-факторами , изоморфными", Журнал комбинаторной теории, Series B , 92 (2): 395-404, DOI : 10.1016 / j.jctb.2004.09.004 , М.Р. 2099150 .
  4. ^ Дейтер, Итало Дж. (2011), «От графа Кокстера к графу Клейна», Journal of Graph Theory , 70 : 1–9, arXiv : 1002.1960 , doi : 10.1002 / jgt.20597 , S2CID 754481 .
  5. ^ Браун, Эзра (2002). «Многие имена (7,3,1)» (PDF) . Математический журнал . 75 (2): 83–94. DOI : 10.2307 / 3219140 . JSTOR 3219140 . Архивировано из оригинального (PDF) 05 февраля 2012 года . Проверено 27 октября 2006 .  
  6. ^ В работе Хивуда, PJ (1890). «Теоремы о раскраске карт». Ежеквартальный математический журнал . Первая серия. 24 : 322–339. CS1 maint: discouraged parameter (link)
  7. ^ Хайн ван дер Холст (2006). «Графики и препятствия в четырех измерениях» (PDF) . Журнал комбинаторной теории, серии B . 96 (3): 388–404. DOI : 10.1016 / j.jctb.2005.09.004 .
  8. ^ Гербрахт, Эберхард Х.-А. (2009). «Одиннадцать вложений единичного расстояния графа Хивуда». arXiv : 0912.5395 . Bibcode : 2009arXiv0912.5395G . Cite journal requires |journal= (help).
  9. ^ Бонди, JA ; Мурти, USR (1976). Теория графов с приложениями . Нью-Йорк: Северная Голландия. п. 237 . ISBN 0-444-19451-7. Архивировано из оригинала на 2010-04-13 . Проверено 18 декабря 2019 .
  10. ^ Кондер, Марстон; Мортон, Маргарет (1995). "Классификация трехвалентных симметричных графов малого порядка" (PDF) . Австралазийский журнал комбинаторики . 11 : 146.
  11. ^ Ройл, Г. «Кубические симметричные графы (перепись Фостера)». Архивировано 20 июля 2008 г. в Wayback Machine.
  12. ^ Кондер, М. и Добчаньи, П. "Трехвалентные симметричные графы до 768 вершин". J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
  13. ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.