Im mathematischen Feld der Graph-Theorie ist der Graph von Petersen ein ungeleiteter Graph mit 10 Scheitelpunkten und 15 Rändern. Es ist ein kleiner Graph, der als ein nützliches Beispiel und Gegenbeispiel für viele Probleme in der Graph-Theorie dient. Der Graph von Petersen wird für Julius Petersen genannt, der 1898 ihn gebaut hat, um der kleinste bridgeless Kubikgraph ohne drei Rand-Färben zu sein. Obwohl der Graph allgemein Petersen kreditiert wird, war es tatsächlich zuerst 12 Jahre früher, in einem Vortrag davon erschienen.

Donald Knuth stellt fest, dass der Graph von Petersen "eine bemerkenswerte Konfiguration ist, die als ein Gegenbeispiel vielen optimistischen Vorhersagen darüber dient, was für Graphen im Allgemeinen wahr sein könnte."

Aufbauten

Der Graph von Petersen ist die Ergänzung des Liniengraphen dessen. Es ist auch der Graph von Kneser; das bedeutet, dass es einen Scheitelpunkt für jede 2-Elemente-Teilmenge eines 5-Elemente-Satzes hat, und zwei Scheitelpunkte durch einen Rand verbunden werden, wenn, und nur wenn die entsprechenden 2-Elemente-Teilmengen von einander zusammenhanglos sind. Als ein Graph von Kneser der Form ist es ein Beispiel eines sonderbaren Graphen.

Geometrisch ist der Graph von Petersen der Graph, der durch die Scheitelpunkte und Ränder des Hemi-Dodekaeders, d. h. eines Dodekaeders mit entgegengesetzten Punkten, Linien und Gesichtern gebildet ist, identifiziert zusammen.

Embeddings

Der Graph von Petersen ist nichtplanar. Jeder nichtplanare Graph hat als Minderjährige entweder der ganze Graph oder der ganze zweiteilige Graph, aber der Graph von Petersen hat beide als Minderjährige. Der Minderjährige kann gebildet werden, indem er die Ränder eines vollkommenen Zusammenbringens, zum Beispiel die fünf kurzen Ränder im ersten Bild zusammenzieht. Der Minderjährige kann gebildet werden, indem er einen Scheitelpunkt (zum Beispiel der Hauptscheitelpunkt der 3-symmetrischen Zeichnung) und das Zusammenziehen eines Rand-Ereignisses jedem Nachbar des gelöschten Scheitelpunkts löscht.

Die allgemeinste und symmetrische Flugzeug-Zeichnung des Graphen von Petersen, als ein Pentagramm innerhalb eines Pentagons, hat fünf Überfahrten. Jedoch ist das nicht die beste Zeichnung, um Überfahrten zu minimieren; dort besteht eine andere Zeichnung (gezeigt in der Zahl) mit nur zwei Überfahrten. So hat der Graph von Petersen sich treffende Nummer 2. Auf einem Ring kann der Graph von Petersen ohne Rand-Überfahrten gezogen werden; es hat deshalb orientable Klasse 1.

Der Graph von Petersen kann auch (mit Überfahrten) im Flugzeug auf solche Art und Weise gezogen werden, dass alle Ränder gleiche Länge haben. D. h. es ist ein Einheitsentfernungsgraph.

Die einfachsten non-orientable erscheinen, auf dem der Graph von Petersen ohne Überfahrten eingebettet werden kann, ist das projektive Flugzeug. Das ist das durch den Hemi-Dodekaeder-Aufbau des Graphen von Petersen gegebene Einbetten. Das projektive Flugzeug-Einbetten kann auch aus der fünfeckigen Standardzeichnung des Graphen von Petersen durch das Stellen einer Quer-Kappe innerhalb des Fünf-Punkte-Sterns am Zentrum der Zeichnung und Routenplanung die Sternränder durch diese Quer-Kappe gebildet werden; die resultierende Zeichnung hat sechs fünfeckige Gesichter. Dieser Aufbau bildet eine regelmäßige Karte und zeigt, dass der Graph von Petersen non-orientable Klasse 1 hat.

Symmetries

Der Graph von Petersen ist (mit der Unterschrift srg (10,3,0,1)) stark regelmäßig. Es ist auch symmetrisch, bedeutend, dass es Rand transitiv und transitiver Scheitelpunkt ist. Stärker ist es 3 funken transitiv: Jeder geleitete Drei-Ränder-Pfad im Graphen von Petersen kann in jeden anderen solchen Pfad durch eine Symmetrie des Graphen umgestaltet werden.

