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.

    • Allgemeine Informationen zur Vorlesung und Übung (Stand 17.04.2021) Файл
    • 01. Vorlesung (22.04.2020): Einführung Файл
    • 01. Vorlesung (22.04.2020): Druckversion (Einführung) Файл
    • 01. Vorlesung (22.04.2020): Video (Einführung) Файл
    • 01. Vorlesung (22.04.2020): Rundreiseprobleme I: Eulerkreise [24.04.: Nach Chat zwei Folien hinzugefügt – danke für die Frage, JG!] Файл
    • 01. Vorlesung (22.04.2020): Druckversion (Eulerkreise) Файл
    • 01. Vorlesung (22.04.2020): Video (Eulerkreise) Файл
    • 01. Vorlesung (22.04.2020): Rundreiseprobleme II: Hamiltonkreise Файл
    • 01. Vorlesung (22.04.2020): Druckversion (Hamiltonkreise) Файл
    • 01. Vorlesung (22.04.2020): Video (Hamilton) Файл
    • 02. Vorlesung (29.04.2020): Problem des Handlungsreisenden (TSP) Файл
    • 02. Vorlesung (29.04.2020): Druckversion Файл
    • 02. Vorlesung (29.04.2020): Video (TSP Teil I – Exakte Algorithmen) Страница
    • 02. Vorlesung (29.04.2020): Video (TSP Teil II – Komplexität) [mit Inhaltsverzeichnis – danke für den Tipp, RH!] Файл
    • 03. Vorlesung (06.05.2020): Lineare Programmierung Файл
    • 03. Vorlesung (06.05.2020): Druckversion Файл
    • 03. Vorlesung (06.05.2020): Video [>100 MB, daher leider ohne Inhaltsverzeichnis] Страница
    • 04. Vorlesung (13.05.2019): Max-Flow-Min-Cut-Theorem, Flussalgorithmen [13.05.: Korollar dank SW klarer formuliert] Файл
    • 04. Vorlesung (13.05.2019): Druckversion Файл
    • 04. Vorlesung (13.05.2019): Video (Teil I – 22 Min.) Файл
    • 04. Vorlesung (13.05.2019): Video (Teil II – 15 Min.) Файл
    • 04. Vorlesung (13.05.2019): Video (Teil III – Beweis der Laufzeit von Edmonds-Karp, 22 Min.) Файл
    • 05. Vorlesung (20.05.2020): Paarungen (Matchings) Файл
    • 05. Vorlesung (20.05.2020): Druckversion Файл
    • 05. Vorlesung (20.05.2020): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Файл
    • 05. Vorlesung (20.05.2020): Video (Teil II – Heiratssatz, 8 Min.) Файл
    • 06. Vorlesung (27.05.2020): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden Файл
    • 06. Vorlesung (27.05.2020): Druckversion Файл
    • 06. Vorlesung (27.05.2020): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Файл
    • 06. Vorlesung (27.05.2020): Video (Teil II – Algorithmus von Christofides, 13 Min.) Файл
    • 06. Vorlesung (27.05.2020): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Файл
    • 07. Vorlesung (03.06.2020): Minimale Wurzelspannbäume Файл
    • 07. Vorlesung (03.06.2020): Druckversion Файл
    • 07. Vorlesung (03.06.2020): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Файл
    • 07. Vorlesung (03.06.2020): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Файл
    • 08. Vorlesung (10.06.2020): Randomisierte Algorithmen für MinCut [10.6.: Plot hinzugefügt] Файл
    • 08. Vorlesung (10.06.2020): Druckversion Файл
    • 08. Vorlesung (10.06.2020): Video (45 Min.) Страница
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 09. Vorlesung (17.06.2020): Färbungen, Cliquen und unabhängige Mengen Файл
    • 09. Vorlesung (17.06.2020): Druckversion Файл
    • 09. Vorlesung (17.06.2020): Video Страница
    • 10. Vorlesung (24.06.2020): Fest-Parameter-Berechenbarkeit Файл
    • 10. Vorlesung (24.06.2020): Druckversion Файл
    • 10. Vorlesung (24.06.2020): Video (42 Min.) Страница
    • 11. Vorlesung (01.07.2020): Planare Graphen Файл
    • 11. Vorlesung (01.07.2020): Druckversion Файл
    • 11. Vorlesung (01.07.2020): Video (Teil 1, 35 Min.) Страница
    • 11. Vorlesung (01.07.2020): Video (Teil 3, 21 Min.) Файл
    • 12. Vorlesung (08.07.2020): Färben planarer Graphen und Planaritätstest [08.08.: Folie "Anzahl der rekursiven Aufrufe" hinzugefügt] Файл
    • 12. Vorlesung (08.07.2020): Druckversion Файл
    • 12. Vorlesung (08.07.2020): Video (Teil I – Färben planarer Graphen, 18 Min.) Файл
    • 12. Vorlesung (08.07.2020): Video (Teil II – Planaritätstest, 26 Min.) Файл
    • 13. Vorlesung (15.07.2020): PageRank und Power-Methode Файл
    • 13. Vorlesung (15.07.2020): Druckversion Файл
    • 13. Vorlesung (15.07.2020): Video (11 Min.) Файл
    • The Mathematics of Google Search (von Raluca Tanase und Remus Radu) Гиперссылка
    • 14. Vorlesung (22.07.2020): Orthogonales Zeichnen mittels Flüssen (deutsch) Файл
    • 14. Vorlesung (22.07.2020): Druckversion Файл
    • 14. Vorlesung (22.07.2020): Orthogonale Zeichnungen mittels Flüssen (englisch, von Jonathan Klawitter) Гиперссылка
    • 14. Vorlesung (22.07.2020): Druckversion Гиперссылка
    • 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil I, Einleitung) Гиперссылка
    • 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil II, Orthogonale Repräsentation) Гиперссылка
    • 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil III: Orthogonale Zeichnung) Гиперссылка
    • 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Bonustrack: NP-Schwere der Flächenminimierung) Гиперссылка
◄ Kursbeschreibung
► Übung