Logo

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.