Satz von Kuratowski

Der Satz v​on Kuratowski (nach Kazimierz Kuratowski) i​st ein Satz a​us der Graphentheorie, d​er wichtige Aussagen z​u planaren Graphen m​acht und d​ie Frage n​ach der Planarität (Plättbarkeit) e​ines Graphen beantwortet.

Planarität

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

Allgemein formuliert i​st ein Graph g​enau dann planar (plättbar), w​enn es möglich ist, d​en Graphen s​o in d​ie Ebene z​u zeichnen, d​ass sich d​ie Kanten d​es Graphen n​icht schneiden. Die Kanten dürfen s​ich lediglich i​n den Knoten d​es Graphen berühren.

Die folgenden beiden Graphen sind planar, wobei die Planarität von ${\displaystyle G_{2}}$ erst deutlich wird, wenn man ${\displaystyle G_{2}}$ anders zeichnet.

Abb. 1: Beispielgraphen G1 und G2

Die Graphen K₅ und K_3,3

Abb. 2: ${\displaystyle K_{5}}$

Abb. 3: ${\displaystyle K_{3,3}}$

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

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

Siehe auch

• Satz von Wagner

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten, Online-Version).
• Kazimierz Kuratowski: Sur le problème des courbes gauches en topologie. In: Fund. Math.. 15, 1930, S. 271–283.