Vorlesung: Graphentheorie
Termine
- 06.04.2021 erste VL
- 09.04.2021 UE (Technik ausprobieren, Organisation)
- 16.04.2021 UE (Besprechung des ersten UE-Blattes)
- 13.05.2021 keine VL (Himmelfahrt)
- 14.05.2021 keine UE
VL |
Dienstag |
12:15 - 13:45 |
BigBlueButton |
|
Donnerstag |
12:15 - 13:45 |
|
UE (Gruppe 1) |
Freitag |
10:15 - 11:45 |
BigBlueButton |
UE (Gruppe 2) |
Freitag |
12:15 - 13:45 |
|
Prüfungen |
12.07. & 13.07. |
|
BigBlueButton |
|
04.08. – 09.08. |
|
29.09. & 01.10. |
Die Vorlesungen und Übungen werden zu den angebenen Zeiten live über den BBB-Server der Universität abgehalten. Die Vorlesungen werden dabei aufgenommen und die Videos werden danach über den BBB-Server abrufbar sein. Das Passwort für den BBB-Raum der Vorlesung ist in STiNE verfügbar und der BBB-Raum der Übungen ist kennwortfrei.
Leistungsnachweis
- Bestehen der mündlichen Prüfung
(erfolgreiche Teilnahme an der Übung wird vorausgesetzt)
- Die Prüfungen finden am 12.07., 13.07, 05.08. und 06.08. statt. Die Prüfungstermine können über
das Sekretariat vereinbart werden.
Die Prüfungen finden online im BigBlueButton statt.
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
- Paarungen
- Zusammenhang
- Graphen in der Ebene
- Färbungen
- Kapitel 4.1-4.3 (ohne Satz 4.2.6)
- Netzwerke
- Extremale Graphentheorie
- Kapitel 6.1, Propositionen 6.2.1. und 6.2.2 und Hadwiger-Vermutung
- Ramseytheorie
- Hamiltonkreise
- Satz 8.1.1 und Proposition 8.1.2 und Kapitel 8.2
- Zufallsgraphen (20.06.-)
- Wohlquasiordnungen und Minoren (04.07.-07.07.)
Übungen
Die Übungen werden von Christian Reiher geleitet. In den Übungen wird der Stoff der Vorlesung
vertieft und es werden die Übungsaufgaben 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,
- erfolgreiche Präsentation in der Übung
- und 50% als ausreichend bewertete schriftliche Abgaben (in 3er Gruppen)
Es wird voraussichtlich 12 Übungsblätter mit jeweils vier Aufgaben für die Besprechung und einer
Aufgabe für die schrifliiche Abgabe geben.
Die Übungsaufgaben werden in der Übung und auf dieser Webseite bekanntgegeben und die schriftlichen Abgaben und Korrekturen werden über den Moodle-Server der Universität organisiert.
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, 5te Auflage, 2017
- R. Diestel: Graph Theory, Springer, 5th ed., 2016/17
|