WikiDer > Граф Фрухта
| Граф Фрухта | |
|---|---|
 Граф Фрухта | |
| Названный в честь | Роберт Фрухт |
| Вершины | 12 |
| Края | 18 |
| Радиус | 3 |
| Диаметр | 4 |
| Обхват | 3 |
| Автоморфизмы | 1 ({я бы}) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Кубический Халин Панциклический |
| Таблица графиков и параметров | |
в математический поле теория графов, то Граф Фрухта это 3-регулярный граф с 12 вершинами, 18 ребрами и никакими нетривиальными симметрии.[1] Впервые он был описан Роберт Фрухт в 1939 г.[2]
Граф Фрухта - это панциклический График Халина с хроматическое число 3, хроматический индекс 3, радиус 3 и диаметр 4. Как и любой граф Халина, граф Фрухта многогранник (планарный и 3-вершинно-связанный) и Гамильтониан, с обхват 3. Его число независимости 5.
Граф Фрухта можно построить из Обозначение LCF: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].
Алгебраические свойства
Граф Фрухта входит в пятерку самых маленьких кубические графы имея только один автоморфизм графа, личность[3] (то есть каждую вершину можно топологически отличить от любой другой вершины). Такие графы называются асимметричный (или тождественные) графы. Теорема Фрухта заявляет, что любой группа может быть реализована как группа симметрий графа,[2] и усиление этой теоремы, также принадлежащее Фрухту, утверждает, что любая группа может быть реализована как симметрии 3-регулярного графа;[4] граф Фрухта является примером этой реализации для тривиальная группа.
В характеристический многочлен графа Фрухта есть .
Галерея
В хроматическое число графа Фрухта равно 3.
Граф Фрухта Гамильтониан.
Смотрите также
 | Викискладе есть медиафайлы по теме Граф Фрухта. |
Рекомендации
- ^ Вайсштейн, Эрик В. «График Фрухта». MathWorld.
- ^ а б Фрухт, Р. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe"., Compositio Mathematica (на немецком), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
- ^ Bussemaker, F.C .; Cobeljic, S .; Цветкович, Д. М .; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов, Отчет EUT, 76-WSK-01, кафедра математики и вычислительной техники, Технологический университет Эйндховена
- ^ Frucht, R. (1949), "Графы третьей степени с заданной абстрактной группой", Канадский математический журнал, 1: 365–378, Дои:10.4153 / CJM-1949-033-6, ISSN 0008-414X, МИСТЕР 0032987.