Materialien zur Vorlesung
Perfilado de sección
-
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 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
(+ Kurzversion)Thema (+ Langversion) Videos (alt!) Literatur 15.04.2026 Organisation und Einführung Einführung (12') 15.04.2026 Rundreiseprobleme: Euler und Hamilton Euler (13'), Hamilton (14') 22.04.2026 Lineare Programmierung und Fluss LP und Fluss (30') 06.05.2026 Rundreiseprobleme III (TSP) Exakte Berechnung (28'), Komplexität und Approximation (12') 13.05.2026 Max-Flow-Min-Cut-Theorem und Flussalgorithmen Schnitte, Residualgraphen, augmentierende Wege (22'), Algorithmus von Ford & Fulkerson (15'), Algorithmus von Edmonds & Karp (22') 20.05.2026 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)