Hrabě Fruhta
| hrabě Fruhta | |
|---|---|
| Pojmenoval podle | Robert Frucht |
| Vrcholy | 12 |
| žebra | osmnáct |
| Poloměr | 3 |
| Průměr | čtyři |
| obvod | 3 |
| Automorfismy | 1 (stejné) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
kubický rovinný Hamiltonián |
| Mediální soubory na Wikimedia Commons | |
Fruchtův graf je jedním ze dvou minimálních kubických grafů , které nemají netriviální automorfismy . Popsal Robert Frucht v roce 1939. [1]
Vlastnosti
hrabě Fruhta:
- Má 12 vrcholů a 18 hran;
- Je kubický graf ;
- Má poloměr 3, průměr 4, obvod 3, chromatické číslo 3, chromatický index 3, číslo nezávislosti 5;
- Fruchtův graf je hamiltonovský a je dán kódem LCF
![{\displaystyle [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2a4e6b7dd4767afd081e8a2a4e28e1272e5fd9)
-
Barvení ve třech barvách.
- Hrabě Fruhta je hrabě Halin .
- Stejně jako všechny Halinovy grafy je i Fruchtův graf rovinný , spojený se 3 vrcholy a polytopový graf .
- Fruchtův graf je jedním ze dvou minimálních kubických grafů , které mají jediný automorfismus , identitu [3] (takže jakýkoli vrchol může být topologicky odlišný od zbytku). Takové grafy se nazývají asymetrické grafy.
- Fruchtův teorém říká, že jakákoli grupa může být reprezentována jako grupa symetrie grafu, [1] a posílení této věty, také Fruchtova, říká, že jakákoli grupa může být reprezentována jako grupa symetrie 3-regulárního grafu [4]. Fruchtův graf uvádí příklad takové implementace pro triviální skupinu .
- Charakteristický polynom Fruchtova grafu je .
Odkazy
- ↑ 1 2 R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. // Compositio Mathematica. - 1939. - T. 6 . — S. 239–250 . — ISSN 0010-437X . .
- ↑ Weisstein, Eric W. Frucht Graph na webu Wolfram MathWorld .
- ↑ Skiena, S. Implementace diskrétní matematiky: Kombinatorika a teorie grafů pomocí Mathematica. Reading, MA: Addison-Wesley, 1990
- ↑ R. Frucht. Grafy třetího stupně s danou abstraktní skupinou // Canadian Journal of Mathematics . - 1949. - T. 1 . — S. 365–378 . — ISSN 0008-414X . - doi : 10.4153/CJM-1949-033-6 . .