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 (19.04.2023): Einführung Fitxer
    • 01. Vorlesung (19.04.2023): Druckversion (Einführung) Fitxer
    • 01. Vorlesung (19.04.2023): Video (Einführung, 12') Fitxer
    • 01. Vorlesung (19.04.2023): Rundreiseprobleme I: Eulerkreise Fitxer
    • 01. Vorlesung (19.04.2023): Druckversion (Eulerkreise) Fitxer
    • 01. Vorlesung (19.04.2023): Video (Eulerkreise, 13') Fitxer
    • 01. Vorlesung (19.04.2023): Rundreiseprobleme II: Hamiltonkreise Fitxer
    • 01. Vorlesung (19.04.2023): Druckversion (Hamiltonkreise) Fitxer
    • 01. Vorlesung (19.04.2023): Video (Hamiltonkreise, 14') Fitxer
    • 02. Vorlesung (26.04.2023): Lineare Programmierung Fitxer
    • 02. Vorlesung (26.04.2023): Druckversion Fitxer
    • 02. Vorlesung (26.04.2023): Video (30') Pàgina
    • 03. Vorlesung (03.05.2023): Problem des Handlungsreisenden (TSP) Fitxer
    • 03. Vorlesung (03.05.2023): Druckversion Fitxer
    • 03. Vorlesung (03.05.2023): Video (TSP Teil I – Exakte Algorithmen, 28') Pàgina
    • 03. Vorlesung (03.05.2023): Video (TSP Teil II – Komplexität und Approximation, 12') Fitxer
    • 04. Vorlesung (10.05.2023): Max-Flow-Min-Cut-Theorem und Flussalgorithmen [14.05.: kleine Korrektur auf S. 21/22] Fitxer
    • 04. Vorlesung (10.05.2023): Druckversion Fitxer
    • 04. Vorlesung (10.05.2023): Video (Teil I – 22 Min.) Fitxer
    • 04. Vorlesung (10.05.2023): Video (Teil II – 15 Min.) Fitxer
    • 04. Vorlesung (10.05.2023): Video (Teil III – 22 Min.) Fitxer
    • 05. Vorlesung (17.05.2023): Paarungen (Matchings) Fitxer
    • 05. Vorlesung (17.05.2023): Druckversion Fitxer
    • 05. Vorlesung (17.05.2023): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Fitxer
    • 05. Vorlesung (17.05.2023): Video (Teil II – Heiratssatz, 8 Min.) Fitxer
    • 06. Vorlesung (24.05.2023): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden Fitxer
    • 06. Vorlesung (24.05.2023): Druckversion Fitxer
    • 06. Vorlesung (24.05.2023): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Fitxer
    • 06. Vorlesung (24.05.2023): Video (Teil II – Algorithmus von Christofides, 13 Min.) Fitxer
    • 06. Vorlesung (24.05.2023): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Fitxer
    • 06. Vorlesung (24.05.2023): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) Fitxer
    • 07. Vorlesung (31.05.2023): Minimale Wurzelspannbäume Fitxer
    • 07. Vorlesung (31.05.2023): Druckversion Fitxer
    • 07. Vorlesung (31.05.2023): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Fitxer
    • 07. Vorlesung (31.05.2023): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Fitxer
    • 07. Vorlesung (31.05.2023): Bonustrack – Beispiel für Edmonds' Algorithmus Fitxer
    • 08. Vorlesung (07.06.2023): Randomisierte Algorithmen für MinCut Fitxer
    • 08. Vorlesung (07.06.2023): Druckversion Fitxer
    • 08. Vorlesung (07.06.2023): Video (45 Min.) Pàgina
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 08. Vorlesung (07.06.2023): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel Fitxer
    • 09. Vorlesung (14.06.2023): Färbungen, Cliquen und unabhängige Mengen [14.06.: kleine Änderungen, u.a. Kreis C -> K] Fitxer
    • 09. Vorlesung (14.06.2023): Druckversion Fitxer
    • 09. Vorlesung (14.06.2023): Video (31 Min.) Pàgina
    • 10. Vorlesung (21.06.2023): Fest-Parameter-Berechenbarkeit – u.a. der Grad-3-Suchbaum-Algorithmus für Vertex Cover Fitxer
    • 10. Vorlesung (21.06.2023): Druckversion Fitxer
    • 10. Vorlesung (21.06.2023): Bonustrack – Beispiel für den Grad-3-Suchbaum-Algorithmus Fitxer
    • 10. Vorlesung (21.06.2023): Video (42 Min.) – passt nicht mehr genau zu den Folien! Pàgina
    • 11. Vorlesung (28.06.2023): Planare Graphen Fitxer
    • 11. Vorlesung (28.06.2023): Druckversion Fitxer
    • 11. Vorlesung (28.06.2023): Video (Teil 1, 35 Min.) Pàgina
    • 11. Vorlesung (28.06.2023): Video (Teil 2, 21 Min.) Fitxer
    • 12. Vorlesung (05.07.2023): Färben planarer Graphen und Planaritätstest [05.07.: kosmetische Änderungen] Fitxer
    • 12. Vorlesung (05.07.2023): Druckversion Fitxer
    • 12. Vorlesung (05.07.2023): Video (Teil I – Färben planarer Graphen, 18 Min.) Fitxer
    • 12. Vorlesung (05.07.2023): Video (Teil II – Planaritätstest, 26 Min.) Fitxer
    • 12. Vorlesung (05.07.2023): Bonustrack – Beispiel für den Planaritätstest von Auslander & Parter Fitxer
    • 12. Vorlesung (05.07.2023): Bonustrack – Beispiel für Thomassens Algorithmus zum 5-Listenfärben Fitxer
    • 13. Vorlesung (12.07.2023): PageRank und Power-Methode Fitxer
    • 13. Vorlesung (12.07.2023): Druckversion Fitxer
    • 13. Vorlesung (12.07.2023): Video (11 Min.) Fitxer
    • 13. Vorlesung (12.07.2023): The Mathematics of Google Search (von Raluca Tanase und Remus Radu) URL
    • 13. Vorlesung (12.07.2023): Dynamische Programmierung und das Rucksackproblem Fitxer
    • 13. Vorlesung (12.07.2023): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem Fitxer
    • 13. Vorlesung (12.07.2023): Druckversion Fitxer
    • 13. Vorlesung (12.07.2023): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') URL
◄ Kursbeschreibung
► Übung