Fruhta gróf
| Fruhta gróf | |
|---|---|
| Valaki után elnevezve | Robert Frucht |
| Csúcsok | 12 |
| borda | tizennyolc |
| Sugár | 3 |
| Átmérő | négy |
| Heveder | 3 |
| Automorfizmusok | 1 (azonos) |
| Kromatikus szám | 3 |
| Kromatikus index | 3 |
| Tulajdonságok |
köbös síkbeli Hamiltoni |
| Médiafájlok a Wikimedia Commons oldalon | |
A Frucht-gráf egyike annak a két minimális köbös gráfnak , amelyek nem rendelkeznek nem triviális automorfizmusokkal . Robert Frucht írta le 1939-ben. [1]
Tulajdonságok
Fruhta gróf:
- Nincsenek nem triviális szimmetriái [2] ;
- 12 csúcsa és 18 éle van;
- Egy köbös gráf ;
- Egy k élű gráf ;
- Sugárja 3, átmérője 4, kerülete 3, kromatikus száma 3, kromatikus indexe 3, függetlenségi száma 5;
- A Frucht gráf Hamilton -féle , és egy LCF-kód adja
![{\displaystyle [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2a4e6b7dd4767afd081e8a2a4e28e1272e5fd9)
-
Színezés három színben.
- Fruhta gróf Halin gróf .
- Mint minden Halin-gráf, a Frucht-gráf síkbeli , 3 -csúccsal összefüggő és politóp gráf .
- A Frucht gráf egyike annak a két minimális köbös gráfnak , amelyeknek egyetlen automorfizmusa van , az azonosság [3] (tehát bármely csúcs topológiailag elkülönülhet a többitől). Az ilyen gráfokat aszimmetrikus gráfoknak nevezzük .
- Frucht tétele kimondja, hogy bármely csoport ábrázolható egy gráf szimmetriacsoportjaként, [1] és ennek a tételnek a megerősítése, szintén Frucht tétele azt állítja, hogy bármely csoport ábrázolható egy 3-reguláris gráf szimmetriacsoportjaként [4]. A Frucht gráf példát ad a triviális csoport ilyen megvalósítására .
- A Frucht-gráf karakterisztikus polinomja : .
Linkek
- ↑ 1 2 R. Frucht. A Graphen által kifejlesztett elvont absztrakt csoport. Compositio Mathematica. - 1939. - T. 6 . — S. 239–250 . — ISSN 0010-437X . .
- ↑ Weisstein, Eric W. Frucht Graph a Wolfram MathWorld webhelyen .
- ↑ Skiena, S. A diszkrét matematika megvalósítása: Kombinatorika és gráfelmélet a Mathematicával. Reading, MA: Addison-Wesley, 1990
- ↑ R. Frucht. Harmadik fokozat grafikonjai egy adott absztrakt csoporttal // Canadian Journal of Mathematics . - 1949. - T. 1 . – S. 365–378 . — ISSN 0008-414X . - doi : 10.4153/CJM-1949-033-6 . .