В теорії графів Графом Фрухта називається 3-регулярний граф з 12 вершинами і 18 ребрами без нетривіальних симетрій. Граф вперше був описаний [en] в 1939 році.
Граф Фрухта | |
---|---|
Граф Роберта Фрухта | |
(Вершин) | 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-регулярного графу. Граф Фрухта дає приклад такої реалізації для тривіальної групи.
Характеристичний многочлен графу Фрухта дорівнює .
Галерея
- Хроматичне число графу Фрухта дорівнює 3.
- Граф Фрухта є гамільтоновим.
Посилання
- Weisstein, Eric W. Frucht Graph(англ.) на сайті Wolfram MathWorld.
- R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. // Compositio Mathematica. — 1939. — Т. 6. — С. 239–250. — ISSN 0010-437X..
- Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
- R. Frucht. Graphs of degree three with a given abstract group // . — 1949. — Т. 1. — С. 365–378. — ISSN 0008-414X. — DOI: . з джерела 6 липня 2011. Процитовано 2016-01-13..
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv Grafom Fruhta nazivayetsya 3 regulyarnij graf z 12 vershinami i 18 rebrami bez netrivialnih simetrij Graf vpershe buv opisanij en v 1939 roci Graf FruhtaGraf Roberta FruhtaVershin 12Reber 18Radius 3Diametr 4Obhvat 3Avtomorfizm 1 totozhnij Hromatichne chislo 3Hromatichnij indeks 3Vlastivosti kubichnij planarnij gamiltoniv Graf Fruhta ce graf Halina z hromatichnim chislom 3 hromatichnim indeksom 3 radiusom 3 diametrom 4 i obhvatom 3 Yak i vsi grafi Halina graf Fruhta ye planarnim 3 vershinno zv yaznim i bagatogrannim grafom Vin takozh ye k reberno zv yaznim grafom Jogo chislo nezalezhnosti dorivnyuye 5 Graf Fruhta ye gamiltonovim i mozhe buti pobudovanij za LCF zapisom 5 2 4 2 5 2 2 5 2 5 4 2 Algebrayichni vlastivostiGraf Fruhta ce odin z dvoh minimalnih kubichnih grafiv sho mayut yedinij avtomorfizm totozhnist takim chinom bud yaka vershina mozhe buti topologichno vidrizana vid inshih Taki grafi nazivayutsya asimetrichnimi grafami Teorema Fruhta stverdzhuye sho bud yaku grupu mozhna predstaviti yak grupu simetrij grafu a posilennya ciyeyi teoremi tezh Fruht stverdzhuye sho bud yaka grupa mozhe buti predstavlena yak grupa simetrij 3 regulyarnogo grafu Graf Fruhta daye priklad takoyi realizaciyi dlya trivialnoyi grupi Harakteristichnij mnogochlen grafu Fruhta dorivnyuye 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 displaystyle x 3 x 2 x x 1 x 2 x 3 x 2 2x 1 x 4 x 3 6x 2 5x 4 GalereyaHromatichne chislo grafu Fruhta dorivnyuye 3 Graf Fruhta ye gamiltonovim PosilannyaWeisstein Eric W Frucht Graph angl na sajti Wolfram MathWorld R Frucht Herstellung von Graphen mit vorgegebener abstrakter Gruppe Compositio Mathematica 1939 T 6 S 239 250 ISSN 0010 437X Skiena S Implementing Discrete Mathematics Combinatorics and Graph Theory with Mathematica Reading MA Addison Wesley 1990 R Frucht Graphs of degree three with a given abstract group 1949 T 1 S 365 378 ISSN 0008 414X DOI 10 4153 CJM 1949 033 6 z dzherela 6 lipnya 2011 Procitovano 2016 01 13