Satz von Kuratowski - LinkFang.de





Satz von Kuratowski


Der Satz von Kuratowski (nach Kazimierz Kuratowski) ist ein Satz aus der Graphentheorie, der wichtige Aussagen zu planaren Graphen macht und die Frage nach der Planarität (Plättbarkeit) eines Graphen beantwortet.

Planarität

Allgemein formuliert ist ein Graph genau dann planar (plättbar), wenn es möglich ist, den Graphen so in die Ebene zu zeichnen, dass sich die Kanten des Graphen nicht schneiden. Die Kanten dürfen sich lediglich in den Knoten des Graphen berühren.

Die folgenden beiden Graphen sind planar, wobei die Planarität von [math] G_2[/math] erst deutlich wird, wenn man [math] G_2[/math] anders zeichnet.

Die Graphen K5 und K3,3

Der Satz von Kuratowski benutzt zwei spezielle Graphen: [math] K_5[/math] und [math] K_{3,3}[/math]. Bei [math] K_5[/math] handelt es sich um den vollständigen Graphen mit 5 Knoten (siehe Abb. 2), bei [math] K_{3,3}[/math] um einen vollständig bipartiten Graphen, der in zwei je dreielementige Teilmengen aufgeteilt ist (siehe Abb. 3). Beide Graphen sind nicht planar. Sie sind sogar die kleinsten nicht-planaren Graphen überhaupt, was direkt aus dem Satz von Kuratowski folgt.

Der Satz von Kuratowski

Der Satz von Kuratowski besagt, dass ein Graph genau dann planar ist, wenn er keinen Teilgraphen besitzt, der ein Unterteilungsgraph des [math]K_5[/math] oder des [math]K_{3,3}[/math] ist. Einen Unterteilungsgraph erhält man, indem man wiederholt eine Kante durch ein inzidentes Kantenpaar ersetzt. Alternativ kann man formulieren, dass ein Graph genau dann planar ist, wenn er weder den [math]K_5[/math] noch den [math]K_{3,3}[/math] als topologischen Minor enthält.

Literatur


Kategorien: Topologische Graphentheorie | Satz (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Satz von Kuratowski (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.