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 K3,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 I1 und ein Äußeres A1 zerlegt. Dies gälte insbesondere für die geschlossene Kurve durch die vier unteren Eckpunkte des K3,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 I2 und Äußerem A2, wobei I2 eine Teilmenge von I1 ist. Der Durchschnitt von A2 und I1 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 I3 und ein Äußeres A3 hat und die andere verbliebene Kante müßte dann I3 und A3 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 K5 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 K5 und K3,3 nicht in die Ebene einbetten kann, kann man dann natürlich auch keinen Graphen in die Ebene einbetten, der K5 oder K3,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 K5 oder K3,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 K3,3 benutzte man den Jordanschen Kurvensatz. Wenn man sich jetzt für die Frage interessiert, ob der K3,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 K3,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 K3,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 K3,3 kann nicht in X eingebettet werden
(iii) K5 und K3,3 können nicht in X eingebettet werden.
Kommentare (3)