В математической области теории графов , то граф Tutte-Косетер или Tutte восемь-клетка или Кремона-Ричмонд график представляет собой 3 - регулярный граф с 30 вершинами и 45 ребрами. В качестве уникального маленького кубического графа из обхвата 8 это клетка и граф Мура . Это двудольное , и может быть построено как граф Леви из обобщенного четырехугольника W 2 (известный как конфигурация Кремоны-Richmond ). Граф назван в честь Уильяма Томаса Тутте иHSM Coxeter ; он был открыт Тутте (1947), но его связь с геометрическими конфигурациями была исследована обоими авторами в паре совместно опубликованных статей (Tutte 1958; Coxeter 1958a).
График Тутте – Кокстера | |
---|---|
Названный в честь | WT Tutte H. SM Coxeter |
Вершины | 30 |
Края | 45 |
Радиус | 4 |
Диаметр | 4 |
Обхват | 8 |
Автоморфизмы | 1440 (Aut (S 6 )) |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Кубический граф Кейджа Мура Симметричный дистанционно-регулярный дистанционно-транзитивный Двудольный |
Таблица графиков и параметров |
Все кубические дистанционно регулярные графы известны. [1] Тутт – Кокстер - один из 13 таких графиков.
Он имеет перекресток номер 13, [2] [3] книжную толщину 3 и очередь номер 2. [4]
Конструкции и автоморфизмы
Особенно простая комбинаторная конструкция графа Тутта – Кокстера принадлежит Кокстеру (1958b) и основана на работе Сильвестра (1844). В современной терминологии возьмем полный граф на 6 вершинах K 6 . У него 15 граней, а также 15 идеальных сочетаний . Каждая вершина графа Тутта – Кокстера соответствует ребру или идеальному совпадению K 6 , а каждое ребро графа Тутта-Кокстера соединяет идеальное совпадение K 6 с каждым из трех составляющих его ребер. По симметрии каждое ребро K 6 принадлежит трем точным совпадениям. Между прочим, это разбиение вершин на ребра-вершины и совпадающие вершины показывает, что граф Тутта-Кокстера двудольный.
Основываясь на этой конструкции, Кокстер показал, что граф Тутте – Кокстера является симметричным графом ; у него есть группа из 1440 автоморфизмов , которые можно отождествить с автоморфизмами группы перестановок шести элементов (Coxeter 1958b). На внутренних автоморфизмах этой группы соответствует перестановке шесть вершин К 6 графу; эти перестановки действуют на граф Тутта – Кокстера, переставляя вершины на каждой стороне его двудольного деления, сохраняя при этом каждую из двух сторон фиксированной как набор. Кроме того, внешние автоморфизмы группы перестановок меняют одну сторону двудольности на другую. Как показал Кокстер, любой путь, содержащий до пяти ребер в графе Тутта – Кокстера, эквивалентен любому другому такому пути с помощью одного такого автоморфизма.
Граф Тутте – Кокстера как здание
Этот граф представляет собой сферическую конструкцию, связанную с симплектической группой (существует исключительный изоморфизм между этой группой и симметрической группой ). В частности, это график инцидентности обобщенного четырехугольника .
Конкретно, граф Тутте-Кокстера может быть определен из 4-мерного симплектического векторного пространства над следующим образом:
- вершины являются либо ненулевыми векторами, либо изотропными двумерными подпространствами,
- существует грань между ненулевым вектором v и изотропным двумерным подпространством если и только если .
Галерея
Хроматическое число графа Тутты-Кокстер 2.
Хроматической индекс графа Тутты-Кокстер равно 3.
Рекомендации
- ^ Брауэр, AE; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
- ^ Пегг, ET ; Эксу, Г. (2009). «Графики пересекающихся чисел». Mathematica Journal . 11 (2). DOI : 10.3888 / tmj.11.2-2 .
- ^ Эксу, Г. "Прямолинейные рисунки известных графов" .
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- Кокстер, HSM (1958a). «Хорды неразрушенной квадрики в PG (3,3)». Может. J. Math . 10 : 484–488. DOI : 10,4153 / CJM-1958-047-0 .
- Кокстер , HSM (1958b). «Двенадцать баллов в PG (5,3) с 95040 самотрансформациями». Труды Королевского общества А . 247 (1250): 279–293. DOI : 10.1098 / rspa.1958.0184 . JSTOR 100667 . S2CID 121676627 .
- Сильвестр, Дж. Дж. (1844 г.). «Элементарные исследования в анализе комбинаторной агрегации» . Фил. Mag . Серия 3. 24 : 285–295. DOI : 10.1080 / 14786444408644856 .
- Тутте, WT (1947). «Семейство кубических графов». Proc. Cambridge Philos. Soc . 43 (4): 459–474. DOI : 10.1017 / S0305004100023720 .
- Тутте, WT (1958). «Хорды неразрушенной квадрики в PG (3,3)». Может. J. Math . 10 : 481–483. DOI : 10,4153 / CJM-1958-046-3 .
Внешние ссылки
- Франсуа Лабель. "3D модель восьмерки клетки Тутте" .
- Вайсштейн, Эрик В. «Граф Леви» . MathWorld .
- Эксу, Дж. «Прямолинейные рисунки известных графов». [1]