https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Petersen-GraphPetersen-Graph - Versionsgeschichte2026-05-26T17:16:10ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Petersen-Graph&diff=147247&oldid=previmported>Simplicial Vertex: Artikel erweitert und zwei Bilder hinzugefügt2026-03-19T23:14:21Z<p>Artikel erweitert und zwei Bilder hinzugefügt</p>
<p><b>Neue Seite</b></p><div>{{Infobox Graph<br />
| bild_1 = Petersen_graph.svg<br />
| benennerIn = Julius Peter Christian Petersen<br />
| knoten = 10<br />
| kanten = 15<br />
| radius = 2<br />
| hamiltonsch = 0<br />
| eulersch = 0<br />
| planar = 0<br />
| bipartit = 0<br />
| azyklisch = 0<br />
| perfekt = 0<br />
| snark = 1<br />
| knotenzusammenhang = 3<br />
| cliquenzahl = 2<br />
| regularität = 3<br />
| schnittzahl = 2<br />
| chromatischeZahl = 3<br />
| chromatischerIndex = 4<br />
| charakteristisch = <math>(t-1)^5(t+2)^4(t-3)</math><br />
| 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><br />
| tutte = <br />
}}<br />
<br />
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.<br />
<br />
Eigenschaften des Petersen-Graphen:<br />
<br />
* Kubisch bzw. 3-[[Regulärer Graph|regulär]] (per [[Definition]])<br />
* [[Weg (Graphentheorie)#Länge und Abstand|Radius]] und [[Weg (Graphentheorie)#Länge und Abstand|Durchmesser]] sind 2<br />
* Geschlecht ist 1<br />
* Nicht [[Planarer Graph|planar]]<br />
* [[Zusammenhang von Graphen|Zusammenhängend]]<br />
* [[Symmetrie (Geometrie)|Symmetrisch]]<br />
* [[Stark regulärer Graph|Stark regulär]]<br />
* [[Snark (Graphentheorie)|Snark]]<br />
* Die Länge des kürzesten [[Zyklus (Graphentheorie)#Zyklischer Graph|Kreises]] ist 5<br />
* Die Länge des längsten [[Zyklus (Graphentheorie)#Zyklischer Graph|Kreises]] ist 9<br />
* Enthält keinen [[Hamiltonkreisproblem|Hamilton-Kreis]]<br />
* Kleinster [[hypohamiltonscher Graph]]<br />
* Ist kein [[Cayley-Graph]], obwohl er regulär und lokal-endlich ist.<br />
* Ist ein [[Einheitsdistanz-Graph]], da er eine Darstellung besitzt, bei der alle Kanten Einheitslänge haben.<br />
<br />
==Färbung==<br />
[[Datei:PetersenBarveniHran.svg|links|mini|209x209px|Eine optimale Kantenfärbung des Petersen-Graphen.]]<br />
[[Datei:Petersen graph 3-coloring.svg|mini|204x204px|Eine optimale Knotenfärbung des Petersen-Graphen.]]<br />
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>. <br />
<br />
== Weblinks ==<br />
* {{MathWorld<br />
| id = PetersenGraph<br />
| title = Petersen-Graph<br />
}}<br />
{{Commonscat|Petersen graph|Petersen-Graph}}<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
[[Kategorie:Regulärer Graph]]</div>imported>Simplicial Vertex