Mathematisches Seminar über Graphen

Andreas M. Hinz

Mathematisches Institut der Universität München

Sommersemester 2010

Inhalt

Das mathematische Spiel Der Turm von Hanoi wurde 1883 vom französischen Zahlentheoretiker Edouard Lucas erfunden. Mittlerweile ist es zu einem Paradigma in der diskreten Mathematik, der Informatik und der Neuropsychologie geworden. Die hier als Test-Tool verwendeten Varianten lassen sich als Graphen modellieren, den Turm-Graphen. Trotz seines augenscheinlich elementaren Charakters gibt es eine Reihe von ungelösten mathematischen Problemen im Zusammenhang mit diesem Objekt. Ziel des Seminars ist es, zu diesen Fragen vorzudringen und einige Lösungsstrategien zu entwickeln. Dabei geht es um historische, graphentheoretische und algorithmische Themen.

Themen und Termine

1. Das Schubfachprinzip (M 03.05. Hinz, M 05.07. Strobl, 23.04. Scherer)
2. Die Chinesischen Ringe und der Gray-Code (M 26.04. Holz auf der Heide, F 30.04. Bredenpohl)
3. Der Turm von Hanoi (M 10.05. Karl, F (M 10.05., 16:15, B045) Keller)
4. Oxford-, London-, Hanoi- und Sierpinski-Graphen (M 31.05. Dorn, F 21.05. Böcker)
5. Planarität (M 07.06. Höck, F 28.05. Mundigl)
6. Überschneidungszahl und Geschlecht (M 14.06. Morawietz, F 04.06. Köhler)
7. Perfekte Codes (M 21.06. Rothe, F 11.06. Schäfer)
8. Färbungen (M 19.04. Hölzle, F (M 14.06., 08:30, B252) Pikovska)
9. Färbungen von Hanoi-Graphen (M 28.06. Pfeiffer, F (M 21.06., 16:15, B045) Bauer)
10. Der Dijkstra-Algorithmus (M 05.07. David, F 02.07. Herold)
11. Metrische Eigenschaften der Hanoi-Graphen (M 12.07. Götz/Sieß, F (M 12.07., 16:15, B045) Sommerschuh)
12. Bewegungen der größten Scheibe (M 19.07. Zehentner, F 23.07. Bader)

Außerordentliche Sitzungen am Dienstag, dem 20. Juli 2010, um 17:15 Uhr im Raum B005 und am Donnerstag, dem 22. Juli 2010, um 14:15 Uhr im Raum B251: P. Alonso Ruiz, Spektralanalysis von \Delta_SG mittels Hanoi- und Sierpinski-Gasket-Graphen.

Vorkenntnisse

Vorexamen oder Vordiplom; Kenntnisse in Diskreter Mathematik (dort finden Sie auch das Vorlesungsskript), insbesondere Graphentheorie (mit Vorlesungsskript), sind hilfreich.

Vorbesprechung

Eine Vorbesprechung fand statt am Freitag, dem 12.02.2010, um 16:00 Uhr im Raum B133.

Die Scheine können ab sofort in der Prüfungskanzlei abgeholt werden.

Kontakt

Fragen können Sie richten an
A. M. Hinz, Tel. 21804122, e-mail hinz@math.lmu.de

A. M. Hinz, hinz@math.lmu.de, 2010-07-26