Vorlesung: Graphentheorie
Termine
- 04.04.2016 (erste VL)
- 11.04.2016 (erste UE)
- 05.05.2016 Feiertag (Christi Himmelfahrt)
- 16.-20.05.2016 Pfingstferien
| VL |
Montag |
10:15 - 11:45 |
Geomatikum, H3 |
|
Donnerstag |
10:15 - 11:45 |
Geomatikum, H2 |
| UE |
Montag |
12:15 - 13:45 |
Geomatikum, 1240 |
Leistungsnachweis
- Bestehen der mündlichen Prüfung (erfolgreiche Teilnahme an der Übung wird vorausgesetzt)
- Termin nach Absprache
Einordnung
- Wahlpflichtmodul, Bachelor (4. Semester), 9LP
- 4+2 SWS
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 (04.04.-11.04.)
- Kapitel 0.1-0.6 und 0.8 aus [D-De]
- Paarungen & Überdeckungen (11.04.-14.04)
- Kapitel 1.1 und 1.2 [D-De]
- Zusammenhang (18.04.-21.04.)
- Kapitel 2.1-2.3 aus [D-De]
- Graphen in der Ebene (25.04.-12.05.)
- Kapitel 3.1, 3.2 und 3.4 aus [D-De]
- Färbungen (12.05.-02.06.)
- Kapitel 4.1-4.3, Satz 4.4.2, Propositionen 4.5.1 und 4.5.2 aus [D-De]
- Netzwerke (02.06.)
- Extremale Graphentheorie (06.06.)
- Kapitel 6.1, Propositionen 6.2.1. und 6.2.2 und Hadwiger-Vermutung aus [D-De]
- Ramseytheorie für Graphen (09.06.)
- Hamiltonkreise (13.06.-16.06.)
- Satz 8.1.1 und Proposition 8.1.2 und Kapitel 8.2 aus [D-De]
- Zufallsgraphen (20.06.-)
- Kapitel 9.1, 9.2 und 9.3 (bis Korollar 9.3.3) aus [D-De]
- Wohlquasiordnungen und Minoren (04.07.-07.07.)
- Kapitel 10.1 und 10.2 aus [D-De]
Übungen
Die Übungen werden von
Jakob Schnitzer
geleitet. Es
wird der Stoff der Vorlesung
vertieft und es werden die Übungaufgaben besprochen und von den Studierenden vorgetragen.
Für die erfolgreiche Teilnahme an der Übung sind folgende Kriterien zu erfüllen:
- 50% der Punkte der bepunkteten Übungsaufgaben
- 50% als ausreichend bewertete schriftliche Abgaben
Es wird voraussichtlich 12 Übungsblätter mit jeweils Aufgaben für ca. 5 Punkte und einer
Aufgabe für die schrifliiche Abgabe geben. Zusätzlich wird es auf jedem Übungsblatt
ein paar leichte Aufgaben (ohne Punkte) geben, die nicht gewertet werden
und nur für den Einstieg gedacht sind. Die Übungsaufgaben werden in der Übung und auf dieser Webseite bekanntgegeben.
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
| 
