Vorlesung: Graphentheorie
Termine
- 02.04.2013 (erste VL)
- 11.04.2013 (erste UE)
| VL |
Dienstag |
12:15 - 13:45 |
Geomatikum, H5 |
|
Donnerstag |
14:15 - 15:45 |
Geomatikum, H6 |
| UE |
Donnerstag |
16:00 - 17:30 |
Geomatikum, H6 |
Leistungsnachweis
- Bestehen der mündlichen Prüfung (erfolgreiche Teilnahme an der Übung wird vorausgesetzt)
- Prüfungstermine werden am Ende der Vorlesung vereinbart
Einordnung
- Vertiefungsmodul, Bachelor (4. Semester), 9LP
- 4+2 SWS
- Graphentheorie und Diskrete Mathematik
Voraussetzungen
Die Vorlesung setzt nur Grundbegriffe aus den Anfängervorlesungen des ersten Studienjahres
voraus. Vorherige Teilnahme an der Vorlesung „Diskrete Mathematik” ist nicht nötig.
Überblick
Die Graphentheorie ist eines der jüngsten und zugänglichsten Gebiete der Mathematik.
Ohne, wie in den klassischen Disziplinen oft unumgänglich, zunächst ein umfassendes
Instrumentarium an Begriffsapparat und Techniken beherrschen lernen zu müssen, begegnet man hier
von Anfang an mathematischen Problemen, die man im Prinzip ohne weitere Voraussetzungen selbst
bearbeiten könnte. Hierzu soll die Vorlesung sowohl einladen, als auch
den ordnend-motivierenden Rahmen darstellen.
Inhalte
In der Vorlesung werden die Leitprobleme und grundlegenden Sätze der Graphentheorie vorgestellt.
Die Vorlesung folgt dabei größtenteils der deutschen Ausgabe des Buches
Graphentheorie von Reinhard Diestel,
so dass in der Vorlesung niemand mitschreiben muss.
- Grundbegriffe (02.04.-11.04.)
- Kapitel 0.1-0.6 und 0.8 aus [D-De]
- Paarungen & Überdeckungen (11.04.-19.04.)
- Kapitel 1.1, 1.2 und 1.5 aus [D-De]
- Zusammenhang (26.04.-03.05.)
- Kapitel 2.1-2.3 aus [D-De]
- Graphen in der Ebene (03.05.-16.05.)
- Kapitel 3.1, 3.2 und 3.4 aus [D-De]
- Färbungen (16.05.-04.06.)
- Kapitel 4.1-4.4 aus [D-De]
- Netzwerke (04.06.-06.06.)
- Kapitel 5.1 und 5.2 aus [D-De]
- Extremale Graphentheorie (11.06.-13.06.)
- Kapitel 6.1, Proposition 6.2.2 und Hadwiger-Vermutung aus [D-De]
- Ramseytheorie für Graphen (18.06.)
- Hamiltonkreise (20.06.)
- Zufallsgraphen (25.06.-27.06.)
- Kapitel 9.1, 9.2 und 9.3 (bis Korollar 9.3.3) aus [D-De]
- Unendliche Graphen (02.07.)
- Wohlquasiordnungen und Minoren (09.07.-11.07.)
- Kapitel 10.1 und 10.2 aus [D-De]
Übungen
Die Übungen werden von
Prof. Christian Reiher
geleitet. Es
wird der Stoff der Vorlesung
vertieft und es werden die Übungaufgaben besprochen und von den Studierenden vorgetragen.
Erforderlich für das Bestehen der Übung ist die Lösung von insgesamt 50%
der normalen und der schweren (mit Plus markierten) Übungsaufgaben, wobei die normalen Aufgaben
mit einem Punkt und die schweren mit zwei Punkten bewertet werden. Die leichten Aufgaben (mit Minus markiert)
werden nicht gewertet und sind nur zum Einstieg gedacht. Es wird voraussichtlich 12 Übungsblätter
mit jeweils zwei bis drei normalen, ein oder zwei schweren Aufgaben, sowie einigen leichten Aufgaben geben.
Literatur
- B. Bollobás: Modern Graph Theory, Springer, 2nd ed., 1998
- J. A. Bondy & U. S. R. Murty: Graph Theory, Springer, 2008
- R. Diestel: Graphentheorie, Springer, 4. Auflage, 2010
- R. Diestel: Graph Theory, Springer, 4th ed., 2010
|
