| Граф Фрухта | |
|---|---|
 Граф Фрухта | |
| Названный в честь | Роберт Фрухт |
| Вершины | 12 |
| Края | 18 |
| Радиус | 3 |
| Диаметр | 4 |
| Обхват | 3 |
| Автоморфизмы | 1 ({ id }) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Кубический Галин Панциклический |
| Таблица графиков и параметров | |
В математической области теории графов , то графы Frucht представляет собой 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] граф Фрухта дает пример этой реализации для тривиальной группы .
Характеристический полином графа Frucht является .
Галерея [ править ]
Хроматическое число от Frucht графа 3.
Граф Фрухта гамильтонов .
См. Также [ править ]
 | Викискладе есть медиафайлы, связанные с графом Фрухта . |
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. "График Фрухта" . MathWorld .
- ^ a b Frucht, R. (1939), «Herstellung von Graphen mit vorgegebener abstrakter Gruppe». , Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804 .
- ^ Буссемейкер, ФК; Cobeljic, S .; Цветкович, DM; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов , отчет EUT, 76-WSK-01, кафедра математики и вычислительной техники, Технологический университет Эйндховена
- ^ Frucht, R. (1949), "Графы третьей степени с данной абстрактной группы", Canadian Journal математики , 1 : 365-378, DOI : 10,4153 / CJM-1949-033-6 , ISSN 0008-414X , MR 0032987 .