Heawood-Graph
In der Mathematik ist der Heawood-Graph ein Graph mit 14 Knoten und 21 Kanten, der unter anderem als Inzidenzgraph der Fano-Ebene von Bedeutung ist. Er ist nach Percy Heawood benannt.
Kombinatorische Eigenschaften
Der Heawood-Graph ist ein kubischer Graph, d. h. 3-regulär.
Er ist bipartit und hat deshalb die chromatische Zahl 2.
Er hat Durchmesser 3 und ist der einzige kubische Graph, der keinen Zykel der Länge 5 enthält.
Symmetrien
Die Automorphismengruppe des Heawood-Graphen ist isomorph zur projektiven linearen Gruppe und hat demzufolge 336 Elemente.
Der Heawood-Graph ist abstandstransitiv, d. h. zu je zwei Punktpaaren mit gibt es einen Automorphismus, der auf und auf abbildet.
Der Heawood-Graph in Geometrie und Topologie
Der Heawood-Graph ist der Inzidenzgraph der Fano-Ebene.
Er kann kreuzungsfrei in den Torus eingebettet werden, den er in 7 sich paarweise berührende Regionen zerlegt. Insbesondere ist er dual zum vollständigen Graphen .
Weblinks
- Wolfram MathWorld: Heawood Graph
Auf dieser Seite verwendete Medien
Autor/Urheber: Koko90, Lizenz: CC BY-SA 3.0
The chromatic number of the Heawood graph is 2. Layout from LCF with Graphviz (and GAP + GRAPE + G-GRAPE).
A partition of the torus into seven mutually adjacent regions, requiring seven colors. The torus is shown unrolled onto a square; points on the top edge of the square should be thought of as connected to the corresponding points on the bottom edge of the square, and points on the left edge of the square should be thought of as connected to the corresponding points on the right edge of the square. The edges and vertices of the regions form an embedding of the en:Heawood graph onto the torus. A combinatorially equivalent partition of the torus into regions forms the set of faces of the en:Szilassi polyhedron.
Category:Mathematics images