|
Vorlesung: Graphentheorie
Termine
- 19.10.2010 (erste VL)
- 29.10.2010 (erste UE)
VL |
Dienstag |
10:15 - 11:45 |
Geomatikum, H4 |
|
Freitag |
10:15 - 11:45 |
Geomatikum, H4 |
UE |
Freitag |
08:30 - 10:00 |
Geomatikum, H3 |
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 (5. Semester), 9SP
- Vertiefungs- und Spezialvorlesung, Master, 12SP (letztmalig; höhere Anforderungen bei den Übungsaufgaben und in der Prüfung)
- 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,
so dass in der Vorlesung niemand mitschreiben muss.
- Grundbegriffe (19.10.-29.10.)
- Kapitel 0.1-0.6 und 0.8 aus [D-De]
- Paarungen & Überdeckungen (29.10.-05.11.)
- Kapitel 1.1, 1.2 und 1.5 aus [D-De]
- Zusammenhang (09.11.-16.11.)
- Kapitel 2.1-2.3 aus [D-De]
- Graphen in der Ebene (19.11.-26.11.)
- Kapitel 3.1, 3.2 und 3.4 aus [D-De]
- Färbungen (30.11., 10.12-14.12.)
- Kapitel 4.1-4.3 aus [D-De]
- Unendliche Graphen (03.12.-07.12.)
- Netzwerke (14.12.-17.12.)
- Kapitel 5.1 und 5.2 aus [D-De]
- Hamiltonkreise (04.01.-07.01.)
- Extremale Graphentheorie (11.01.-21.01.)
- Kapitel 6.1, Proposition 6.2.2 und Hadwiger-Vermutung aus [D-De]
- Ramseytheorie für Graphen (21.01.-25.01.)
- Zufallsgraphen (28.01.-01.02.)
- Kapitel 9.1, 9.2 und 9.3 (bis Korollar 9.3.3) aus [D-De]
- Wohlquasiordnungen und Minoren (04.02.)
- Kapitel 10.1 und 10.2 aus [D-De]
Folien der VL (Stand 15.02.11).
Übungen
In den Übungen wird der Stoff der Vorlesung
vertieft und es werden die Übungaufgaben besprochen und von den Studierenden vorgetragen.
Erforderlich für das Bestehen der Übung im Bachelor (9SP) ist die Lösung von insgesamt 50%
der normalen und der leichten (mit Minus markierten) Übungsaufgaben, wobei die normalen Aufgaben
mit 2 Punkten bewertet werden und die leichten mit nur einem Punkt. Die schweren Aufgaben (mit + markiert)
gehen in die Summe der verlangten Punkte beim Bachelor nicht ein, können aber zur Aufbesserung des Punktekontos
zusätzlich genutzt werden. Jede dieser Plusaufgaben bringt bei vollständig präsentierter
Lösung 6 Punkte, kann also drei normale oder sechs einfache Aufgaben ersetzen.
(Damit ist es im Bachelor möglich, mehr als 100% zu erlangen.)
Für das Bestehen der Übung im Master (12SP) ist es erforderlich 50% aller Punkte zu erreichen.
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, 4te Auflage, 2010
- R. Diestel: Graph Theory, Springer, 4th ed., 2010
|
|