В теорії графів Графом Фрухта називається 3-регулярний граф з 12 вершинами і 18 ребрами без нетривіальних симетрій[1]. Граф вперше був описаний Робертом Фрухтом[en] в 1939 році[2].

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

Граф Фрухта — це граф Халіна з хроматичним числом 3, хроматичним індексом 3, радіусом 3, діаметром 4 і обхватом 3. Як і всі графи Халіна, граф Фрухта є планарним, 3-вершинно-зв'язним і багатогранним графом. Він також є k-реберно-зв'язним графом. Його число незалежності дорівнює 5.

Граф Фрухта є гамільтоновим і може бути побудований за LCF-записом [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].

Алгебраїчні властивостіРедагувати

Граф Фрухта — це один з двох мінімальних кубічних графів, що мають єдиний автоморфізм — тотожність[3] (таким чином, будь-яка вершина може бути топологічно відрізана від інших). Такі графи називаються асиметричними графами. Теорема Фрухта стверджує, що будь-яку групу можна представити як групу симетрій графу[2], а посилення цієї теореми, теж Фрухт, стверджує, що будь-яка група може бути представлена ​​як група симетрій 3-регулярного графу[4]. Граф Фрухта дає приклад такої реалізації для тривіальної групи.

Характеристичний многочлен графу Фрухта дорівнює  .

ГалереяРедагувати

СсылкиРедагувати

  1. Weisstein, Eric W. Frucht Graph(англ.) на сайті Wolfram MathWorld.
  2. а б R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. // Compositio Mathematica. — 1939. — Т. 6. — С. 239–250. — ISSN 0010-437X..
  3. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
  4. R. Frucht. Graphs of degree three with a given abstract group // Canadian Journal of Mathematics. — 1949. — Т. 1. — С. 365–378. — ISSN 0008-414X. — DOI:10.4153/CJM-1949-033-6..