Граф Фрухта - Frucht graph

Граф Фрухта
Граф Фрухта
Названный в честь	Роберт Фрухт
Вершины	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] граф Фрухта является примером этой реализации для тривиальная группа.

В характеристический многочлен графа Фрухта есть ${displaystyle (x-3) (x-2) x (x + 1) (x + 2) (x ^ {3} + x ^ {2} -2x-1) (x ^ {4} + x ^ { 3} -6x ^ {2} -5x + 4)}$.

Галерея

• 

  В хроматическое число графа Фрухта равно 3.

• 

  Граф Фрухта Гамильтониан.

Смотрите также

Рекомендации