Loading AI tools
симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами Из Википедии, свободной энциклопедии
В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном[англ.] по аналогии с двенадцатилучевой звездой на флаге Науру.[1]
| Граф Науру | |
|---|---|
 | |
| Вершин | 24 |
| Рёбер | 36 |
| Радиус | 4 |
| Диаметр | 4 |
| Обхват | 6 |
| Автоморфизмы | 144 (S4×S3) |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Свойства |
кубический
целый |
 Медиафайлы на Викискладе | |
Хроматическое число графа равно 2, хроматический индекс равен 3, диаметр — 4, радиус — 4, а обхват равен 6[2]. Граф является вершинно 3-связным и рёберно 3-связным.
Наименьшие кубические графы с числом пересечений 1-8 известны (последовательность A110507 в OEIS). Наименьший граф с 8 пересечениями — это граф Науру. Существует 5 неизоморфных кубических графов с 24 вершинами и числом пересечений 8[3]. Один из них — граф МакГи, известный также как (3-7)-клетка.[4]
Граф Науру является гамильтоновым и может быть описан с помощью LCF-нотации : [5, −9, 7, −7, 9, −5]4.[1]
Граф Науру можно также построить как обобщённый граф Петерсена G(12, 5), образованный вершинами двенадцатиугольника, где рёбра соединяют вершины в 12-лучевую звезду путём соединения вершин с шагом 5.
Также возможно построение на основе комбинаторики. Возьмём три различных объекта и положим в четыре неразличимых ящика, не более одного объекта в ящик. Существует 24 способа размещения объектов, что соответствует 24 вершинам графа. Если есть возможность перейти от одного размещения к другому путём перемещения ровно одного предмета в пустой ящик, две вершины соединяем ребром. Результирующий граф переходов от размещения к размещению является графом Науру.
Группа автоморфизмов графа Науру является группой порядка 144.[5]. Группа изоморфна прямому произведению симметрических групп S4 и S3 и действует транзитивно на вершинах, на рёбрах и дугах графа. Таким образом, граф Науру является симметричным (хотя и не дистанционно-транзитивным). Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое. Согласно списку Фостера граф Науру является единственным кубическим симметричным графом с 24 вершинами[2].
Обобщённый граф Петерсена G(n, k) является вершинно-транзитивным в том и только в том случае, когда n = 10 и k =2 или если k2 ≡ ±1 (mod n) и является рёберно-транзитивным только в следующих случаях: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5)[6]. Таким образом, граф Науру является одним из семи симметричных обобщённых графов Петерсена. Среди этих семи графов кубический граф , граф Петерсена , Граф Мёбиуса — Кантора , граф додекаэдра и граф Дезарга .
Граф Науру является графом Кэли группы S4, симметрической группы перестановок четырёх элементов, образованной перестановками первого элемента с тремя другими: (1 2), (1 3) и (1 4).
Характеристический многочлен матрицы графа Науру равен
откуда следует, что граф является целым — графом, спектр которого состоит только из целых чисел.
.svg) Тор образуется, топологически, путём склеивания противоположных рёбер правильного шестиугольника. |
.svg) цвета и перестановки показывают, что граф является графом Кэли группы S4. |
.svg) Каждое ребро представлено двумя элементами одного цвета, находящимися симметрично относительно диагонали. |
Граф Науру имеет два различных вложения как обобщённый правильный многогранник, при которых топологические поверхности разделены на рёбра, вершины и грани таким образом, что существует симметрия, переводящая любой флаг (инцидентная тройка из вершины, ребра и грани) в любой другой флаг[7].
Одно из этих двух вложений образует тор, так что граф Науру является тороидальным графом — он состоит из 12 шестиугольных граней вместе с 24 вершинами и 36 гранями графами Науру. Двойственный граф этого вложения является симметричным 6-регулярным графом с 12 вершинами и 36 рёбрами.
Другое симметричное вложение графа Науру имеет шесть двенадцатиугольных граней и образует поверхность рода 4. Его двойственный граф не является простым графом, поскольку каждая грань имеет три общих ребра с четырьмя другими гранями, а является мультиграфом. Этот двойственный граф можно образовать из графа правильного октаэдра путём замены каждого ребра тремя параллельными рёбрами.
Множество граней любого из этих двух вложений является множеством многоугольников Петри другого вложения.
Как и все обобщённые графы Петерсена, граф Науру можно представить в виде точек плоскости таким образом, что смежные вершины находятся на расстоянии единица. Таким образом, он является графом единичных расстояний[8]. Этот граф и призма являются единственными обобщёнными графами Петерсена G(n,p), которые невозможно представить таким образом, что симметрии рисунка образуют циклическую группу порядка n. Взамен его представление в виде графа имеет в качестве группы симметрий диэдрическую группу Dih6.
Первым, кто написал о графе Науру, был Фостер (Foster), указав граф в списке всех кубических симметричных графов [9]. Полный список кубических симметричных графов назван теперь его именем (Список Фостера) и в этом списке графу Науру присвоен номер F24A, но не присвоено какое-либо имя[10]. В 1950 Коксетер упомянул граф во второй раз, дав гамильтоново представление для иллюстрации статьи и описав граф как граф Леви проективной конфигурации, открытой Цахариасом[11][12].
В 2003 Эд Пегг (Ed Pegg Jr.) написал в своей статье на сайте Математической ассоциации Америки, что F24A заслуживает имя, но не предложил какое-либо [13]. Наконец, в 2007, Дэвид Эпштейн использовал название граф Науру, поскольку флаг республики Науру содержит 12-лучевую звезду, аналогичную той, что возникает при построении графа как обобщённого графа Петерсена.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
