Graphen
Wintersemester 2007/8
Inhalt
In Situationen wo endlich viele Objekte paarweise miteinander verbunden sein
können oder auch nicht, bietet sich als mathematisches Modell ein
Graph an (nicht zu verwechseln mit der gleichnamigen graphischen
Darstellung einer reellwertigen Funktion). Ein Beispiel aus dem täglichen
Leben ist der Münchner U-Bahn-Netzplan: Haltestellen werden durch einen
Punkt dargestellt und sind zwei Stationen durch (mindestens) eine U-Bahn-Linie
benachbart, so verbindet man die zugehörigen Punkte durch einen Strich. So
einfach dieses Konzept ist, so vielfältig und schwierig sind die
zahlreichen mathematischen Fragestellungen, die topologischer (Zusammenhang,
Planarität, Färbbarkeit), metrischer (Abstand) oder algorithmischer
(kürzeste Wege) Natur sein können.
Die Veranstaltung soll eine Einführung in dieses aktuelle Teilgebiet der
Diskreten Mathematik geben. Als Leitmotiv wird dabei das mathematische
Solitärspiel Der Turm von Hanoi dienen, an dessen Beispiel sich alle
Begriffe und viele Resultate anschaulich darstellen lassen. Es bietet auch die
Grundlage für laufende multidisziplinäre Forschungsprojekte in
Zusammenarbeit mit Informatikern und Neuropsychologen.
Zeit und Ort
dienstags, 16-18 Uhr; Übungen 14-täglich mittwochs, 16-18 Uhr
in Hörsaal B040 der Theresienstraße 39.
Beginn der Veranstaltung: 2007-10-16.
Übungstermine sind: 2007-10-30 (18 Uhr, ausnahmsweise), 2007-11-14,
2007-11-28, 2007-12-12, 2008-01-09, 2008-01-16, 2008-01-30;
ein Abschlußtermin (mit Kurzvortrag über das Zeichnen von Graphen
(Q. Stierstorfer) und
Seminarvorbesprechung) ist für 2008-02-06
vorgesehen.
Vorkenntnisse
Grundkenntnisse über die mathematische Denkweise und aus der (naiven)
Mengenlehre.
Literatur
Zur Einstimmung:
1. A. Beutelspacher, M.-A. Zschiegner, Diskrete Mathematik für Einsteiger,
2. Auflage, Vieweg, Wiesbaden, 2004.
2. M. Nitzsche, Graphen für Einsteiger, 2. Auflage, Vieweg, Wiesbaden,
2005.
3. A. P. Barth, Algorithmik für Einsteiger, Vieweg, Wiesbaden, 2003.
4. A. M. Hinz, Der Turm von Hanoi, mathe-lmu.de 4(2001), 20-25.
Eine ausführliche, kommentierte
Literaturliste wurde im Verlaufe der
Vorlesung erstellt.
Übungsblätter und korrigierte Lösungen (Abgabe in der Vorlesung
oder im Übungskasten) liegen von nun an aus feuerpolizeilichen Gründen
(nicht meine Erfindung!) in einem Kasten rechts von den Übungskästen
aus.
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Hier finden Sie Teil
1, hier Teil 2
und hier Teil 3
der Vorlesung.
Es wurde behandelt:
Kapitel 0. Einleitende Beispiele
0. Topologische Fragestellungen
1. Metrische Fragestellungen
1.0. Die Chinesischen Ringe
1.1. Der Turm von Hanoi
2. Formale Definition der Graphen
Kapitel I. Mengen und Zahlen
3. Mengen
3.1. Zerlegungen
3.2. Gleichwertigkeit
4. Zahlen
4.1. Anzahl
4.2. Rekursion
4.3. Metrische Räume
Kapitel II. Spezielle Graphen
5. Weg-, Kreis- und vollständige Graphen
6. Bäume
6.1. Grundlegende Eigenschaften von Bäumen
6.2. Aufspannende Bäume und eine weitere Charakterisierung von Bäumen
6.3. Minimale aufspannende Bäume
6.4. Wurzelbäume und indizierte Bäume
6.4.1. Wurzelbäume
6.4.2. Indizierte Bäume
6.4.3. Anmutige Bäume
7. Bipartite Graphen
8. Turm-Graphen
8.1. Analyse der Lösung zum klassischen TH-Problem
8.2. Rückkehr zu quadratfreien Folgen
8.3. Rückkehr zu Graphen
8.4. Metrische Eigenschaften der Hanoi-Graphen H_3^n
8.4.1. Die Lösung für P1
8.4.2. Diskussion der Lösung für P1
8.4.3. Die Lösung für P2
8.5. Hanoi-Graphen zu höheren Basen
8.5.0. Des Teufels Nadel
8.5.1. Höhere Basen
Kapitel III. Spezielle Fragestellungen
9. Planarität
10. Färbungen
10.1. Eckenfärbung
10.2. Kantenfärbung
10.3. Totalfärbung
11. Metrische Eigenschaften
11.0. Metrische Eigenschaften der Hanoi-Graphen H_4^n
11.1. Dijkstras Algorithmus
Für ein Beispiel der praktischen Anwendung der Graphentheorie im
täglichen Leben siehe
Die KGB-Methode
A. M. Hinz, Andreas.Hinz@mathematik.uni-muenchen.de,
2008-02-26