Satz von Kuratowski

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Animation: der Petersen-Graph enthält  K_{ 3 , 3 }  als Minor und ist deshalb nicht planar.

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  G_2 erst deutlich wird, wenn man  G_2 anders zeichnet.

Abb. 1: Beispielgraphen G1 und G2

Die Graphen  K_5 und  K_{3,3}[Bearbeiten]

Abb. 2:  K_5
Abb. 3:  K_{3,3}

Der Satz von Kuratowski benutzt zwei spezielle Graphen:  K_5 und  K_{3,3}. Bei  K_5 handelt es sich um den vollständigen Graphen mit 5 Knoten (siehe Abb. 2), bei  K_{3,3} 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[Bearbeiten]

Der Satz von Kuratowski besagt, dass ein Graph genau dann planar ist, wenn er keinen Teilgraphen besitzt, der ein Unterteilungsgraph des K_5 oder des K_{3,3} 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 K_5 noch den K_{3,3} als topologischen Minor enthält.

Literatur[Bearbeiten]