Es ist einer von nur 13 mit der Entfernung regelmäßigen Kubikgraphen.

Die automorphism Gruppe des Graphen von Petersen ist die symmetrische Gruppe; die Handlung auf dem Graphen von Petersen folgt aus seinem Aufbau als ein Graph von Kneser. Jeder Homomorphismus des Graphen von Petersen zu sich, der angrenzende Scheitelpunkte nicht identifiziert, ist ein automorphism. Wie gezeigt, in den Zahlen können die Zeichnungen des Graphen von Petersen fünfwegige oder dreiseitige Symmetrie ausstellen, aber es ist nicht möglich, den Graphen von Petersen im Flugzeug auf solche Art und Weise zu ziehen, dass die Zeichnung die volle Symmetrie-Gruppe des Graphen ausstellt.

Trotz seines hohen Grads der Symmetrie ist der Graph von Petersen nicht ein Graph von Cayley. Es ist der kleinste mit dem Scheitelpunkt transitive Graph, der nicht ein Graph von Cayley ist.

Pfade von Hamiltonian und Zyklen

Der Graph von Petersen hat einen Pfad von Hamiltonian, aber keinen Zyklus von Hamiltonian. Es ist der kleinste bridgeless Kubikgraph ohne Zyklus von Hamiltonian. Es ist hypohamiltonian, bedeutend, dass, obwohl es keinen Zyklus von Hamiltonian hat, jeden Scheitelpunkt löschend, es Hamiltonian macht, und der kleinste hypohamiltonian Graph ist.

Weil ein begrenzter verbundener mit dem Scheitelpunkt transitiver Graph, der keinen Zyklus von Hamiltonian, der Graph von Petersen hat, ein Gegenbeispiel zu einer Variante der Vermutung von Lovász ist, aber die kanonische Formulierung der Vermutung bittet um einen Pfad von Hamiltonian und wird durch den Graphen von Petersen nachgeprüft.

Nur fünf mit dem Scheitelpunkt transitive Graphen ohne Zyklen von Hamiltonian sind bekannt: Der ganze Graph K, der Graph von Petersen, der Graph von Coxeter und die zwei Graphen sind auf die Graphen von Petersen und Coxeter durch das Ersetzen jedes Scheitelpunkts durch ein Dreieck zurückzuführen gewesen. Wenn G ein 2-verbundener, r-regular Graph mit höchstens 3r + 1 Scheitelpunkte ist, dann ist G Hamiltonian, oder G der Graph von Petersen ist.

Um zu sehen, dass der Graph von Petersen keinen Zyklus von Hamiltonian C hat, beschreiben wir die 3-regelmäßigen Zehn-Scheitelpunkte-Graphen, die wirklich einen Zyklus von Hamiltonian haben und zeigen, dass keiner von ihnen der Graph von Petersen, durch die Entdeckung eines Zyklus in jedem von ihnen ist, der kürzer ist als jeder Zyklus im Graphen von Petersen. Jeder Zehn-Scheitelpunkte-Hamiltonian 3-regelmäßiger Graph besteht aus einem Zehn-Scheitelpunkte-Zyklus C plus fünf Akkorde. Wenn ein Akkord zwei Scheitelpunkte in der Entfernung zwei oder drei entlang C von einander verbindet, hat der Graph einen 3-Zyklen- oder 4-Zyklen-, und kann nicht deshalb der Graph von Petersen sein. Wenn zwei Akkorde entgegengesetzte Scheitelpunkte von C zu Scheitelpunkten in der Entfernung vier entlang C verbinden, gibt es wieder einen 4-Zyklen-. Der einzige restliche Fall ist eine gebildete Leiter von Möbius durch das Anschließen jedes Paares von entgegengesetzten Scheitelpunkten durch einen Akkord, der wieder einen 4-Zyklen-hat. Da der Graph von Petersen Umfang fünf hat, kann es nicht auf diese Weise gebildet werden und hat keinen Zyklus von Hamiltonian.

Das Färben

Der Graph von Petersen hat chromatische Nummer 3, bedeutend, dass seine Scheitelpunkte mit drei Farben — aber nicht mit zwei — solch gefärbt werden können, dass kein Rand Scheitelpunkte derselben Farbe verbindet.

Der Graph von Petersen hat chromatischen Index 4; das Färben der Ränder verlangt vier Farben. Ein Beweis davon verlangt, dass Überprüfung von vier Fällen demonstriert, dass kein 3 Rand-Färben besteht. Als ein verbundener bridgeless Kubikgraph mit dem chromatischen Index vier ist der Graph von Petersen ein snark. Es ist der kleinstmögliche snark, und war der einzige bekannte snark von 1898 bis 1946. Der snark Lehrsatz, ein Ergebnis, das von W. T. Tutte vermutet ist, und hat 2001 durch Robertson, Sanders bekannt gegeben, Seymour und Thomas, stellen fest, dass jeder snark den Graphen von Petersen als ein Minderjähriger hat.

