« vorheriger Beitrag  · nächster Beitrag »

06.05.11 · 20:47 Uhr

Topologie von Flächen CLXVI

Kategorie: Naturwissenschaften  ·  Kommentare: 3

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.

Man könnte sich dann fragen, welche metrischen Räume diese Bedingungen überhaupt erfüllen, neben der Sphäre bzw. der Ebene, für die diese Bedingungen ja nach dem Jordanschen Kurvensatz gelten. Zum Beispiel ist es ziemlich offensichtlich, daß diese Bedingungen für Räume der Dimension ≥ 3 nicht gelten: in einen 3-dimensionalen Raum kann man jeden Graph einbetten; und es ist auch anschaulich klar, daß eine Kurve diesen Raum nicht zerlegt.
Auch für Flächen mit Geschlecht ≥ 1 (Torus, Brezel, ...) kann man sich leicht überlegen, daß es nicht-zerlegende geschlossene Kurven gibt
und auch, daß es Einbettungen von K_3,3 und K₅ in diese Flächen gibt.
Thomassen hat dann 1992 bewiesen, daß (jedenfalls für kompakte Räume) diese Bedingungen tatsächlich nur für die 2-dimensionale Sphäre erfüllt sind:

Sei X ein kompakter 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) K₅ und K_3,3 können nicht in X eingebettet werden
(iii) X ist eine 2-dimensionale Sphäre.

Thomassen, C. (1992). A characterization of the $2$-sphere in terms of Jordan curve separation Proceedings of the American Mathematical Society, 115 (3), 863-863 DOI: 10.1090/S0002-9939-1992-1124153-0

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101, Teil 102, Teil 103, Teil 104, Teil 105, Teil 106, Teil 107, Teil 108, Teil 109, Teil 110, Teil 111, Teil 112, Teil 113, Teil 114, Teil 115, Teil 116, Teil 117, Teil 118, Teil 119, Teil 120, Teil 121, Teil 122, Teil 123, Teil 124, Teil 125, Teil 126, Teil 127, Teil 128, Teil 129, Teil 130, Teil 131, Teil 132, Teil 133, Teil 134, Teil 135, Teil 136, Teil 137, Teil 138, Teil 139, Teil 140, Teil 141, Teil 142, Teil 143, Teil 144, Teil 145, Teil 146, Teil 147, Teil 148, Teil 149, Teil 150, Teil 151, Teil 152, Teil 153, Teil 154, Teil 155, Teil 156, Teil 157, Teil 158, Teil 159, Teil 160, Teil 161, Teil 162, Teil 163, Teil 164, Teil 165

 

Autor: Thilo· 3 Kommentare· Permalink· Trackback-URL

Tags: bipartit· Ebene· Einbettung· Graph· Jordan· Kuratowski· Kurvensatz· planar· Sphäre· Thomassen· vollständig