Topologie von Flächen CLXVI

Die drei kleinen Schweinchen und nochmal zum Jordanschen Kurvensatz.

In einem alten Kinderspiel sollen die Häuser der drei kleinen Schweinchen H1, H2 und H3 jeweils mit einem Wasserwerk W, einem Elektrizitätswerk E und einem Heizkraftwerk H durch Leitungen so verbunden werden, dass die Leitungen sich nicht überkreuzen:

Quelle: LEDA-Tutorium

Die Aufgabe ist nicht lösbar: man wird es nicht schaffen, die Leitungen kreuzungsfrei einzuzeichnen.

Mathematisch formuliert man die Frage so:
Gibt es eine Einbettung des vollständig bipartiten Graphen K_3,3 (Bild unten) in die Ebene?
(Einbettung heißt, daß keine zwei Punkte des Graphen auf denselben Punkt in der Ebene abgebildet werden.)

Es ist nach ein wenig Probieren ziemlich klar, daß es keine Einbettung dieses Graphen in die Ebene gibt. Wenn man das mathematisch formal beweisen will, braucht man aber den Jordanschen Kurvensatz, über den wir vor 2 Wochen geschrieben hatten. Der Jordansche Kurvensatz besagt, daß jede geschlossene Kurve die Ebene in ein Inneres I₁ und ein Äußeres A₁ zerlegt. Dies gälte insbesondere für die geschlossene Kurve durch die vier unteren Eckpunkte des K_3,3, wenn man diesen in die Ebene eingebettet hätte. Die beiden oberen Eckpunkte müßten dann beide im Inneren oder beide im Äußeren liegen, andernfalls ginge ihre Verbindungskante ja durch die geschlossene Kurve. Sagen wir o.B.d.A. beide liegen im Inneren. Zusammen mit den beiden mittleren Eckpunkten bilden sie wieder eine geschlossene Kurve mit Innerem I₂ und Äußerem A₂, wobei I₂ eine Teilmenge von I₁ ist. Der Durchschnitt von A₂ und I₁ ist ein 5-Eck 6-Eck, innerhalb dessen die beiden verbliebenen Kanten liegen müßten. Eine dieser Kanten bildet mit zweien dreien der 5-Ecks6-Ecks-Kanten eine geschlossene Kurve, die wieder ein Inneres I₃ und ein Äußeres A₃ hat und die andere verbliebene Kante müßte dann I₃ und A₃ verbinden, was nicht möglich ist.

Mit einer ähnlichen Anwendung des Jordanschen Kurvensatzes kann man beweisen, daß sich auch der oben abgebildete vollständige Graph K₅ nicht in die Ebene einbetten läßt.
(Ein einfacherer Beweis wäre über die Eulersche Polyederformel E-K+F=2, die in beiden Fällen leicht zu einem Widerspruch führt. Allerdings benutzen die Beweise der Eulerschen Polyederformel bereits den Jordanschen Kurvensatz.)

Da man K₅ und K_3,3 nicht in die Ebene einbetten kann, kann man dann natürlich auch keinen Graphen in die Ebene einbetten, der K₅ oder K_3,3 als Teilgraphen enthält, oder der eine ihrer Unterteilungen enthält.
(Unterteilung heißt, daß man auf den Kanten der Graphen eventuell noch zusätzliche ‘überflüssige’ Ecken einfügt, diese unterteilten Graphen sehen topologisch genauso aus und sind dann natürlich auch nicht einbettbar.)

Interessanterweise sind das die einzigen Bedingungen für bzw. gegen die Einbettbarkeit eines Graphen in die Ebene. Ein Graph läßt sich genau dann in die Ebene einbetten (ist planar), wenn er keine Unterteilung von K₅ oder K_3,3 als Teilgraphen enthält. Das ist der Satz von Kuratowski:

matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf

Beim Beweis der Nichteinbettbarkeit von K_3,3 benutzte man den Jordanschen Kurvensatz. Wenn man sich jetzt für die Frage interessiert, ob der K_3,3 in irgendeinen anderen Raum eingebettet werden kann, dann wird man naheliegenderweise erst einmal schauen, ob für diesen Raum ein Analogon zum Jordanschen Kurvensatz gilt, also ob jede Kurve den Raum in zwei Zusammenhangskomponenten zerlegt. Wenn letzteres zutrifft, dann kann man mit demselben Beweis wie oben beweisen, daß sich der K_3,3 nicht einbetten läßt.

Ende der 80er Jahre hat Carsten Thomassen bewiesen, daß diese Bedingung (daß jede Kurve den Raum zerlegt) i.d.R. äquivalent dazu ist, daß sich der K_3,3 nicht einbetten läßt. Genauer hat er folgenden Satz bewiesen:

Sei X ein metrischer Raum (zusammenhängend, kein Kreis und nicht durch Herausnahme eines abgeschlossenen Intervalls zerlegbar), dann sind die folgenden Bedingungen äquivalent:
(i) jede geschlossene Kurve zerlegt X in zwei Zusammenhangskomponenten
(ii) der K_3,3 kann nicht in X eingebettet werden
(iii) K₅ und K_3,3 können nicht in X eingebettet werden.