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

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

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