Grev Fruhta
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 12 hjørner og 18 kanter;
- 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 .
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 . .