Grev Fruhta
| Grev Fruhta | |
|---|---|
| Opkaldt efter | Robert Frucht |
| Toppe | 12 |
| ribben | atten |
| Radius | 3 |
| Diameter | fire |
| Omkreds | 3 |
| Automorfismer | 1 (identisk) |
| Kromatisk tal | 3 |
| Kromatisk indeks | 3 |
| Ejendomme |
kubisk plan Hamiltonian |
| Mediefiler på Wikimedia Commons | |
Frucht-grafen er en af to minimale kubiske grafer , der ikke har ikke-trivielle automorfier . Beskrevet af Robert Frucht i 1939. [1]
Egenskaber
Grev Fruhta:
- Har ingen ikke-trivielle symmetrier [2] ;
- Har 12 hjørner og 18 kanter;
- Er en kubisk graf ;
- Er en kant k-forbundet graf ;
- Har radius 3, diameter 4, omkreds 3, kromatisk nummer 3, kromatisk indeks 3, uafhængighedsnummer 5;
- Frucht-grafen er Hamiltonsk og er givet af en LCF-kode
![{\displaystyle [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2a4e6b7dd4767afd081e8a2a4e28e1272e5fd9)
-
Farvelægning i tre farver.
- Grev Fruhta er grev Halin .
- Som alle Halin-grafer er Frucht-grafen plan , 3 -vertex-forbundet og en polytopgraf .
- Frucht-grafen er en af de to minimale kubiske grafer , der har en enkelt automorfi , identiteten [3] (således kan ethvert vertex være topologisk adskilt fra resten). Sådanne grafer kaldes asymmetriske grafer.
- Fruchts sætning siger, at enhver gruppe kan repræsenteres som symmetrigruppen i en graf, [1] og en styrkelse af denne sætning, også Fruchts, siger, at enhver gruppe kan repræsenteres som symmetrigruppen af en 3-regulær graf [4] Frucht-grafen giver et eksempel på en sådan implementering for trivielle grupper .
- Frucht-grafens karakteristiske polynomium er .
Links
- ↑ 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- webstedet .
- ↑ Skiena, S. Implementering af diskret matematik: kombinatorik og grafteori med Mathematica. Reading, MA: Addison-Wesley, 1990
- ↑ R. Frucht. Grafer for grad tre med en given abstrakt gruppe // Canadian Journal of Mathematics . - 1949. - T. 1 . — S. 365–378 . — ISSN 0008-414X . - doi : 10.4153/CJM-1949-033-6 . .