Zusätzlich hat der Graph unbedeutenden chromatischen Index 3, beweisend, dass der Unterschied zwischen dem chromatischen Index und chromatischen Bruchindex so groß sein kann wie 1. Der langjährige Goldberg-Seymour Conjecture schlägt vor, dass das die größte mögliche Lücke ist.

Die Thue Zahl (eine Variante des chromatischen Index) des Graphen von Petersen ist 5.

Andere Eigenschaften

Der Graph von Petersen:

ist

• 3-verbunden und folglich 3 Rand verbunden und bridgeless. Sieh das Wörterverzeichnis.
• hat Unabhängigkeit Nummer 4 und ist 3-partite. Sieh das Wörterverzeichnis.

ist

• kubisch, hat Überlegenheit Nummer 3, und hat ein vollkommenes Zusammenbringen und einen 2-Faktoren-.
• ist der kleinste Kubikgraph des Umfangs 5. (Es ist das einzigartige - Käfig. Tatsächlich, da es nur 10 Scheitelpunkte hat, ist es der einzigartige - Graph von Moore.)
• hat Radius 2 und Diameter 2. Es ist der größte Kubikgraph mit dem Diameter 2.
• hat Graph-Spektrum −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• hat 2000 Überspannen-Bäume, den grössten Teil jedes 10-Scheitelpunkte-Kubikgraphen.
• hat chromatisches Polynom
• hat charakteristisches Polynom, es einen integrierten Graphen — ein Graph machend, dessen Spektrum völlig aus ganzen Zahlen besteht.

Petersen, der Vermutung färbt

Gemäß DeVos, Nesetril und Raspaul, "Ist ein Zyklus eines Graphen G ein Satz C E (G), so dass jeder Scheitelpunkt des Graphen (V (G), C) hat sogar Grad. Wenn G, H Graphen sind, definieren wir eine Karte φ: E (G) —> E (H), um Zyklus-continous zu sein, wenn das Vorimage jedes Zyklus von H ein Zyklus von G ist. Ein faszinierender onjecture der Raubmöwe behauptet, dass jeder bridgeless Graph einen zum Graphen von Petersen kartografisch darstellenden Zyklus-continous hat. Raubmöwe hat dass gezeigt, wenn diese Vermutung wahr ist, dann so ist der 5 Zyklus doppelte Deckel-Vermutung und die Vermutung von Berge-Fulkerson."

Zusammenhängende Graphen

Der verallgemeinerte Graph von Petersen G (n, k) wird durch das Anschließen der Scheitelpunkte eines regelmäßigen n-gon zu den entsprechenden Scheitelpunkten eines Sternvielecks mit dem Symbol von Schläfli {n/k} gebildet. Zum Beispiel, in dieser Notation, ist der Graph von Petersen G (5,2): Es kann durch das Anschließen entsprechender Scheitelpunkte eines Pentagons und Fünf-Punkte-Sterns gebildet werden, und die Ränder im Stern verbinden jeden zweiten Scheitelpunkt.

Die verallgemeinerten Graphen von Petersen schließen auch das N-Prisma G (n, 1) ein

der Graph von Dürer G (6,2), der Möbius-Kantor Graph

G (8,3), das Dodekaeder G (10,2), der Graph von Desargues G (10,3) und der Graph von Nauru G (12,5).

Die Familie von Petersen besteht aus den sieben Graphen, die vom Graphen von Petersen durch die Null oder mehr Anwendungen von Δ-Y gebildet werden können oder sich Y-Δ verwandelt. Der ganze Graph K ist auch in der Familie von Petersen. Diese Graphen bilden die verbotenen Minderjährigen für linklessly embeddable Graphen, Graphen, die in den dreidimensionalen Raum auf solche Art und Weise eingebettet werden können, dass keine zwei Zyklen im Graphen verbunden werden.

Der Clebsch Graph enthält viele Kopien des Graphen von Petersen als veranlasste Subgraphen: Für jeden Scheitelpunkt v des Graphen von Clebsch veranlassen die zehn Nichtnachbarn von v eine Kopie des Graphen von Petersen.

Zeichen

• .

. . ..

Links

• Keller, Mitch.
• Graph von Petersen in der Online-Enzyklopädie von Folgen der ganzen Zahl