Planarer-Graphen-Prüfer
Euler's Formula · Kuratowski-Theorem · K₅/K₃₄₃ Detection · Genus Calculator
Bestimme, ob ein Graph planar ist, mithilfe von V−E+F=2, Kantenschranken und der Suche nach K₅/K₃₄₃-Unterteilungen. Gib eine Kantenliste ein, um zu beginnen.
Schnellbeispiele
Unterstützt Zahlen oder einzelne Buchstaben als Labels. Maximal 12 Knoten für vollständige K₅/K₃₄₃-Unterteilungsprüfungen.
Planaritäts-Urteil
Minimales Geschlecht
Schritt-für-Schritt-Begründung
Grapheneigenschaften
Graph-Visualisierung
Was ist ein planarer Graph?
Ein planarer Graph ist ein Graph, der in die euklidische Ebene eingebettet werden kann – d.h. auf einer flachen Oberfläche so gezeichnet werden kann, dass sich keine zwei Kanten (außer in ihren gemeinsamen Endpunkten) schneiden.
Bekannte Beispiele für planare Graphen sind Bäume, Polygon-Graphen und das Gerüst jedes konvexen Polyeders.
Euler's Formula: V − E + F = 2
Der Eckpfeiler der Planaritätstheorie ist die Eulersche Polyederformel (1752). Für jeden zusammenhängenden planaren Graphen mit V Knoten, E Kanten und F Flächen gilt:
V − E + F = 2
Die Größe χ = V − E + F wird als Euler-Charakteristik bezeichnet. Für zusammenhängende planare Graphen ist χ = 2.
- Für jeden einfachen planaren Graphen mit V ≥ 3: E ≤ 3V − 6
- Für bipartite planare Graphen mit V ≥ 3: E ≤ 2V − 4
Dies sind notwendige, aber nicht hinreichende Bedingungen. Der Petersen-Graph erfüllt E ≤ 3V−6, ist aber nicht planar.
Kuratowski-Theorem
Das Kuratowski-Theorem (1930) liefert die vollständige Charakterisierung: Ein endlicher Graph ist genau dann planar, wenn er keinen Unterteilungsgraphen von K₅ oder K₃₄₃ enthält.
K₅ ist der vollständige Graph mit 5 Knoten. K₃₄₃ ist der vollständig bipartite Graph (3+3 Knoten). Dies sind die einzigen minimalen nicht-planaren Graphen.
Wagner's Theorem (Graph Minors Version)
Eine äquivalente Formulierung ist der Satz von Wagner (1937): Ein Graph ist planar, wenn er weder K₅ noch K₃₄₃ als Minor enthält.
Der Vier-Farben-Satz
Jeder planare Graph ist 4-färbbar: Seine Knoten können mit höchstens 4 Farben gefärbt werden. Das ist der Vier-Farben-Satz.
Graphen-Geschlecht
Für nicht-planare Graphen ist das Geschlecht (Genus) g die minimale Anzahl von Henkeln an einer Sphäre für eine kreuzungsfreie Einbettung. Planare Graphen haben Genus 0.
g ≥ ⌈(E − 3V + 6) / 6⌉
Referenztabelle: Gängige Graphen
| Graph | V | E | Planar? | Grund |
|---|---|---|---|---|
| K₃ (Dreieck) | 3 | 3 | JA | V−E+F=2, F=2 |
| K₄ | 4 | 6 | JA | Tetraedrisch, E=3V−6 |
| K₅ | 5 | 10 | NEIN | E=10 > 3×5−6=9 |
| K₃₄₃ | 6 | 9 | NEIN | Bipartit, E=9 > 2×6−4=8 |
| Würfel Q₃ | 8 | 12 | JA | Bipartit, E=12 ≤ 2×8−4=12 |
| Petersen-Graph | 10 | 15 | NEIN | Enthält K₃₄₃-Unterteilung |
| Oktaeder | 6 | 12 | JA | E=12 = 3×6−6 (strikt) |
| Ikosaeder | 12 | 30 | JA | E=30 = 3×12−6 (strikt) |
Anwendungen von planaren Graphen
- Leiterplattendesign (PCB-Layout): Eine Schaltung ist planar, wenn ihre Komponenten ohne Kabelkreuzungen auf einer Ebene angeordnet werden können.
- VLSI-Chipdesign: Die Minimierung von Kreuzungen nutzt Algorithmen für Planaritätstests.
- Kartenfärbung: Politische Karten sind planare Graphen; der Vier-Farben-Satz garantiert 4-Farben-Lösungen.
- Netzwerklayout: Die Visualisierung planarer Netzwerke (Stromnetze, U-Bahn-Karten) nutzt Planarität.
- Computergrafik: Planare Gitternetz-Triangulierungen liegen 3D-Rendering-Algorithmen zugrunde.
- Molekularchemie: Einige Molekül-Graphen sind planar.