Petersen-Graph

{{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#ifexpr: {{#iferror:{{#ifexpr:{{#switch:N {{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#if: {{#expr: 0 = 0 OR 0 = 1 }} {{#if: {{#expr: 1 = 0 OR 1 = 1 }} {{#ifeq: {{#expr: {{#invoke:Expr|TemplateMax}} }} }} {{#ifeq:{{#expr: 0 + 0 + 0 + 0 + 0 + 1 + 0 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N {{#ifexpr: {{#invoke:Expr|TemplateMin}}|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Chromatische Zahl|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |3|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" colspan="2" | Fehler: Chromatische Zahl muss eine ganze Zahl sein. }} {{#ifexpr: {{#invoke:Expr|TemplateMin}}|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Chromatischer Index|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |4|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" colspan="2" | Fehler: Chromatischer Index muss eine ganze Zahl sein. }} {{#ifexpr: {{#invoke:Expr|TemplateMin}}|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Knotenzusammenhang|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |3|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" colspan="2" | Fehler: knotenzusammenhangszahl muss eine ganze Zahl sein. }} {{#ifexpr: {{#invoke:Expr|TemplateMin}} {{#ifexpr: {{#invoke:Expr|TemplateMin}}|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Schnittzahl|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |2|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" colspan="2" | Fehler: Schnittzahl muss eine ganze Zahl sein. }} {{#if:<math>t(t - 1)(t - 2)(t^7 - 12t^6 + 67t^5 - </math>
<math>230t^4 + 529t^3 - 814t^2 + 775t - 352)</math>|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Chromatisches Polynom|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |<math>t(t - 1)(t - 2)(t^7 - 12t^6 + 67t^5 - </math>
<math>230t^4 + 529t^3 - 814t^2 + 775t - 352)</math>|}} {{#if:<math>(t-1)^5(t+2)^4(t-3)</math>|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Charakteristisches Polynom|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |<math>(t-1)^5(t+2)^4(t-3)</math>|}} {{#if:|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Tuttepolynom|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" ||}} {{#ifexpr:{{#invoke:Expr|TemplateMax}}=1|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | LCF-Notation|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |{{{LCF}}}|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" colspan="2" | Fehler: Damit eine LCF-Notation existieren kann, muss der Graph hamiltonsch und kubisch sein. Bitte prüfe deine Eingabe erneut und setze dann hamiltonsch=1, sowie regularität=3.}}

{{#if:|{{{name}}}|Petersen-Graph}}
Datei:Petersen graph.svg}} [[Datei:{{{bild_2}}}|120px|]]}} }} }}
Benannt nach	Julius Peter Christian Petersen
Größe	10 Knoten, 15 Kanten
	colspan="2" | Fehler: zulässige Werte von hamiltonsch sind 0 oder 1
	colspan="2" | Fehler: zulässige Werte von eulersch sind 0 oder 1
R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }}		colspan="2" | Fehler: zulässige Werte von regularität sind natürliche Zahlen mit Null
	colspan="2" | Fehler: zulässige Werte von planar sind 0 oder 1
	colspan="2" | Fehler: zulässige Werte von bipartit sind 0 oder 1
	colspan="2" | Fehler: zulässige Werte von azyklisch sind 0 oder 1
	colspan="2" | Fehler: zulässige Werte von perfekt sind 0 oder 1
	colspan="2" | Fehler: zulässige Werte von snark sind 0 oder 1
1		colspan="2" | Fehler: azyklische Graphen sind stets biparit und planar, sowie nicht eulersch und nicht hamiltonsch
R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} }}|0||| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Eigenschaften|| style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" |{{#ifeq:0|1|hamiltonsch{{#ifeq:{{#expr: 0 + 0 + 0 + 0 + 1 + 0 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}}}{{#ifeq:0|1|eulersch{{#ifeq:{{#expr: 0 + 0 + 0 + 1 + 0 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}}}{{#ifeq:1|1|snark{{#ifeq:{{#expr: 0 + 0 + 0 + 0 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}}}{{#ifeq:0|1|perfekt{{#ifeq:{{#expr: 0 + 0 + 0 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}}}{{#ifeq: 0|1|azyklisch{{#ifeq:{{#expr: 1 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}|{{#ifeq:0|1|planar{{#ifeq:{{#expr: 0 + 1 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}||.|, }}}}{{#ifeq:0|1|bipartit{{#ifeq:{{#expr: 1 + {{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}} -->}}|0|.|, }}}}}}{{#ifeq:{{#if: {{#iferror:{{#ifexpr:{{#switch:N	R+ = abs	R- = -abs	Z = trunc	Z+	N = abs trunc	round ({{{3}}}) }} | 1 }} }} |1|0}}|1|{{#ifexpr: 3=3|kubisch|3-regulär}}.}} }}
style="border-top: solid 1px #CCD2D9; padding: 0 .3em;" | Cliquenzahl	2	Fehler: Cliquenzahl muss eine ganze Zahl sein. }}

