График Науру - Википедия - Nauru graph

Науру график
Науру graph.svg
Граф Науру гамильтонов.
Вершины24
Края36
Радиус4
Диаметр4
Обхват6
Автоморфизмы144 (S4× S3)
Хроматическое число2
Хроматический индекс3
Толщина книги3
Номер очереди2
ХарактеристикиСимметричный
Кубический
Гамильтониан
интеграл
Граф Кэли
Двудольный
Таблица графиков и параметров

в математический поле теория графов, то Науру график это симметричный двудольный кубический граф с 24 вершинами и 36 ребрами. Он был назван Дэвид Эппштейн после двенадцатиконечной звезды в флаг Науру.[1]

Она имеет хроматическое число 2, хроматический индекс 3, диаметр 4, радиус 4 и обхват 6.[2] Это также 3-вершинно-связанный и 3-реберный график. Она имеет толщина книги 3 и номер очереди 2.[3]

Граф Науру требует не менее восьми пересечений на любом его чертеже на плоскости. Это один из пяти неизоморфных графов, связанных как наименьший кубический граф, требующий восьми пересечений. Еще один из этих пяти графиков - это График Макги, также известный как (3-7) -клетка.[4][5]

Строительство

График Науру Гамильтониан и может быть описан Обозначение LCF  : [5, −9, 7, −7, 9, −5]4.[1]

Граф Науру также можно построить как обобщенный граф Петерсена грамм(12, 5) который образован вершинами двенадцатигранник соединены с вершинами двенадцатиконечной звезды, в которой каждая точка звезды соединена с точками в пяти шагах от нее.

Также существует комбинаторная конструкция графа Науру. Возьмите три различимых объекта и поместите их в четыре различимых ящика, не более одного объекта на ящик. Есть 24 способа так распределить объекты, соответствующие 24 вершинам графа. Если можно перейти из одного состояния в другое, переместив ровно один объект из его текущего местоположения в пустой ящик, то вершины, соответствующие двум состояниям, соединяются ребром. Результирующий граф переходов между состояниями и есть граф Науру.

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

Группа автоморфизмов графа Науру - это группа порядка 144.[6] Он изоморфен прямой продукт из симметричные группы S4 и S3 и действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Науру - это симметричный граф (хотя не переходное расстояние ). Он имеет автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно Приемная перепись, граф Науру - единственный кубический симметричный граф с 24 вершинами.[2]

Обобщенный граф Петерсена грамм(п, к) вершинно-транзитивно тогда и только тогда, когда п = 10 и k = 2 или если k2 ≡ ± 1 (мод.п) и является реберно-транзитивным только в следующих семи случаях: (п, к) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).[7] Итак, граф Науру - один из семи симметричных обобщенных графов Петерсена. Среди этих семи графиков есть кубический график , то Граф Петерсена , то График Мёбиуса – Кантора , то додекаэдрический граф и График дезарга .

Граф Науру - это Граф Кэли из S4, симметричная группа перестановок на четырех элементах, созданная тремя разными способами замены первого элемента одним из трех других: (1 2), (1 3) и (1 4).

В характеристический многочлен графа Науру равно

сделать это интегральный график - граф, спектр полностью состоит из целых чисел.

  • Симметричное вложение на торе, образованном склейкой противоположных сторон правильного шестиугольника

  • Обобщенный граф Петерсена, раскрашенный и помеченный как граф Кэли S4

  • Матрица смежности. Каждое ребро представлено двумя симметрично расположенными элементами одного цвета.

  • 1-планарный рисунок с 8 пересечениями

  • 24 направления качения октаэдр на треугольная сетка, нарисованный на шестиугольном торе

Топологические свойства

Симметричное вложение графа Науру на поверхность рода 4 с шестью додекагональными гранями.

График Науру имеет два разных вложения как обобщенный правильный многогранник: топологическая поверхность, разделенная на ребра, вершины и грани таким образом, что существует симметрия, принимающая любые флаг (инцидентная тройка вершины, ребра и грани) в любой другой флаг.[8]

