Planarer Graph Prüfer

Planarer Graph Prüfer

Der Planarer Graph Prüfer entscheidet, ob ein einfacher ungerichteter Graph planar ist — also in der Ebene gezeichnet werden kann, ohne dass sich zwei Kanten schneiden. Wenn der Graph den Test nicht besteht, findet und visualisiert das Tool den Kuratowski-Beweis: eine Unterteilung von entweder K₅ (dem vollständigen Graphen mit 5 Knoten) oder K₃,₃ (dem vollständigen bipartiten Graphen mit 3 + 3 Knoten). Das Tool ist für die Lehre, die Vorbereitung auf Wettbewerbsprogrammierung und die schnelle Überprüfung kleiner Graphenkonstruktionen konzipiert.

Was bedeutet „planar“?

Ein Graph G = (V, E) ist planar, wenn er so in die Ebene eingebettet werden kann, dass sich Kanten nur an ihren gemeinsamen Endpunkten treffen — es gibt keine Kreuzungen. Äquivalent dazu kann G kreuzungsfrei auf der Oberfläche einer Kugel gezeichnet werden. Planarität ist eine rein topologische Eigenschaft: Sie hängt nicht davon ab, wie man den Graphen zeichnet, sondern nur davon, ob irgendeine kreuzungsfreie Zeichnung existiert.

Planare Graphen kommen überall vor — Straßen- und Versorgungsnetze, Leiterplatten-Routing (PCB), die Kantengraphen platonischer Körper und die Flächenstruktur von Polyedern. Dennoch sind viele „natürliche“ Graphen hartnäckig nicht planar: Jedes Mal, wenn man versucht, 3 Häuser mit 3 Versorgungsleitungen ohne Kreuzungen zu verbinden, stößt man auf die K₃,₃-Barriere.

Satz von Kuratowski — Das Herzstück des Prüfers

Kazimierz Kuratowski bewies 1930, dass Planarität eine rein kombinatorische Charakterisierung hat:

Eine Unterteilung eines Graphen H entsteht, indem man einige Kanten von H durch längere Pfade ersetzt, deren interne Knoten alle neu sind und den Grad 2 haben. Der Satz von Kuratowski besagt daher, dass K₅ und K₃,₃ die einzigen Hindernisse für die Planarität sind — jeder nicht planare Graph enthält einen von ihnen in einer „gestreckten“ Form.

Die verbotenen Graphen

Eulersche Formel und schnelle notwendige Bedingungen

Bevor die (relativ aufwendige) Unterteilungssuche gestartet wird, wendet der Prüfer zwei schnelle notwendige Bedingungen an, die aus der Eulerschen Formel abgeleitet sind: Für jeden zusammenhängenden planaren Graphen, der mit V Knoten, E Kanten und F Flächen (einschließlich der unbeschränkten Außenfläche) in der Ebene gezeichnet wird, gilt:

Zusammen mit der Beobachtung, dass jede Fläche eines einfachen planaren Graphen mindestens 3 Kanten an ihrem Rand hat, erhalten wir die obere Kantenschranke:

Jeder Graph, der diese Ungleichungen verletzt, ist sofort nicht planar, ohne dass eine Unterteilungssuche erforderlich ist. K₅ hat m = 10, n = 5 ⇒ 3n − 6 = 9, also 10 > 9 — verletzt die Schranke. K₃,₃ hat m = 9, n = 6 ⇒ 2n − 4 = 8, also 9 > 8 — verletzt die bipartite Schranke.

Wie die Unterteilungssuche funktioniert

Nach den einfachen Euler-Prüfungen sucht das Tool direkt nach einer Unterteilung:

1. Quick Win — Erkennung von K₅ oder K₃,₃ als direkten Teilgraphen. Wenn 5 Knoten paarweise benachbart sind, ist das sofort K₅. Wenn 6 Knoten in 3 + 3 aufgeteilt sind und alle 9 Kreuzkanten vorhanden sind, ist das K₃,₃.
2. K₅-Unterteilungssuche. Für jede Kandidatengruppe von 5 „Verzweigungsknoten“ (jeder mit Grad ≥ 4 in G) wird versucht, 10 Pfade zu finden — einen pro Paar —, die intern knotendisjunkt sind (kein Nicht-Verzweigungsknoten erscheint in mehr als einem Pfad) und keine anderen Verzweigungsknoten als interne Knoten verwenden. Ein Treffer beweist die Nicht-Planarität.
3. K₃,₃-Unterteilungssuche. Wahl von 6 Verzweigungsknoten (jeder mit Grad ≥ 3) und einer 3 + 3 Bipartition. Suche nach 9 Pfaden für die Kreuzpaare mit derselben Anforderung an die Disjunktheit.
4. Kein Beweis ⇒ planar. Wenn innerhalb der Größengrenzen keine Unterteilung gefunden wird, garantiert der Satz von Kuratowski, dass der Graph planar ist.

