Greve Fruhta
| Greve Fruhta | |
|---|---|
| Döpt efter | Robert Frucht |
| Toppar | 12 |
| revben | arton |
| Radie | 3 |
| Diameter | fyra |
| Omkrets | 3 |
| Automorfismer | 1 (identisk) |
| Kromatiskt nummer | 3 |
| Kromatiskt index | 3 |
| Egenskaper |
kubisk plan Hamiltonian |
| Mediafiler på Wikimedia Commons | |
Frucht-grafen är en av två minimala kubiska grafer som inte har icke-triviala automorfismer . Beskrevs av Robert Frucht 1939. [1]
Egenskaper
Greve Fruhta:
- Har inga icke-triviala symmetrier [2] ;
- Har 12 hörn och 18 kanter;
- Är en kubikgraf ;
- Är en kant-k-kopplad graf ;
- Har radie 3, diameter 4, omkrets 3, kromatiskt nummer 3, kromatiskt index 3, oberoende nummer 5;
- Frucht-grafen är Hamiltonsk och ges av en LCF-kod
![{\displaystyle [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2a4e6b7dd4767afd081e8a2a4e28e1272e5fd9)
-
Färgläggning i tre färger.
- Greve Fruhta är greve Halin .
- Liksom alla Halin-grafer är Frucht-grafen plan , 3 -vertex-ansluten och en polytopgraf .
- Frucht-grafen är en av de två minimala kubiska graferna som har en enda automorfism , identiteten [3] (sålunda kan vilken vertex som helst vara topologiskt skild från resten). Sådana grafer kallas asymmetriska grafer.
- Fruchts sats anger att vilken grupp som helst kan representeras som symmetrigruppen i en graf, [1] och en förstärkning av denna sats, även Fruchts, anger att vilken grupp som helst kan representeras som symmetrigruppen i en 3-regelbunden graf [4] Frucht-grafen ger ett exempel på en sådan implementering för triviala grupper .
- Det karakteristiska polynomet i Frucht-grafen är .
Länkar
- ↑ 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 Graf på Wolfram MathWorld- webbplatsen .
- ↑ Skiena, S. Implementering av diskret matematik: kombinatorik och grafteori med Mathematica. Reading, MA: Addison-Wesley, 1990
- ↑ R. Frucht. Grafer över grad tre med en given abstrakt grupp // Canadian Journal of Mathematics . - 1949. - T. 1 . — S. 365–378 . — ISSN 0008-414X . - doi : 10.4153/CJM-1949-033-6 . .