Satz von Kuratowski
Zeichnung: Vollständiger Graph mit 5 Knoten
Abb. 1: K5
Zeichnung: Bipartiter Graph 3 Knoten pro Teilmenge
Abb. 2: K3,3
Der Satz von Kuratowski (nach Kazimierz Kuratowski) macht wichtige Aussagen zu planaren Graphen und beantwortet die Frage nach der Plättbarkeit (Planarität) eines Graphen.
Allgemein formuliert ist ein Graph genau dann planar (plättbar), wenn es möglich ist den Graphen so 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 G2 erst deutlich wird, wenn man G2 anders zeichnet.
bild:Forbys_planar_graphs_example.png
Der Satz von Kuratowski benutzt zwei spezielle Graphen: K5 und K3,3. Bei K5 handelt es sich um den vollständigen Graphen mit 5 Knoten (siehe Abb. 1), bei K3,3 um einen bipartiten Graphen, der in zwei je dreielementige Teilmengen aufgeteilt ist (siehe Abb. 2).
Beide Graphen sind nicht planar. Sie sind sogar die kleinsten nicht-planaren Graphen überhaupt, was direkt aus dem Satz von Kuratowski folgt.
Satz von Kuratowski
- Ein endlicher Graph ist genau dann planar, wenn er keinen Teilgraphen enthält, der durch Erweiterung von K5 oder K3,3 entstanden ist. Erweiterung bedeutet hier das beliebig oft wiederholbare (auch Null mal) Einfügen von neuen Knoten auf Kanten, also zwischen zwei bereits bestehenden Knoten.
Mit Teilgraph ist hier ein Graph gemeint, der aus dem ursprünglichen Graphen durch Entfernen von Knoten bzw. Kanten entsteht, wobei die Entfernung eines Knoten mitsamt aller inzidenten Kanten einen induzierten Teilgraph ergibt.
Äquivalente Formulierungen des Satzes von Kuratowski sind:
- Ein Graph G ist genau dann planar, wenn weder K5 noch K3,3 ein Minor von G ist.
und
- Ein Graph G ist genau dann planar, wenn er keinen zu K5 oder K3,3 homöomorphen Teilgraph enthält.
Eine Verallgemeinerung des Satzes von Kuratowki ist der Satz von Robertson und Seymour.
Kategorie:Graphentheorie
Kuratowski, Satz von