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

    Die Vorlesungsvideos sind nur sichtbar, wenn Sie in WueCampus eingeloggt sind.

    • 01. Vorlesung (14.04.2021): Einführung Fitxer
    • 01. Vorlesung (14.04.2021): Druckversion (Einführung) Fitxer
    • 01. Vorlesung (14.04.2021): Video (Einführung) Fitxer
    • 01. Vorlesung (14.04.2021): Rundreiseprobleme I: Eulerkreise [19.04.: Auf S. 4 Kante zu v0 durchgestrichen – danke, Vasil!] Fitxer
    • 01. Vorlesung (14.04.2021): Druckversion (Eulerkreise) Fitxer
    • 01. Vorlesung (14.04.2021): Video (Eulerkreise) Fitxer
    • 01. Vorlesung (14.04.2021): Rundreiseprobleme II: Hamiltonkreise Fitxer
    • 01. Vorlesung (14.04.2021): Druckversion (Hamiltonkreise) Fitxer
    • 01. Vorlesung (14.04.2021): Video (Hamiltonkreise) Fitxer
    • 02. Vorlesung (21.04.2021): Problem des Handlungsreisenden (TSP) Fitxer
    • 02. Vorlesung (21.04.2021): Druckversion Fitxer
    • 02. Vorlesung (21.04.2021): Video (TSP Teil I – Exakte Algorithmen) Pàgina
    • 02. Vorlesung (21.04.2021): Video (TSP Teil II – Komplexität) Fitxer
    • 02. Vorlesung (21.04.2021): Bonustrack – Dynamische Programmierung und das Rucksackproblem Fitxer
    • 02. Vorlesung (21.04.2021): Bonustrack – Druckversion Fitxer
    • 02. Vorlesung (21.04.2021): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') URL
    • 03. Vorlesung (28.04.2021): Lineare Programmierung Fitxer
    • 03. Vorlesung (28.04.2021): Druckversion Fitxer
    • 03. Vorlesung (28.04.2021): Video Pàgina
    • 03. Vorlesung (28.04.2021): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem Fitxer
    • 04. Vorlesung (05.05.2021): Max-Flow-Min-Cut-Theorem und Flussalgorithmen Fitxer
    • 04. Vorlesung (05.05.2021): Druckversion Fitxer
    • 04. Vorlesung (05.05.2021): Video (Teil I – 22 Min.) Fitxer
    • 04. Vorlesung (05.05.2021): Video (Teil II – 15 Min.) Fitxer
    • 04. Vorlesung (05.05.2021): Video (Teil III – 22 Min.) Fitxer
    • 05. Vorlesung (12.05.2021): Paarungen (Matchings) Fitxer
    • 05. Vorlesung (12.05.2021): Druckversion Fitxer
    • 05. Vorlesung (12.05.2021): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Fitxer
    • 05. Vorlesung (12.05.2021): Video (Teil II – Heiratssatz, 8 Min.) Fitxer
    • 05. Vorlesung (12.05.2021): Bonustrack – ILP-Formulierung für Größte Paarung Fitxer
    • 06. Vorlesung (19.05.2021): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden Fitxer
    • 06. Vorlesung (19.05.2021): Druckversion Fitxer
    • 06. Vorlesung (19.05.2021): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Fitxer
    • 06. Vorlesung (19.05.2021): Video (Teil II – Algorithmus von Christofides, 13 Min.) Fitxer
    • 06. Vorlesung (19.05.2021): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Fitxer
    • 06. Vorlesung (19.05.2021): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) Fitxer
    • 07. Vorlesung (26.05.2021): Minimale Wurzelspannbäume Fitxer
    • 07. Vorlesung (26.05.2021): Druckversion Fitxer
    • 07. Vorlesung (26.05.2021): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Fitxer
    • 07. Vorlesung (26.05.2021): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Fitxer
    • 07. Vorlesung (26.05.2021): Bonustrack – Beispiel für Edmonds' Algorithmus Fitxer
    • 08. Vorlesung (02.06.2021): Randomisierte Algorithmen für MinCut Fitxer
    • 08. Vorlesung (02.06.2021): Druckversion Fitxer
    • 08. Vorlesung (02.06.2021): Video (45 Min.) Pàgina
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 08. Vorlesung (02.06.2021): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel Fitxer
    • 09. Vorlesung (09.06.2021): Färbungen, Cliquen und unabhängige Mengen Fitxer
    • 09. Vorlesung (09.06.2021): Druckversion Fitxer
    • 09. Vorlesung (09.06.2021): Video (31 Min.) Pàgina
    • 10. Vorlesung (16.06.2021): Fest-Parameter-Berechenbarkeit (alte Folien, passen zum Video) Fitxer
    • 10. Vorlesung (16.06.2021): Druckversion Fitxer
    • 10. Vorlesung (16.06.2021): Der Grad-3-Algorithmus (einfacher als der Grad-4-Algorithmus). Fitxer
    • 10. Vorlesung (16.06.2021): Druckversion des Grad-3-Algorithmus Fitxer
    • 10. Vorlesung (16.06.2021): Bonustrack – Beispiel für den Grad-3-Algorithmus Fitxer
    • 10. Vorlesung (16.06.2021): Video (42 Min.) Pàgina
    • 11. Vorlesung (22.06.2021): Planare Graphen Fitxer
    • 11. Vorlesung (22.06.2021): Druckversion Fitxer
    • 11. Vorlesung (22.06.2021): Video (Teil 1, 35 Min.) Pàgina

    • 11. Vorlesung (22.06.2021): Teil 2 wird in der Zoom-Vorlesung "live" besprochen.

    • 11. Vorlesung (22.06.2021): Video (Teil 3, 21 Min.) Fitxer
    • 12. Vorlesung (30.06.2021): Färben planarer Graphen und Planaritätstest Fitxer
    • 12. Vorlesung (30.06.2021): Druckversion Fitxer
    • 12. Vorlesung (30.06.2021): Video (Teil I – Färben planarer Graphen, 18 Min.) Fitxer
    • 12. Vorlesung (30.06.2021): Video (Teil II – Planaritätstest, 26 Min.) Fitxer
    • 12. Vorlesung (30.06.2021): Bonustrack – Beispiel für den Planaritätstest von Auslander & Parter Fitxer
    • 13. Vorlesung (07.07.2021): Bonustrack – Beispiel für Thomassens Algorithmus zum 5-Listenfärben Fitxer
    • 13. Vorlesung (07.07.2021): PageRank und Power-Methode [kleine Änderungen am 7.7.] Fitxer
    • 13. Vorlesung (07.07.2021): Druckversion Fitxer
    • 13. Vorlesung (07.07.2021): Video (11 Min.) Fitxer
◄ Kursbeschreibung
► Übung