WikiSort.ru - Не сортированное

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

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

Свойства

Граф Фрухта

• имеет 12 вершин и 18 рёбр,
• 3-регулярный граф
• Не имеет нетривиальных симметрий.^[2]

• Граф Фрухта — это граф Халина с хроматическим числом 3.
  • Как и все графы Халина, граф Фрухта является планарным, 3-вершинно-связным и графом многогранника^[en].
• Является рёберно k-связным графом.
• Его число независимости равно 5.
• хроматическим индексом 3,
• радиусом 3,
• диаметр 4,
• обхватом 3.

• Граф Фрухта является гамильтоновым и может быть построен по LCF записи^[en]* [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

• Граф Фрухта — это один из двух минимальных кубических графов, имеющих единственный автоморфизм — тождественность^[3] (таким образом, любая вершина может быть топологически отличима от остальных). Такие графы называются асимметричными графами.
  • Теорема Фрухта утверждает, что любую группу можно представить как группу симметрий графа,^[1] а усиление этой теоремы, тоже Фрухта, утверждает, что любая группа может быть представлена как группа симметрий 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.
• 
  Граф Фрухта является гамильтоновым.

Ссылки

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.