Vorlesung Graphentheorie (Sommer 2023)
News
- 10.04.2023 Webseite online
- 10.04.2023 ILIAS-Seite online
- 18.07.2023 Letzte Vorlesung, Besprechung der Evaluation
Inhalt
In dieser Bachelorvorlesung für Informatiker werden folgende Inhalte aus der Graphentheorie behandelt:
- Zusammenhang
- Dominatoren
- BFS/DFS
- Minimaler Fluss/Maximaler Schnitt
- Gewichtetes Matching in bipartiten Graphen
- Graphfärbung
- Planare Graphen
Plan
- Vorlesung Dienstag (2h): 16:15-18:00 101-00-026
- oder Dienstag (1h): 16:15-17:00 101-00-026 an Übungstagen
| Datum | Vorlesung | Übung | |
| 18.04.2023 | 01: Organisation, Motivation & Ungerichtete Graphen (2h) | - | |
| 25.04.2023 | 02: Satz von König, Satz von Euler (2h) | - | |
| 02.05.2023 | 03: Gerichtete Graphen (1h) | 01 | |
| 09.05.2023 | 04: Bäume, MST (2h) | - | |
| 16.05.2023 | 05: Gerichtete Bäume, Dominatoren (1h) | 02 | |
| 23.05.2023 | 06: BFS, DFS (2h) | - | |
| 06.06.2023 | 07: Theorem von Berge und Hall (1h) | 03 | |
| 13.06.2023 | 08: Min Flow Max Cut (2h) | - | |
| 20.06.2023 | 09: Bipartite Matchings, Duale Probleme (1h) | 04 | |
| 27.06.2023 | 10: Weighted Matching in Bipartite Graphs (2h) | - | |
| 04.07.2023 | 11: Min-Cut/Max-Flow (1h) | 05 | |
| 11.07.2023 | 12: Graph-Färbung und Planare Graphen (2h) | - | |
| 18.07.2023 | 13: Kuratowskis Satz, Zusammenfassung und Ausblick (1h) | 06 |
Material
- Aktuelle ILIAS-Seite
- Englisch-sprachige Vorlesung von 2022 ILIAS
Übungsgruppen
- Gruppe 1, Hans Albert, Dienstag 17-18 Uhr, 051-00-006, deutsch, Präsenz
- Gruppe 2, Jürgen Mattheis, 17-18 Uhr, 051-00-034, deutsch, hybrid (BigBlueButton)
- Gruppe 3, Matthias Herrmann, 17-18 Uhr, 101-00-026, deutsch, online (BigBlueButton)
- Gruppe 4, Jürgen Mattheis, 18–19 Uhr, 051-00-034, englisch, hybrid (BigBlueButton)
- Gruppe 5, Hans Albert, 18-19 Uhr, 051-00-006, deutsch, Präsenz
- Gruppe 6, Matthias Herrmann, 18–19 Uhr, 051-00-031, deutsch, online (BigBlueButton)
Übungsgruppen werden in den ersten beiden Vorlesungswochen nach der Präferenz hinsichtlich Sprache und Präsenz eingeteilt.
Prüfung
Die 90-minütige schriftliche Prüfung findet am 8.09.2023 von 9:00-11:00 Uhr statt. Zusätzlich findet eine zweite ebenfalls schriftliche Prüfung für Studenten, die am 8.09.2023 verhindert sind am 26.07.2023 um 10 Uhr in Raum 051-02-007 statt. Melden Sie sich hierfür formlos im Forum dieser ILIAS-Seite im entsprechenden Thread an. Als Hilfsmittel außer Lebensmittel und Getränke ist ein eigenhändig beidseitig beschriebenes A4-Blatt zulässig. Versehen Sie es mit Ihren Namen und Matrikelnummer. Bitte melden Sie sich rechtzeitig elektronisch über das Campus-System an.
Literatur
- Introduction to Graph Theory, Second Edition, Douglas West, Prentice Hall 2002.
- Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online)
- Graph Theory, Reinhard Diestel, Electronic Edition 2010 pdf
Weitere Literatur wird in der Veranstaltung angegeben.