Fruchts Grafik
| Fruchtgraph | |
|
Fruchts Grafik | |
| Anzahl der Scheitelpunkte | 12 |
|---|---|
| Anzahl Kanten | 18 |
| Abschlussverteilung | 3- regulär |
| Strahl | 3 |
| Durchmesser | 4 |
| Gittergewebe | 3 |
| Automorphismen | 1 ({ id }) |
| Chromatische Zahl | 3 |
| Chromatischer Index | 3 |
| Eigenschaften |
Kubischer Hamilton-Operator Planar Asymmetrisch |
Der Frucht-Graphen ist in der Graphentheorie ein 3-regulärer Graph mit 12 Ecken und 18 Kanten. Es ist der kleinste kubische Graph, dessen Automorphismusgruppe nur das neutrale Element enthält. Mit anderen Worten, es ist der kleinste reguläre Graph des dritten Grades, der ein asymmetrischer Graph ist . Es wurde erstmals 1939 von Robert Frucht beschrieben , daher der Name.
Eigenschaften
Allgemeine Eigenschaften
Der Frucht-Graphen ist planar und Hamiltonsch . Es ist auch ein Fall des Halin-Graphen .
Der Durchmesser des Frucht-Graphen, die maximale Exzentrizität seiner Eckpunkte, beträgt 4, sein Radius , die minimale Exzentrizität seiner Eckpunkte, beträgt 3 und sein Netz , die Länge seines kürzesten Zyklus , ist 3. Er hat einen 3- Eckpunkt -verbundener Graph und ein 3- kantenverbundener Graph , d.h. er ist zusammenhängend und um ihn getrennt zu machen, müssen ihm mindestens 3 Knoten oder 3 Kanten fehlen.
Färbung
Die chromatische Zahl des Frucht-Graphen ist 3. Das heißt, es ist möglich, ihn mit 3 Farben einzufärben, so dass zwei durch eine Kante verbundene Ecken immer unterschiedliche Farben haben, aber diese Zahl ist minimal. Es gibt keine gültige 2-Färbung des Diagramms.
Der chromatische Index des Frucht-Graphen ist 3. Es gibt also eine 3-Färbung der Kanten des Graphen, so dass zwei Kanten, die auf die gleichen Ecken fallen, immer unterschiedliche Farben haben. Diese Zahl ist minimal.
Es ist möglich, die unterschiedlichen Färbungen eines Graphen zu zählen. Dies ergibt eine Funktion, die von der Anzahl der erlaubten Farben abhängt. Diese Funktion ist polynomial und wird als das chromatische Polynom des Graphen bezeichnet. Dieses Polynom hat Wurzeln alle positiven ganzen Zahlen oder Nullen, die streng kleiner als 3 Grad und 12 sind. Es ist gleich: .
Algebraische Eigenschaften
Die Automorphismusgruppe des Frucht-Graphen enthält nur das neutrale Element. Er hat also die Ordnung 1. Damit ist Fruchts Graph ein asymmetrischer Graph .
Das charakteristische Polynom der Adjazenzmatrix des Frucht-Graphen ist: .
Galerie
-
Der Fruchtgraph ist planar
-
Der Fruchtgraph ist Hamiltonsch is
-
Der Fruchtgraph lässt eine 3-Färbung zu
Siehe auch
Interne Links
Verweise
- (de) Weisstein, Eric W "Frucht Graph." Von MathWorld - Eine Webressource von Wolfram
- (in) Skiena S. Implementieren von diskreter Mathematik: Kombinatorik und Graphentheorie mit Mathematica. Lesen, MA: Addison-Wesley, 1990
- (de) "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Komp. Mathematik. 6, 239-250, 1939