Petersen-Graph
Benannt nach | Julius Peter Christian Petersen |
Größe | 10 Knoten, 15 Kanten |
Eigenschaften | snark, kubisch. |
Chromatische Zahl | 3 |
Chromatischer Index | 4 |
Knotenzusammenhang | 3 |
Cliquenzahl | 2 |
Schnittzahl | 2 |
Chromatisches Polynom | |
Charakteristisches Polynom | |
LCF-Notation |
Der Petersen-Graph (benannt nach dem dänischen Mathematiker Julius Petersen) ist ein 3-regulärer (also kubischer) Graph mit 10 Knoten. Das bedeutet, dass jeder der Knoten drei Nachbarn hat, die Gradfolge ist also (3,3,3,3,3,3,3,3,3,3). Der Petersen-Graph ist in der Graphentheorie ein oft verwendetes Beispiel und Gegenbeispiel. Er tritt auch in der tropischen Geometrie auf.
Eigenschaften des Petersen-Graphen:
- Kubisch bzw. 3-regulär (per Definition)
- Nicht planar
- Zusammenhängend
- Symmetrisch
- Die Länge des kürzesten Kreises ist 5
- Enthält keinen Hamilton-Kreis
- Kleinster hypohamiltonscher Graph
- Chromatische Zahl (Graphentheorie) 3
- Chromatischer Index (Graphentheorie) 4
- Ist kein Cayley-Graph, obwohl er regulär und lokal-endlich ist.
Der Petersen-Graph gehört zu einer Gruppe von zusammenhängenden, brückenlosen und nicht planaren Graphen, die als „Snark“ bezeichnet werden.
Siehe auch: Typen von Graphen in der Graphentheorie in Graph (Graphentheorie)
Weblinks
- Eric W. Weisstein: Petersen-Graph. In: MathWorld (englisch).