Одно из этих двух вложений образует тор, поэтому граф Науру представляет собой тороидальный граф: он состоит из 12 шестиугольных граней вместе с 24 вершинами и 36 ребрами графа Науру. В двойственный граф этого вложения - симметричный 6-регулярный граф с 12 вершинами и 36 ребрами.

Другое симметричное вложение графа Науру имеет шесть двенадцатигранный граней и образует поверхность род 4. Его двойник не простой график, поскольку каждая грань имеет три ребра с четырьмя другими гранями, но мультиграф. Этот двойник может быть образован из графика регулярного октаэдр заменив каждое ребро пучком из трех параллельных ребер.

Множество граней любого из этих двух вложений - это множество Полигоны Петри другого вложения.

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

График Науру как график единичных расстояний, от Житник, Хорват и Писанский (2010).

Как и все обобщенные графы Петерсена, граф Науру может быть представлен точками на плоскости таким образом, что соседние вершины находятся на единичном расстоянии друг от друга; то есть это график единичного расстояния.[9] Он и призмы - единственные обобщенные графы Петерсена. грамм(п,п), которые не могут быть представлены таким образом, чтобы симметрии рисунка образовывали циклическую группу порядка п. Вместо этого его графическое представление единичных расстояний имеет группа диэдра Dih6 как его группа симметрии.

История

Первым, кто написал о графе Науру, был Р. М. Фостер, чтобы собрать все кубические симметричные графы.[10] Весь список кубических симметричных графов теперь назван в его честь. Foster Census а внутри этого списка граф Науру пронумерован F24A, но не имеет конкретного названия.[11] В 1950 г. Х. С. М. Кокстер цитировал график во второй раз, давая гамильтоново представление, используемое для иллюстрации этой статьи, и описывая его как Граф Леви из проективная конфигурация открыл Захария.[12][13]

В 2003 г. Эд Пегг написал в своей онлайн-колонке MAA, что F24A заслуживает названия, но не предложил его.[14] Наконец, в 2007 году Дэвид Эппштейн использовал имя Науру график поскольку флаг из Республика Науру имеет 12-конечную звезду, аналогичную той, которая появляется при построении графа как обобщенный граф Петерсена.[1]

Рекомендации

  1. ^ а б c Эппштейн, Д., Многоликость графа Науру, 2007.
  2. ^ а б Кондер, М. и Добчаньи П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
  3. ^ Вольц, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
  4. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A110507 (Количество узлов в наименьшем кубическом графе с числом пересечения n)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS..
  5. ^ Пегг, Э. Т.; Эксу, Г. (2009), «Графики пересечения чисел», Математика журнал, 11, заархивировано из оригинал на 2019-03-06, получено 2010-01-02.
  6. ^ Ройл, Г. F024A данные В архиве 2011-03-06 на Wayback Machine
  7. ^ Фрухт, Р.; Graver, J. E .; Уоткинс, М. Э. (1971), "Группы обобщенных графов Петерсена", Труды Кембриджское философское общество, 70: 211–218, Дои:10.1017 / S0305004100049811.
  8. ^ Макмаллен, Питер (1992), "Правильные многогранники типа {п, 3} с 2п вершины ", Geometriae Dedicata, 43 (3): 285–289, Дои:10.1007 / BF00151518.
  9. ^ Читник, Арджана; Хорват, Борис; Писанский, Томаж (2010), Все обобщенные графы Петерсена являются графами единичных расстояний (PDF), Препринты IMFM, 1109.
  10. ^ Фостер, Р. М. (1932 г.), «Геометрические схемы электрических сетей», Труды Американского института инженеров-электриков, 51: 309–317, Дои:10.1109 / T-AIEE.1932.5056068.
  11. ^ Bouwer, I. Z .; Чернов, W. W .; Monson, B .; Звезда, Z (1988), Приемная перепись, Исследовательский центр Чарльза Бэббиджа.
  12. ^ Кокстер, Х. С. М. (1950), «Самодуальные конфигурации и регулярные графы», Бюллетень Американского математического общества, 56: 413–455, Дои:10.1090 / S0002-9904-1950-09407-5.
  13. ^ Захариас, М. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik, 6: 147–170.
  14. ^ Пегг, Эд (2003), Кубические симметричные графы, Математическая ассоциация Америки.