Graphen und Algorithmen

Vorlesung: Mittwoch 15:00-16:30 im Curie-Hörsaal
Dozent: Jens M. Schmidt
Übung: Donnerstag 17:00-18:30 im Curie-Hörsaal (gerade Wochen)
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Bachelor 5. Fachsemester
Voraussetzungen: Einführung in die diskrete Mathematik, Einführung in OR und lineare Optimierung
Prüfung:

Prüfungsvoraussetzungen sind die regelmäßige und aktive Mitarbeit in den Übungen und das Vorstellen eigener Lösungen von Übungsaufgaben. Zum Ende der Vorlesungszeit wird eine mündliche Prüfung angeboten (eine Kombiprüfung ist möglich, diese bitte rechtzeitig anmelden).
Skript:Ein vorläufiges Skript ist hier verfügbar.
Literatur:




  • L. Lovasz, M. D. Plummer - Matching Theory, AMS Chelsea, 2009.
  • B. Korte und J. Vygen - Combinatorial Optimization, 5th Edition, Springer, 2012.
  • R. Diestel - Graph Theory, 3th Edition, Springer, 2010.
  • D. Jungnickel - Graphs, Networks and Algorithms, 4th Edition, 2013.


Datum Inhalt Übung
11.10.2017 Grundlagen Einführung in Graphen, Wege und Kreise, Baumcharakterisierungen ueb01.pdf
18.10.2017 Berechnungsmodell Bipartite Graphen, Unit-cost RAM, Zeitkomplexität, O-Notation
25.10.2017 Graphtraversierung Graph-Repräsentationen, Wurzelbäume, Breitensuche und Distanzbäume in O(n+m) ueb02.pdf
01.11.2017 Graphtraversierung Tiefensuche gerichtet und ungerichtet in O(n+m), Kantenklassifikation, Finishing Time, Kreisdetektion, Starke Zusammenhangskomponenten in O(n+m)
08.11.2017 Eulersche Graphen Eulersche Graphen und Eulerzüge, Fleurys Algorithmus, Hierholtzers Algorithmus in O(n+m) ueb03.pdf
15.11.2017 Matchings Satz von Petersen-Berge, Satz von Hall, Bipartite Matchings in O(nm)
22.11.2017 Matchings Stabile Matchings, Gale-Shapley in O(n2), Optimalität/Pessimalität ueb04.pdf
29.11.2017 Matchings Tuttes Faktorsatz, Barrieren, Edmonds Blütenschrumpf-Algorithmus in O(n2m), Matchingspiel, Tutte-Berge Formel
06.12.2017 Matchings Faktorkritische Graphen, Ungerade Ohrendekompositionen ueb05.pdf
13.12.2017 Matchings Dekomposition von Gallai-Edmonds in O(n2m)
20.12.2017 Zusammenhang Zusammenhangsparameter und deren Beziehung ueb06.pdf
10.01.2018 Zusammenhang Mengers Theorem (Matroidversion), Menger-Varianten
17.01.2018 Zusammenhang Randomisierter Minimaler Schnitt in O(n4 log n) ueb07.pdf
24.01.2018 Planarität Einführung in planare Graphen, Jordanscher Kurvensatz und dessen Komplement (ohne Beweise), Eulersche Polyederformel
31.01.2018 Planarität Ebene Dualität, Das Museumswächterpoblem, 2-Ohrenlemma, Polygontriangulierungen