Граф Фрухта

Граф Фрухта — один из двух минимальных кубических графов, не имеющих нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939.

Граф Фрухта
Назван в честь	Роберта Фрухта
Вершин	12
Рёбер	18
Радиус	3
Диаметр	4
Обхват	3
Автоморфизмы	1 (тождественный)
Хроматическое число	3
Хроматический индекс	3
Свойства	кубический планарный гамильтонов
Медиафайлы на Викискладе

СвойстваПравить

Граф Фрухта:

• Не имеет нетривиальных симметрий;

• Имеет 12 вершин и 18 рёбер;

• Является кубическим графом;

• Является рёберно k-связным графом;

• Имеет радиус 3, диаметр 4, обхват 3, хроматическое число 3, хроматический индекс 3, число независимости равно 5;

• Граф Фрухта является гамильтоновым и задётся LCF-кодом

  $[-<!--\; -\; -->5,-<!--\; -\; -->2,-<!--\; -\; -->4,2,5,-<!--\; -\; -->2,2,5,-<!--\; -\; -->2,-<!--\; -\; -->5,4,2].$$[-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].$ 

•  

  Раскраска в три цвета.

•  

  Гамильтонов цикл.

• Граф Фрухта — это граф Халина.

• Как и все графы Халина, граф Фрухта является планарным, 3-вершинно-связным и графом многогранника.

• Граф Фрухта — один из двух минимальных кубических графов, имеющих единственный автоморфизм — тождественность (таким образом, любая вершина может быть топологически отличима от остальных). Такие графы называются асимметричными графами.
  • Теорема Фрухта утверждает, что любую группу можно представить как группу симметрий графа, а усиление этой теоремы, тоже Фрухта, утверждает, что любая группа может быть представлена как группа симметрий 3-регулярного графа Граф Фрухта даёт пример такой реализации для тривиальной группы.

• Характеристический многочлен графа Фрухта равен $(x-<!--\; -\; -->3)(x-<!--\; -\; -->2)x(x+1)(x+2)(x^3+x^2-<!--\; -\; -->2x-<!--\; -\; -->1)(x^4+x^3-<!--\; -\; -->6x^2-<!--\; -\; -->5x+4)$$(x-3) (x-2) x (x+1) (x+2) (x^3+x^2-2 x-1) (x^4+x^3-6 x^2-5 x+4)$ .