Teaching

Algorithmen auf Graphen

Bachelorvorlesung im Wintersemester 2018/19
6 CP


Graphen sind ein wichtiges Modellierungswerkzeug in der Informatik und in den verschiedensten modernen Anwendungen. Ob wir einen Routenplaner, ein Smartphone oder Facebook nutzen, so stecken im Hintergrund Graphen und effiziente Verfahren, die graphentheoretische Probleme lösen.

Die Vorlesung gibt eine grundlegende Einführung in die Graphentheorie, die Modellierung von Praxisfragestellungen und Algorithmen zum Lösen dieser. Es werden insbesondere kombinatorische Optimierungsprobleme behandelt, die sich graphentheoretisch formulieren lassen und die mit Hilfe von Polynomialzeitalgorithmen optimal gelöst werden können. Dazu gehören bspw. kürzeste Wege, Rundreiseprobleme (Euler- und Hamiltonkreise), minimale Spannbäume, stabile und maximale Matchings und Flüsse in Netzwerken. Desweiteren werden Grundlagen der Komplexitätsheorie (P, NP, Vollständigkeit, Härte) mit Bezug auf Probleme in Graphen (Färben, Clique, TSP, Hamiltonkreis) behandelt.

Dozentin:
Assistent:
Prof. Dr. Nicole Megow (Email)
Lukas Nölke (Email)
Zeit & Raum:


Mo 10-12 Uhr in Raum MZH 6190 (Vorlesung)
Di 10-11:30 Uhr in Raum MZH 1090 (Übung 1)
Di 12:30-14 Uhr in Raum MZH 3150 (Übung 2)
Start:
Dienstag, 16. Oktober 2018
Literatur:




[KV] Korte, Vygen: Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2012.
[KN] Krumke, Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer-Vieweg, 2012.
[CLRS] Corman, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd edition, MIT Press, 2009.
[KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006.
[AMO] Ahuja, Magnanti, Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

Ein- und Austragen von Prüfungsterminen in Stud.IP ist möglich bis zum 15. Februar, 12:00 Uhr.

Die Bearbeitung der Übungsblätter erfolgt in Gruppen von 2-3 Studierenden. Die Abgabe erfolgt in der Vorlesung am Montag eine Woche später.

Datum Thema Vorlesungsunterlagen
16. Oktober Einführung, grundlegende Graphenbegriffe, Eulersche Graphen Folien, Notizen, Blatt 1
22. Oktober Grundlagen Algorithmen, Korrektheitbeweise und Laufzeitanalyse, Breitensuche Notizen (Handschriftlich), Blatt 2
29. Oktober Kürzeste Wege, Dijkstra's Algorithmus Folien, Notizen, Blatt 3
5. November Kürzeste Wege II (Bellman-Ford, Floyd-Warshall) und Bäume Folien, Notizen, Blatt 4
12. November Minimale aufspannende Bäume (Prim, Kruskal), Clustering Folien , Blatt 5
19. November Netzwerkflüsse, Maximaler s-t-Fluss, Max Fluss = Min Schnitt Folien, Notizen, Blatt 6, Netzwerk
26. November Weitere Flussprobleme, bipartite Graphen, Matchings Notizen, Blatt 7
03. Dezember Matchings, Satz von König, Satz von Hall, M-augmentierende Wege Notizen, Blatt 8
10. Dezember Stabile Matchings, Gale-Shapley, Komplexitätstheorie Folien M, Folien K (neu S.11), Blatt 9
17. Dezember NP-schwere Graphenprobleme Folien, Notizen, Blatt 10
7. Januar Programmieraufgabe (Keine Vorlesung/Übung) Blatt 11, Materialien
14. Januar NP-schwere Graphenprobleme II Folien, Notizen, Blatt 12
21. Januar Approximationsalgorithmen, Metrisches TSP, Christofides, Inapproximierbarkeit Notizen, Blatt 13
28. Januar Heuristiken für TSP (Nearest neighbor, Lokale Suche, Ausblick Metaheuristiken), Zusammenfassung Folien