Das Finden knotendisjunkter Pfade ist im Allgemeinen NP-schwer, daher verwendet der Prüfer eine begrenzte randomisierte Greedy-Suche: Jede Iteration ordnet die erforderlichen Paare nach Schwierigkeit, wählt zuerst einen Pfad für das schwierigste Paar mittels randomisierter BFS, entfernt diese internen Knoten und fährt fort. Wenn diese spezifische Reihenfolge scheitert, wird sie mit einer gemischten Reihenfolge wiederholt — bis zu 40 Versuche pro Verzweigungskonfiguration. Bei allen getesteten kleinen Graphen (bis zu 16 Knoten) reicht dies aus, um einen Beweis zu finden, sofern einer existiert.

So verwenden Sie diesen Rechner

1. Eingabeformat wählen über die Tabs oben: Kantenliste oder Adjazenzliste. Beide kodieren denselben Graphen.
2. Graphen eingeben. Der Graph wird als ungerichtet behandelt, daher sind A-B und B-A dieselbe Kante.
3. Auf Planarität prüfen klicken. Das Tool liefert ein Ergebnis, zeigt die schrittweise Begründung (Euler, bipartit, Kuratowski) und rendert den Graphen.
4. Bei einem nicht planaren Graphen markiert die Visualisierung die K₅- oder K₃,₃-Unterteilung farbig und listet die 10 (oder 9) knotendisjunkten Pfade auf. Klicken Sie auf eine Pfad-Zeile, um ihn zu isolieren.
5. Bei einem planaren Graphen wird die Flächenanzahl F = m − n + 1 + c zusammen mit der Graphenstruktur gemeldet.

Anwendungsbeispiel 1 — K₄ ist planar

K₄ hat n = 4, m = 6. Jeder Graph mit ≤ 4 Knoten ist planar, und tatsächlich lässt sich K₄ als Dreieck einbetten, in dessen Mitte ein Knoten mit allen drei Ecken verbunden ist. Euler sagt: F = 6 − 4 + 2 = 4 Flächen: drei dreieckige Innenflächen plus die Außenfläche.

Anwendungsbeispiel 2 — K₃,₃ ist nicht planar

K₃,₃ hat n = 6, m = 9. Er ist bipartit, daher gilt die bipartite Schranke: m = 9 > 2n − 4 = 8. Dies allein beweist die Nicht-Planarität. Der Beweis ist trivial — K₃,₃ ist selbst der verbotene Teilgraph. Das Tool hebt die 3 + 3 Partition und die 9 direkten Kanten hervor.

Anwendungsbeispiel 3 — Der Petersen-Graph

Der Petersen-Graph hat n = 10, m = 15, also gilt m ≤ 3n − 6 = 24 und die schnellen Euler-Prüfungen werden bestanden. Dennoch ist er bekanntermaßen nicht planar. Der Prüfer findet eine K₃,₃-Unterteilung: Er wählt sechs Knoten aus dem äußeren Fünfeck und dem inneren Pentagramm aus, sodass jedes Kreuzpaar über die verbleibenden vier Knoten durch knotendisjunkte Pfade verbunden werden kann. Das Tool zeichnet den Beweis und macht die Geometrie der 1930er Jahre greifbar.

Anwendungen der Planarität

