Die Vorlesung basiert auf dem Buch Graphentheoretische Konzepte und Algorithmen von Sven Oliver Krumke and Hartmut Noltemeier (Vieweg+Teubner, 2. Auflage, 2009), das man sich aus dem Hochschulnetz hier kapitelweise herunterladen kann.
Außerdem setzt die Vorlesung einige Kapitel des Buchs Introduction to Algorithms (Algorithmen – eine Einführung) von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein (MIT Press und McGraw-Hill, 3. Auflage, 2009 bzw. De Gruyter Oldenbourg, 4. Auflage, 2013) voraus (BFS, DFS, Algorithmus von Dijkstra, minimale Spannbäume).
Sehr intuitiv geschrieben ist Algorithmic Graph Theory von Alan Gibbons (Cambridge University Press, 1985).
In der folgenden Tabelle liefert ein Klick aufs jeweilige Datum die Kurz-/Druckversion der Folien; ein Klick aufs Thema die Langversion.
| Datum |
Thema |
Videos (alt!) |
Literatur |
| 23.04.2025 |
Organisation und Einführung |
Einführung (12') |
|
| 23.04.2025 |
Rundreiseprobleme: Euler und Hamilton |
Euler (13'), Hamilton (14') |
|
| 30.04.2025 |
Lineare Programmierung und Fluss |
LP und Fluss (30') |
|
| 07.05.2025 |
Rundreiseprobleme III (TSP) |
Exakte Berechnung (28'), Komplexität und Approximation (12') |
|
| 21.05.2025 |
Max-Flow-Min-Cut-Theorem und Flussalgorithmen |
Schnitte, Residualgraphen, augmentierende Wege (22'), Algorithmus von Ford & Fulkerson (15'), Algorithmus von Edmonds & Karp (22') |
|
| 28.05.2025 |
Matchings I |
Satz von Menger, bipartites Matching (18'), Heiratssatz (8') |
|
| 04.06.2025 |
Matchings II |
Größte Matchings in bipartiten Graphen (8'), Chistofides' Algorithmus (13'), kostenminimales perfektes bipartites Matching (13'), Bonus: Beispiel dafür (pdf) |
|
| 11.06.2025 |
Wurzelspannbäume |
Edmonds' Algorithmus (18'), Laufzeit und Korrektheit (12'), Bonus: Beispiel dafür (pdf) |
|
| 18.06.2025 |
Randomisierte Algorithmen für MinCut |
Randomisierte MinCut-Algorithmen (45'), Bonus: Idee und Beispiel für den Stoer-Wagner-Algorithmus (pdf) |
Stoer-Wagner-Algorithmus (deterministisch) |
| 25.06.2025 |
Färbungen, Cliquen und unabhängige Mengen |
Färbungen, Cliquen und unabhängige Mengen (31') |
| 02.07.2025 |
Fest-Parameter-Berechenbarkeit am Beispiel von Vertex Cover |
Fest-Parameter-Berechenbarkeit (Video passt nicht mehr genau zum Vorlesungsinhalt; 42'), Bonus: Beispiel zum Grad-3-Algorithmus (pdf) |
| 09.07.2025 |
Planare Graphen |
Planare Graphen (35'), Planar-Separator-Theorem (21') |
| 16.07.2025 |
Färben planarer Graphen + Planaritätstest |
Färben planarer Graphen (18'), Planaritätstest (26'), Bonus: Beispiel zum Färben, Bonus: Beispiel zum Planaritätstest |
| 23.07.2025 |
Pagerank und Powermethode |
Pagerank und Powermethode (11'), Bonus: Webseite dazu |
| 23.07.2025 |
Rucksackproblem |
Bonus: ILP-Formulierung dazu, Bonus: Video von Thomas van Dijk dazu |
