Petersen-Graph
| 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 | <math>t(t - 1)(t - 2)(t^7 - 12t^6 + 67t^5 - </math> <math>230t^4 + 529t^3 - 814t^2 + 775t - 352)</math> |
| Charakteristisches Polynom | <math>(t-1)^5(t+2)^4(t-3)</math> |
| LCF-Notation | {{{LCF}}} |
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)
- Radius und Durchmesser sind 2
- Geschlecht ist 1
- Nicht planar
- Zusammenhängend
- Symmetrisch
- Stark regulär
- Snark
- Die Länge des kürzesten Kreises ist 5
- Die Länge des längsten Kreises ist 9
- Enthält keinen Hamilton-Kreis
- Kleinster hypohamiltonscher Graph
- Ist kein Cayley-Graph, obwohl er regulär und lokal-endlich ist.
- Ist ein Einheitsdistanz-Graph, da er eine Darstellung besitzt, bei der alle Kanten Einheitslänge haben.
Färbung
Der Petersen-Graph hat eine chromatische Zahl von 3, d. h. die Knoten müssen mit mindestens 3 Farben gefärbt werden, sodass jeweils zwei benachbarte Knoten unterschiedliche Farben haben. Der chromatische Index ist 4, d. h. man benötigt mindestens 4 Farben um alle Kanten so einzufärben, dass die inzidente Kanten jedes Knoten paarweise verschiedene Farben haben. Da der Petersen-Graph brückenlos und kubisch ist, aber einen chromatischen Index von 4 besitzt, zählt der Petersen-Graph zu den sogenannten Snark-Graphen. Er ist der kleinste und von 1898 bis 1946 der einzige Graph, für den diese Eigenschaft nachgewiesen wurde<ref name=petersen>Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).</ref>.
Weblinks
- Eric W. Weisstein: Petersen-Graph. In: MathWorld (englisch).
Einzelnachweise
<references />