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 ein Ramanujan-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 links|mini|209x209px|Eine optimale Kantenfärbung des Petersen-Graphen. mini|204x204px|Eine optimale Knotenfärbung des Petersen-Graphen. 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.
Weblinks
Einzelnachweise
Kategorie:Regulärer Graph