{{#ifeq:||

{{#if: 0 | {{#ifexpr: 0 =1 ||}} }} {{#if: 0 | {{#ifexpr: 0 =1 ||}} }} {{#if: 0 | {{#ifexpr: 0 =1 ||}} }} {{#if: 1 | {{#ifexpr: 1 =1 ||}} }} {{#if: 0 | {{#ifexpr: 0 =1 ||}} }} {{#if: 3 | {{#ifexpr: {{#if: {{#iferror:{{#ifexpr:{{#switch:N | R+ = abs | R- = -abs | Z = trunc | Z+ | N = abs trunc | Z- = -abs trunc}}(3) = (3) {{#if: | round ({{{3}}}) }} | 1 }} }} |1|0}} =1 ||}} }} {{#if: | {{#ifexpr: {{#invoke:Expr|TemplateMin}} = 1 || {{#ifexpr:0=1|}} }} }} {{#if: 0 | {{#ifexpr: {{#invoke:Expr|TemplateMin}}=1 ||}} }} {{#if: 0 | {{#ifexpr: {{#invoke:Expr|TemplateMin}}=1 ||}} }} | {{#if: 0 | {{#ifexpr: 0 =1 |Kategorie:Azyklischer Graph|}} }} {{#if: 0 | {{#ifexpr: 0 =1 |Kategorie:Eulerscher Graph|}} }} {{#if: 0 | {{#ifexpr: 0 =1 |Kategorie:Hamiltonscher Graph|}} }} {{#if: 1 | {{#ifexpr: 1 =1 |Kategorie:Snark|}} }} {{#if: 0 | {{#ifexpr: 0 =1 |Kategorie:Perfekter Graph|}} }} {{#if: 3 | {{#ifexpr: {{#if: {{#iferror:{{#ifexpr:{{#switch:N | R+ = abs | R- = -abs | Z = trunc | Z+ | N = abs trunc | Z- = -abs trunc}}(3) = (3) {{#if: | round ({{{3}}}) }} | 1 }} }} |1|0}} =1 |Kategorie:Regulärer Graph|}} }} {{#if: | {{#ifexpr: {{#invoke:Expr|TemplateMin}} = 1 |Kategorie:Regulärer Graph | {{#ifexpr:0=1|Kategorie:Kubischer Graph}} }} }} {{#if: 0 | {{#ifexpr: {{#invoke:Expr|TemplateMin}}=1 |Kategorie:Bipartiter Graph|}} }} {{#if: 0 | {{#ifexpr: {{#invoke:Expr|TemplateMin}}=1 |Kategorie:Planarer Graph|}} }} }}

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

Datei:PetersenBarveniHran.svg

Eine optimale Kantenfärbung des Petersen-Graphen.

Datei:Petersen graph 3-coloring.svg

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<ref name=petersen>{{#invoke:Vorlage:Literatur|f}}</ref>.

Weblinks

• {{#if: | {{{author}}} | Eric W. Weisstein }}: Petersen-Graph. In: MathWorld (englisch). {{#if: PetersenGraph | {{#ifeq: {{#property:P2812}} | PetersenGraph | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}

Datei:Commons-logo.svg

[{{canonicalurl:Commons:Category:{{#if:Petersen graph|Petersen graph|Petersen-Graph}}|uselang=de}} Commons: {{#if:Petersen-Graph|Petersen-Graph|{{#if:Petersen graph|Petersen graph|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Petersen graph

   | {{#ifeq: {{#invoke:Str|left|petersen graph|9}} 
       | category: 

| }}}}

Einzelnachweise

<references />