DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000
Eulersche Linien
Wieso kann eine Ameise die Kanten eines
Oktaeders so ablaufen, daß
jede Kante genau einmal durchlaufen wird, während das mit einem
Würfel nicht klappt? Und wo endet die Reise der Ameise auf dem
Oktaeder?
Welche der folgenden Figuren läßt sich ohne abzusetzen in
einem Zug zeichnen?
Gegeben sei ein (ungerichteter)
Graph, gegeben durch Eckenmenge V
und Kantenmenge E.
Eine endliche Folge v1,v2,...,vt
von Ecken heißt Euler'sche Linie,
falls E = {vjvj+1 | 1 j
t-1} = E
ist, und die Kanten vjvj+1 alle verschieden sind.
Die Eulersche Linie ist geschlossen,
falls v1=vt ist, und andernfalls offen.
|
Die Frage, welche Graphen solche Linien erlauben, wurde schon
1736 von Euler vollständig
beantwortet. Ausgelöst wurde
Euler's Untersuchung durch die Frage, ob im damaligen
Königsberg ein Spaziergang möglich sei, bei dem jede Brücke
genau einmal überschritten wird, dem sogenannten
Königsberger Brückenproblem.
Euler 1736:
Ein Graph hat eine (offene/geschlossene) Eulersche Linie, falls
er zusammenhängend ist und die Grade
(aller Ecken/aller Ecken bis auf zwei) gerade sind.
|
Damit läßt sich obiges Rätsel leicht auflösen:
Wir erhalten Graphen aus den Zeichnungen, indem wir an allen
Punkten, an denen mindestens 3 Linien zusammenstoßen, Ecken
einfügen. Ecken mit geradem Grad sind weiß , Ecken ungeraden
Grades schwarz gefärbt.
Es gibt eine sehr gute Seite zum
Königsberger Brückenproblem
von der Universität/Gesamthochschule Wuppertal.
Weiter zu Hamiltonschen Kreisen
Erich Prisner
erstellt im Februar 2000.