Planaritäts-Prüfer — Testen Sie, ob ein Graph ohne Kreuzungen gezeichnet werden kann
Unser Planaritäts-Prüfer testet, ob ein Graph potenziell auf einer Ebene ohne sich kreuzende Kanten gezeichnet werden könnte, indem er die notwendige Kantenzahl-Bedingung anwendet (E ≤ 3V − 6, verschärft auf E ≤ 2V − 4 für bipartite Graphen) und für Graphen mit 8 oder weniger Knoten eine explizite Suche nach einem K₅- oder K₃,₃-Untergraphen — jeder von beiden beweist definitiv Nicht-Planarität nach dem Satz von Kuratowski.
Kurzantwort
Geben Sie Ihren Graphen als Kantenliste ein, um die notwendige Kantenzahl-Bedingung zu prüfen und nach verbotenen K₅/K₃,₃-Untergraphen zu suchen — eine starke, aber nicht vollständig erschöpfende Planaritätsprüfung.
Geben Sie Kanten als KnotenA-KnotenB ein, z. B. A-B, A-C, A-D, B-C, B-D, C-D.
So verwenden Sie Planaritäts-Prüfer — Kuratowski-Ähnlicher Test Online
- 1
Geben Sie Ihren Graphen als kommagetrennte Kantenliste ein, z. B. A-B, A-C, A-D, B-C, B-D, C-D.
- 2
Klicken Sie auf 'Berechnen', um die notwendigen Bedingungen zu prüfen und nach verbotenen Untergraphen zu suchen.
- 3
Sehen Sie sich das Urteil an — 'definitiv nicht-planar' oder 'wahrscheinlich planar (nicht schlüssig)' — sowie die Begründungsschritte.
Warum Planaritäts-Prüfer — Kuratowski-Ähnlicher Test Online verwenden?
Ein Graph ist planar, wenn er auf einer flachen Ebene gezeichnet werden kann, ohne dass sich zwei Kanten kreuzen. Der Satz von Kuratowski gibt eine exakte Charakterisierung: ein Graph ist genau dann nicht-planar, wenn er eine Unterteilung von K₅ (dem vollständigen Graphen mit 5 Knoten) oder K₃,₃ (dem vollständigen bipartiten Graphen mit zwei Gruppen von je 3) enthält. Die vollständige Erkennung von Unterteilungen oder Minoren dieser Graphen erfordert ausgeklügelte Algorithmen (wie Boyer-Myrvold), weit über das hinaus, was ein clientseitiger Rechner sofort ausführen kann — daher verfolgt dieses Werkzeug stattdessen einen transparent begrenzten Ansatz: es prüft immer die notwendige Kantenzahl-Grenze (eine schnelle, exakte Methode, um viele nicht-planare Graphen auszuschließen), und für kleine Graphen (8 oder weniger Knoten) sucht es zusätzlich direkt nach K₅ oder K₃,₃, die als buchstäbliche Untergraphen erscheinen. Das Finden von einem von beiden beweist Nicht-Planarität schlüssig; keinen zu finden ist ein starker Hinweis auf Planarität, aber kein vollständiger Beweis, da es unterteilte (kantenerweiterte) Kopien dieser verbotenen Graphen nicht erkennt.
Häufig gestellte Fragen
Ähnliche Tools
Graph-Gradfolge-Validator — Erdős–Gallai-Theorem Online
Prüfen Sie, ob eine Zahlenfolge eine gültige (graphische) Gradfolge ist, mit dem Erdős–Gallai-Theorem. Kostenloser Rechner mit schrittweiser Überprüfung.
Graphfärbung-Rechner — Welsh-Powell-Algorithmus Online
Färben Sie die Knoten eines Graphen so, dass keine zwei verbundenen Knoten dieselbe Farbe teilen, mit dem gierigen Welsh-Powell-Algorithmus. Kostenloser Rechner mit einfacher Kantenlisteneingabe.
Adjazenzmatrix-Rechner — Erstellen Sie eine Graphmatrix Online
Erstellen und zeigen Sie die Adjazenzmatrix eines Graphen aus einer einfachen Kantenlisteneingabe an, zusammen mit seiner Gradfolge. Kostenloser Rechner, gewichtet oder ungewichtet.