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 t ( t − 1 ) ( t − 2 ) ( t 7 − 12 t 6 + 67 t 5 − {\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-}
230 t 4 + 529 t 3 − 814 t 2 + 775 t − 352 ) {\displaystyle 230t^{4}+529t^{3}-814t^{2}+775t-352)}
Charakteristisches Polynom ( t − 1 ) 5 ( t + 2 ) 4 ( t − 3 ) {\displaystyle (t-1)^{5}(t+2)^{4}(t-3)}
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

Commons: Petersen-Graph – Sammlung von Bildern, Videos und Audiodateien