В математической области теории графов , то граф Науру является симметричным двудольный кубический граф с 24 вершинами и 36 ребрами. Он был назван Дэвидом Эппштейном в честь двенадцатиконечной звезды на флаге Науру . [1]
Науру график | |
---|---|
Вершины | 24 |
Края | 36 |
Радиус | 4 |
Диаметр | 4 |
Обхват | 6 |
Автоморфизмы | 144 (S 4 × S 3 ) |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Симметричный кубический гамильтонов интегральный граф Кэли Двудольный |
Таблица графиков и параметров |
Он имеет хроматическое число 2, хроматический индекс 3, диаметр 4, радиус 4 и обхват 6. [2] Это также граф с 3 связными вершинами и 3 связными ребрами. Он имеет книжную толщину 3 и номер очереди 2. [3]
Граф Науру требует как минимум восьми пересечений на любом его чертеже на плоскости. Это один из пяти неизоморфных графов, связанных как наименьший кубический граф, требующий восьми пересечений. Еще один из этих пяти графиков - это граф МакГи , также известный как (3-7) -клетка . [4] [5]
Строительство
Граф Науру является гамильтоновым и может быть описан с помощью обозначения LCF : [5, −9, 7, −7, 9, −5] 4 . [1]
Граф Науру также может быть построен как обобщенный граф Петерсена G (12, 5), который образован вершинами двенадцатиугольника, соединенными с вершинами двенадцатиконечной звезды, в которой каждая точка звезды соединена с точками пятью точками. в шагах от него.
Также существует комбинаторная конструкция графа Науру. Возьмите три различимых объекта и поместите их в четыре различимых коробки, не более одного объекта на коробку. Есть 24 способа так распределить объекты, соответствующие 24 вершинам графа. Если можно перейти из одного состояния в другое, переместив ровно один объект из его текущего местоположения в пустой ящик, то вершины, соответствующие двум состояниям, соединяются ребром. Полученный граф переходов между состояниями и есть граф Науру.
Алгебраические свойства
Группа автоморфизмов графа Науру является группа порядка 144. [6] Это изоморфна прямому произведению Китайской симметрических групп S 4 и S 3 и действует транзитивно на вершинах, по краям и на дугах графа . Следовательно, граф Науру является симметричным графом (хотя и не транзитивным по расстоянию ). У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера , граф Науру - единственный кубический симметричный граф с 24 вершинами. [2]
Обобщенный граф Петерсена G ( n, k ) является вершинно-транзитивным тогда и только тогда, когда n = 10 и k = 2 или если k 2 ≡ ± 1 (mod n ), и является реберно-транзитивным только в следующих семи случаях: ( n , k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). [7] Итак, граф Науру - один из семи симметричных обобщенных графов Петерсена. Среди этих семи графиков есть кубический граф , граф Петерсена , граф Мебиуса – Кантора , додекаэдрический граф и граф Дезарга .
Граф Науру является граф Кэли из S 4 , симметричная группа перестановок на четырех элементов, порожденную тремя различными способами замены первого элемента с одним из трех других: (1 2), (1 3) и (1 4).
Характеристический полином графа Науру равен
превращая его в интегральный граф - граф, спектр которого полностью состоит из целых чисел.
Симметричное вложение на торе, образованном склейкой противоположных сторон правильного шестиугольника
Обобщенный граф Петерсена , раскрашенный и помеченный как граф Кэли S 4
Матрица смежности . Каждое ребро представлено двумя симметрично расположенными элементами одного цвета.
1-планарный чертеж с 8 пересечениями
24 ориентации катящегося октаэдра на треугольной сетке , нарисованной на гексагональном торе
Топологические свойства
Граф Науру имеет два различных вложения как обобщенный правильный многогранник : топологическая поверхность, разделенная на ребра, вершины и грани таким образом, что существует симметрия, переводящая любой флаг (инцидентную тройку вершины, ребра и грани) в любой другой флаг. [8]
Одно из этих двух вложений образует тор , поэтому граф Науру является тороидальным графом : он состоит из 12 шестиугольных граней вместе с 24 вершинами и 36 ребрами графа Науру. Двойственный граф этого вложения является симметричным 6-регулярным графом с 12 вершинами и 36 ребрами.
Другое симметричное вложение графа Науру имеет шесть додекагональных граней и образует поверхность рода 4. Его двойственный граф не является простым графом , поскольку каждая грань имеет три ребра с четырьмя другими гранями, а является мультиграфом . Этот двойник может быть образован из графа правильного октаэдра , заменяя каждое ребро пучком из трех параллельных ребер.
Множество граней любого из этих двух вложений - это множество многоугольников Петри другого вложения.
Геометрические свойства
Как и все обобщенные графы Петерсена, граф Науру может быть представлен точками на плоскости таким образом, что соседние вершины находятся на единичном расстоянии друг от друга; то есть это график единичных расстояний . [9] Он и призмы являются единственными обобщенными графами Петерсена G ( n , p ), которые не могут быть представлены таким образом, чтобы симметрии рисунка образовывали циклическую группу порядка n . Вместо этого его представление графа единичных расстояний имеет диэдральную группу Dih 6 в качестве группы симметрии.
История
Первым, кто написал о графе Науру, был Р.М. Фостер , который попытался собрать все кубические симметричные графы. [10] Весь список кубических симметричных графов теперь назван в его честь Перепись Фостера, а внутри этого списка граф Науру имеет номер F24A, но не имеет конкретного имени. [11] В 1950 год Коксетер привел граф во второй раз, что дает гамильтон представление , используемое для иллюстрации этой статьи и описаний его как графа Леви о наличии проективной конфигурации обнаруженной Захарией. [12] [13]
В 2003 году Эд Пегг написал в своей онлайн-колонке MAA, что F24A заслуживает названия, но не предложил его. [14] Наконец, в 2007 году, Дэвид Эпштайна использовал имя Науру график , потому что флаг в Республике Науру имеет 12-точечную звезду , подобную те , которая появляется в построении графика в качестве обобщенного графа Петерсена. [1]
Рекомендации
- ^ Б с Eppstein, D. , многочисленных граней графа Науру , 2007.
- ^ a b Кондер М. и Добчаньи П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A110507 (Количество узлов в наименьшем кубическом графе с номером пересечения n)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS..
- ^ Пегг, ET ; Exoo, G. (2009), "номер графы Crossing" , Mathematica Journal , 11 , архивируются с оригинала на 2019-03-06 , извлекаться 2010-01-02.
- ^ Royle, Г. F024A данные архивации 2011-03-06 в Wayback Machine
- ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "Группа обобщенных графов Петерсена", Труды Кембриджского философского общества , 70 : 211-218, DOI : 10,1017 / S0305004100049811.
- ^ МакМаллен, Питер (1992), «Правильные многогранники типа { p , 3} с 2 p вершинами», Geometriae Dedicata , 43 (3): 285–289, doi : 10.1007 / BF00151518.
- ^ Читник, Арджана; Хорват, Борис; Писанский, Томаж (2010), Все обобщенные графы Петерсена являются графами единичных расстояний (PDF) , Препринты IMFM, 1109.
- ^ Фостер, Р. М. (1932), «Геометрические схемы электрических сетей», Труды Американского института инженеров - электриков , 51 : 309-317, DOI : 10,1109 / Т-AIEE.1932.5056068.
- ^ Bouwer, IZ; Чернов В.В.; Monson, B .; Звезда, Z (1988), Перепись Фостера , Исследовательский центр Чарльза Бэббиджа.
- ^ Косетер, HSM (1950), "Автодуальные конфигурации и регулярные графы", Бюллетень Американского математического общества , 56 : 413-455, DOI : 10,1090 / S0002-9904-1950-09407-5.
- ^ Захариас, М. (1941), «Untersuchungen über ebene Konfigurationen (124, 163)», Deutsche Mathematik , 6 : 147–170.
- ^ Пегг, Эд (2003), Кубические симметричные графы , Математическая ассоциация Америки.