Section outline

◄ Kursbeschreibung
► Übung

  • 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).

    • 01. Vorlesung (27.04.2022): Einführung Файл
    • 01. Vorlesung (27.04.2022): Druckversion (Einführung) Файл
    • 01. Vorlesung (27.04.2022): Video (Einführung) Файл
    • 01. Vorlesung (27.04.2022): Rundreiseprobleme I: Eulerkreise Файл
    • 01. Vorlesung (27.04.2022): Druckversion (Eulerkreise) Файл
    • 01. Vorlesung (27.04.2022): Video (Eulerkreise) Файл
    • 01. Vorlesung (27.04.2022): Rundreiseprobleme II: Hamiltonkreise Файл
    • 01. Vorlesung (27.04.2022): Druckversion (Hamiltonkreise) Файл
    • 01. Vorlesung (27.04.2022): Video (Hamiltonkreise) Файл
    • 02. Vorlesung (04.05.2022): Lineare Programmierung Файл
    • 02. Vorlesung (04.05.2022): Druckversion Файл
    • 02. Vorlesung (04.05.2022): Video Страница
    • 02. Vorlesung (04.05.2022): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem Файл
    • 03. Vorlesung (18.05.2022): Problem des Handlungsreisenden (TSP) [30.5.: Minimum bei TSP-DP geklärt] Файл
    • 03. Vorlesung (18.05.2022): Druckversion Файл
    • 03. Vorlesung (18.05.2022): Video (TSP Teil I – Exakte Algorithmen) Страница
    • 03. Vorlesung (18.05.2022): Video (TSP Teil II – Komplexität und Approximation) Файл
    • 03. Vorlesung (18.05.2022): Dynamische Programmierung und das Rucksackproblem Файл
    • 03. Vorlesung (18.05.2022): Druckversion Файл
    • 03. Vorlesung (18.05.2022): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') Гиперссылка
    • 04. Vorlesung (25.05.2022): Max-Flow-Min-Cut-Theorem und Flussalgorithmen Файл
    • 04. Vorlesung (25.05.2022): Druckversion Файл
    • 04. Vorlesung (25.05.2022): Video (Teil I – 22 Min.) Файл
    • 04. Vorlesung (25.05.2022): Video (Teil II – 15 Min.) Файл
    • 04. Vorlesung (25.05.2022): Video (Teil III – 22 Min.) Файл
    • 05. Vorlesung (01.06.2022): Paarungen (Matchings) Файл
    • 05. Vorlesung (01.06.2022): Druckversion Файл
    • 05. Vorlesung (01.06.2022): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Файл
    • 05. Vorlesung (01.06.2022): Video (Teil II – Heiratssatz, 8 Min.) Файл
    • 06. Vorlesung (08.06.2022): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden Файл
    • 06. Vorlesung (08.06.2022): Druckversion Файл
    • 06. Vorlesung (08.06.2022): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Файл
    • 06. Vorlesung (08.06.2022): Video (Teil II – Algorithmus von Christofides, 13 Min.) Файл
    • 06. Vorlesung (08.06.2022): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Файл
    • 06. Vorlesung (08.06.2022): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) Файл
    • 07. Vorlesung (15.06.2022): Minimale Wurzelspannbäume Файл
    • 07. Vorlesung (15.06.2022): Druckversion Файл
    • 07. Vorlesung (15.06.2022): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Файл
    • 07. Vorlesung (15.06.2022): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Файл
    • 07. Vorlesung (15.06.2022): Bonustrack – Beispiel für Edmonds' Algorithmus Файл
    • 08. Vorlesung (22.06.2022): Randomisierte Algorithmen für MinCut [22.06., 12:00: kleine Änderungen] Файл
    • 08. Vorlesung (22.06.2022): Druckversion Файл
    • 08. Vorlesung (22.06.2022): Video (45 Min.) Страница
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 08. Vorlesung (22.06.2022): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel Файл
    • 09. Vorlesung (29.06.2022): Färbungen, Cliquen und unabhängige Mengen Файл
    • 09. Vorlesung (29.06.2022): Druckversion Файл
    • 09. Vorlesung (29.06.2022): Video (31 Min.) Страница
    • 10. Vorlesung (06.07.2022): Fest-Parameter-Berechenbarkeit – u.a. der Grad-3-Suchbaum-Algorithmus für Vertex Cover Файл
    • 10. Vorlesung (06.07.2022): Druckversion Файл
    • 10. Vorlesung (06.07.2022): Bonustrack – Beispiel für den Grad-3-Suchbaum-Algorithmus Файл
    • 10. Vorlesung (06.07.2022): Video (42 Min.) Страница
    • 10. Vorlesung (06.07.2022): Fest-Parameter-Berechenbarkeit (alte Folien, passen zum Video) – Druckversion Файл
    • 11. Vorlesung (12.07.2022): Planare Graphen [Reminder fürs Anmelden zur Hauptklausur hinzugefügt] Файл
    • 11. Vorlesung (12.07.2022): Druckversion Файл
    • 11. Vorlesung (12.07.2022): Video (Teil 1, 35 Min.) Страница

    • 11. Vorlesung (12.07.2022): Teil 2 ist nicht prüfungsrelevant (Teil 1 und 3 aber schon).

    • 11. Vorlesung (12.07.2022): Video (Teil 3, 21 Min.) Файл
    • 12. Vorlesung (20.07.2022): Färben planarer Graphen und Planaritätstest Файл
    • 12. Vorlesung (20.07.2022): Druckversion Файл
    • 12. Vorlesung (20.07.2022): Video (Teil I – Färben planarer Graphen, 18 Min.) Файл
    • 12. Vorlesung (20.07.2022): Video (Teil II – Planaritätstest, 26 Min.) Файл
    • 12. Vorlesung (20.07.2022): Bonustrack – Beispiel für den Planaritätstest von Auslander & Parter Файл
    • 12. Vorlesung (20.07.2022): Bonustrack – Beispiel für Thomassens Algorithmus zum 5-Listenfärben Файл
    • 13. Vorlesung (27.07.2022): PageRank und Power-Methode Файл
    • 13. Vorlesung (27.07.2022): Druckversion Файл
    • 13. Vorlesung (27.07.2022): Video (11 Min.) Файл
    • The Mathematics of Google Search (von Raluca Tanase und Remus Radu) Гиперссылка
◄ Kursbeschreibung
► Übung