• VLSI- und PCB-Routing. Eine einlagige Schaltung ist nur machbar, wenn der Verbindungsgraph planar ist; nicht planare Netze erzwingen Durchkontaktierungen (Vias) oder zusätzliche Lagen.
• Graphenzeichnung und Visualisierung. Planare Graphen ermöglichen klare, kreuzungsfreie Layouts — nützlich für Netzpläne, Aufrufgraphen (Call Graphs) und schematische Diagramme.
• Algorithmen-Design. Viele NP-schwere Probleme (Maximum Cut, Vertex Cover, Graphenisomorphie) werden in Polynomialzeit lösbar, wenn sie auf planare Graphen beschränkt sind.
• Graphenfärbung. Der Vier-Farben-Satz garantiert, dass jeder planare Graph mit 4 Farben färbbar ist — ein klassisches Ergebnis, dessen Aussage von der Planarität abhängt.
• Kombinatorische Optimierung. Planare kürzeste Pfade, Max-Flow und Min-Cut erlauben spezialisierte schnelle Algorithmen.
• Molekulare Chemie. Die Graphen von aromatischen Benzolring-Kohlenwasserstoffen sind planar; bestimmte Käfigmoleküle sind es nicht.

Häufig gestellte Fragen

Was bedeutet planar für einen Graphen?

Ein Graph ist planar, wenn man ihn so in der Ebene zeichnen kann, dass sich keine zwei Kanten schneiden, außer in gemeinsamen Knoten. Äquivalent dazu ist ein Graph planar, wenn er kreuzungsfrei auf der Oberfläche einer Kugel gezeichnet werden kann. Bäume, Zyklen, der Würfelgraph und die platonischen Körper sind alle planar, während K₅ und K₃,₃ die kanonischen nicht-planaren Beispiele sind.

Was ist der Satz von Kuratowski?

Der Satz von Kuratowski besagt, dass ein endlicher Graph genau dann planar ist, wenn er keinen Teilgraphen enthält, der eine Unterteilung von K₅ oder K₃,₃ ist. Eine Unterteilung entsteht durch das Ersetzen einiger Kanten durch längere Pfade über neue Knoten vom Grad 2. Dies liefert ein konkretes kombinatorisches Zertifikat für die Nicht-Planarität.

Was ist der Unterschied zwischen K₅ und K₃,₃?

K₅ hat 5 Knoten, wobei jedes Paar durch eine Kante verbunden ist (insgesamt 10 Kanten). K₃,₃ hat 6 Knoten, die in zwei Gruppen zu je 3 unterteilt sind, wobei jeder Knoten der einen Gruppe mit jedem der anderen Gruppe verbunden ist (insgesamt 9 Kanten). Beide sind die kleinsten nicht-planaren Graphen ihrer Art und bilden zusammen die verbotenen Minoren für die Planarität.

Wie hilft die Eulersche Ungleichung?

Die Eulersche Formel V − E + F = 2 für planare zusammenhängende Graphen ergibt zusammen mit der Tatsache, dass jede Fläche eines einfachen planaren Graphen mindestens 3 Kanten hat, die Schranke m ≤ 3n − 6. Jeder einfache Graph, der diese Schranke verletzt, ist sofort nicht planar. Für bipartite planare Graphen hat jede Fläche mindestens 4 Kanten, was die engere Schranke m ≤ 2n − 4 ergibt. Der Prüfer wendet beide als schnelle Ausschlussregeln an.

Was ist die Größenbeschränkung?

Der Prüfer verarbeitet bis zu 16 Knoten und 60 Kanten. Dies deckt typische Graphen aus der Lehre und Wettbewerben ab, wie den Petersen-Graphen, den Möbius-Kantor-Graphen, kleine Hyperwürfel und den vollständigen Graphen K₇. Größere Graphen erfordern spezialisierte Planaritätstests in Linearzeit wie Hopcroft-Tarjan.

Wie wird die Beweis-Unterteilung gezeichnet?

Wenn der Graph nicht planar ist, werden die 5 Verzweigungsknoten des gefundenen K₅ — oder die 6 Verzweigungsknoten von K₃,₃, aufgeteilt in zwei Tripel A und B — auf einem inneren Ring hervorgehoben. Die 10 (bzw. 9) erforderlichen intern knotendisjunkten Pfade werden jeweils in einer eigenen Farbe gezeichnet, damit man die K₅- oder K₃,₃-Topologie visuell verfolgen kann. Knoten und Kanten, die nicht zur Unterteilung gehören, werden ausgegraut.

Weiterführende Literatur

• Planarer Graph — Wikipedia
• Satz von Kuratowski — Wikipedia
• Eulerscher Polyedersatz — Wikipedia
• Petersen-Graph — Wikipedia
• Wagners Satz (Minor-Version) — Wikipedia (Englisch)