Quelltext der Seite Petersen-Graph

{{Infobox Graph
| bild_1 = Petersen_graph.svg
| benennerIn = Julius Peter Christian Petersen
| knoten = 10
| kanten = 15
| radius = 2
| hamiltonsch = 0
| eulersch = 0
| planar = 0
| bipartit = 0
| azyklisch = 0
| perfekt = 0
| snark = 1
| knotenzusammenhang = 3
| cliquenzahl = 2
| regularität = 3
| schnittzahl = 2
| chromatischeZahl = 3
| chromatischerIndex = 4
| charakteristisch = <math>(t-1)^5(t+2)^4(t-3)</math>
| chromatisch = <math>t(t - 1)(t - 2)(t^7 - 12t^6 + 67t^5 - </math><br /><math>230t^4 + 529t^3 - 814t^2 + 775t - 352)</math>
| tutte = 
}}

Der '''Petersen-Graph''' (benannt nach dem dänischen Mathematiker [[Julius Peter Christian Petersen|Julius Petersen]]) ist ein 3-[[Regulärer Graph|regulärer]] (also kubischer) [[Graph (Graphentheorie)|Graph]] mit 10 [[Knoten (Graphentheorie)|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 [[Tropische Geometrie|tropischen Geometrie]] auf.

Eigenschaften des Petersen-Graphen:

* Kubisch bzw. 3-[[Regulärer Graph|regulär]] (per [[Definition]])
* [[Weg (Graphentheorie)#Länge und Abstand|Radius]] und [[Weg (Graphentheorie)#Länge und Abstand|Durchmesser]] sind 2
* Geschlecht ist 1
* Nicht [[Planarer Graph|planar]]
* [[Zusammenhang von Graphen|Zusammenhängend]]
* [[Symmetrie (Geometrie)|Symmetrisch]]
* [[Stark regulärer Graph|Stark regulär]]
* [[Snark (Graphentheorie)|Snark]]
* Die Länge des kürzesten [[Zyklus (Graphentheorie)#Zyklischer Graph|Kreises]] ist 5
* Die Länge des längsten [[Zyklus (Graphentheorie)#Zyklischer Graph|Kreises]] ist 9
* Enthält keinen [[Hamiltonkreisproblem|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==
[[Datei:PetersenBarveniHran.svg|links|mini|209x209px|Eine optimale Kantenfärbung des Petersen-Graphen.]]
[[Datei:Petersen graph 3-coloring.svg|mini|204x204px|Eine optimale Knotenfärbung des Petersen-Graphen.]]
Der Petersen-Graph hat eine [[chromatische Zahl]] von 3, d.&nbsp;h. die Knoten müssen mit mindestens 3 Farben gefärbt werden, sodass jeweils zwei benachbarte Knoten unterschiedliche Farben haben. Der [[Chromatischer Index|chromatische Index]] ist 4, d.&nbsp;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 (Graphentheorie)|Snark-Graphen]]. Er ist der kleinste und von 1898 bis 1946 der einzige Graph, für den diese Eigenschaft nachgewiesen wurde<ref name=petersen>{{Literatur |Autor=Julius Petersen |Titel=Sur le théorème de Tait |Sammelwerk=L'Intermédiaire des Mathématiciens |Band=5 |Seiten=225–227 |Datum=1898 |Online=https://archive.org/details/lintermdiairede03lemogoog/page/n239}}</ref>. 

== Weblinks ==
* {{MathWorld
| id = PetersenGraph
| title = Petersen-Graph
}}
{{Commonscat|Petersen graph|Petersen-Graph}}

== Einzelnachweise ==
<references />

[[Kategorie:Regulärer Graph]]