drunter und drüber

31/05/2008 - 23:54 von Uwe Bosse | Report spam
Hallo,
Vor Jahrzehnten hab ich in der Schule gestaunt über folgendes Phànomen beim
Zeichnen geschlossener Kurven:

Wenn man eine oder mehrere geschlossene Kurven so in der Ebene zeichnet,
dass sich an keinem Punkt mehr als zwei Linien kreuzen, so kann man die
Kreuzungen durch "Brücken" ersetzen. Eine Linie führt über die Brücke, die
andere darunter. Bei einer Acht würde man also in der Mitte eine Brücke
haben, und führe man nun die Acht entlang, so kàme man abwechselnd über die
Brücke und unter ihr hindurch.
Erstaunlicherweise ist es stets (bei endlich vielen geschlossenen Kurven mit
endlich vielen Kreuzungen) möglich, die Brücken so einzurichten, dass, egal
welche geschlossene Kurve man entlangfàhrt, man stets abwechselnd über eine
Brücke und dann wieder unter einer hindurch fàhrt.

Findet jemand einen hübschen Beweis dafür? Ganz so trivial kann der nicht
sein, da der Sachverhalt nicht mehr richtig ist, wenn man die Kurven auf
einer Torusoberflàche zeichnet.

Viel Spaß beim Brücken bauen!
 

Lesen sie die antworten

#1 Jan Fricke
01/06/2008 - 02:26 | Warnen spam
Uwe Bosse wrote:
Hallo,
Vor Jahrzehnten hab ich in der Schule gestaunt über folgendes Phànomen beim
Zeichnen geschlossener Kurven:

Wenn man eine oder mehrere geschlossene Kurven so in der Ebene zeichnet,
dass sich an keinem Punkt mehr als zwei Linien kreuzen, so kann man die
Kreuzungen durch "Brücken" ersetzen. Eine Linie führt über die Brücke, die
andere darunter. Bei einer Acht würde man also in der Mitte eine Brücke
haben, und führe man nun die Acht entlang, so kàme man abwechselnd über die
Brücke und unter ihr hindurch.
Erstaunlicherweise ist es stets (bei endlich vielen geschlossenen Kurven mit
endlich vielen Kreuzungen) möglich, die Brücken so einzurichten, dass, egal
welche geschlossene Kurve man entlangfàhrt, man stets abwechselnd über eine
Brücke und dann wieder unter einer hindurch fàhrt.

Findet jemand einen hübschen Beweis dafür? Ganz so trivial kann der nicht
sein, da der Sachverhalt nicht mehr richtig ist, wenn man die Kurven auf
einer Torusoberflàche zeichnet.



Wenn man in der angegebenen Form Kurven in der Ebene zeichnet, so erhàlt
man eine Landkarte, die mit zwei Farben regulàr fàrbbar ist (Beweis der
Vollstàndigkeit halber: siehe unten). Somit wechseln sich an jeder
Kreuzung die beiden Farben links und recht der Kurve ab, d.h. man nimmt
immer eine Brücke, wenn Farbe X von links auf rechts, und einen Tunnel,
wenn Farbe X von rechts auf links wechselt.

Lemma: Eine (ebene) Landkarte ist genau dann 2-fàrbbar, wenn in jedem
Knoten eine gerade Anzahl von Kanten ankommt.
Beweis:
"==>" ist offensichtlich.
"<==": Induktion über die Anzahl der Gebiete.
Induktionsanfang: Falls die Karte ein Gebiet hat¹, dann ist die Aussage
offensichtlich wahr.
Induktionsschritt: Wenn es mehrere Gebiete gibt, dann entferne ich eines
mit seinen Grenzen und bekomme wieder so eine Landkarte mit weniger
Gebieten. (Alle an das entfernte Gebiet angrenzenden Gebiete sind dann
zu einem neuen [großen] Gebiet verschmolzen.) Also kann ich diese Karte
2-fàrben. Nun muss nur noch das entfernte Gebiet wieder eingefügt und
umgefàrbt werden, schon ist die Karte regulàr 2-gefàrbt.


Viele Grüße Jan

__________
¹: Das ist die Stelle, die beim Torus schief geht: In der Ebene ist eine
Landkarte mit nur einem Gebiet ein Wald; da kann aber nicht jeder Knoten
gerade Valenz haben, also gibt es dann weder Knoten noch Kanten (also
grenzt das Gebiet auch nicht an sich selbst). Auf dem Torus (und allen
anderen Flàchen von höherem Geschlecht) gibt es sehr wohl eine Landkarte
mit nur einem Gebiet, das an sich selbst grenzt.

Ähnliche fragen