Course: SS20: Algorithmische Graphentheorie

Topic outline

General

Vorlesung Algorithmische Graphentheorie

Umfang:	5 ECTS, 2+2 SWS [T:2,P:0]
Vorlesung:	mittwochs, 10:15–11:45 Uhr, HS 2 (Nat.wiss. HS-Bau)
Übungen:	1) freitags, 08:30–10:00 Uhr, SE I 2) freitags, 10:15–11:45 Uhr, SE II 3) freitags, 12:15–13:45 Uhr, SE I Bis auf weiteres finden zu den obengenannten Zeiten Online-Sprechstunden auf ifiChat statt. Zur Teilnahme muss man sich ggf. erst bei der Benutzerverwaltung der IT des Instituts ein Benutzerkonto einrichten ("New account" klicken) und dann auf ifiChat den beiden Kanälen agt-vorlesung und agt-uebung beitreten ("join"). Dazu brauchen Sie das Passwort V-E+F=2.
Voraussetzung:	Vorlesung Algorithmen und Datenstrukturen (dringend empfohlen)
Zielgruppe:	Bachelor Informatik ab 2. Semester
Anmeldung:	Einschreibung hier in diesen Wuecampus-Kurs. (Klicken Sie dazu im Kursraum ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.) Die Anmeldung zur Klausur erfolgt über WueStudy (siehe unten).
Dozent:	Alexander Wolff
Übungsleiter:	Diana Sieper, Vasil Alistarov, Lukas Schreiner, Annika Förster
Klausuren:	Mo, 27.07.2020, 11–14 Uhr, Z6: AOK-HS, 0.001 und 0.002 Do, 22.10.2020, 9–12 Uhr, Turing & Zuse Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.

Nachrichtenforum
Diskussionsforum
Restricted Not available unless: Your Email address is not empty

Kursbeschreibung
Inhalt

Wir werden uns grob mit den folgenden Themengebieten der algorithmischen Graphentheorie auseinandersetzen:
- kürzeste Wege,
- Minimale Spannbäume,
- Rundreiseprobleme (Euler- und Hamiltonkreise),
- Flüsse,
- Modellierung mittels (ganzzahliger) linearer Programmierung,
- Matchings,
- planare Graphen,
- Färbbarkeit,
- Approximation und Fest-Parameter-Berechenbarkeit.
Lernziele

Am Ende dieses Kurses sind HörerInnen in der Lage typische Probleme der Informatik als Graphenprobleme zu modellieren. Außerdem können TeilnehmerInnen entscheiden, welche Werkzeuge aus der Vorlesung dabei helfen ein gegebenes Graphenproblem algorithmisch zu lösen. Studierende lernen in diesem Kurs vertieft die Laufzeit von gegebenen Graphalgorithmen abzuschätzen.

Weiterführende Veranstaltungen
- Vorlesung Algorithmische Geometrie (jedes WS)
- Vorlesung Approximationsalgorithmen (jedes WS)
- Vorlesung Exakte Algorithmen (unregelmäßig)
- Vorlesung Visualisierung von Graphen (jedes SS)
- Seminar Visualisierung von Graphen (o.ä., jedes WS und dieses SS)
Siehe auch unsere Veranstaltungsübersicht
Materialien zur Vorlesung
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) File
- 01. Vorlesung (22.04.2020): Einführung File
- 01. Vorlesung (22.04.2020): Druckversion (Einführung) File
- 01. Vorlesung (22.04.2020): Video (Einführung) File
  Restricted Not available unless: Your ID number is not empty
- 01. Vorlesung (22.04.2020): Rundreiseprobleme I: Eulerkreise [24.04.: Nach Chat zwei Folien hinzugefügt – danke für die Frage, JG!] File
- 01. Vorlesung (22.04.2020): Druckversion (Eulerkreise) File
- 01. Vorlesung (22.04.2020): Video (Eulerkreise) File
  Restricted Not available unless: Your ID number is not empty
- 01. Vorlesung (22.04.2020): Rundreiseprobleme II: Hamiltonkreise File
- 01. Vorlesung (22.04.2020): Druckversion (Hamiltonkreise) File
- 01. Vorlesung (22.04.2020): Video (Hamilton) File
  Restricted Not available unless: Your ID number is not empty
- 02. Vorlesung (29.04.2020): Problem des Handlungsreisenden (TSP) File
- 02. Vorlesung (29.04.2020): Druckversion File
- 02. Vorlesung (29.04.2020): Video (TSP Teil I – Exakte Algorithmen) Page
  Restricted Not available unless: Your ID number is not empty
- 02. Vorlesung (29.04.2020): Video (TSP Teil II – Komplexität) [mit Inhaltsverzeichnis – danke für den Tipp, RH!] File
  Restricted Not available unless: Your ID number is not empty
- 03. Vorlesung (06.05.2020): Lineare Programmierung File
- 03. Vorlesung (06.05.2020): Druckversion File
- 03. Vorlesung (06.05.2020): Video [>100 MB, daher leider ohne Inhaltsverzeichnis] Page
  Restricted Not available unless: Your ID number is not empty
- 04. Vorlesung (13.05.2019): Max-Flow-Min-Cut-Theorem, Flussalgorithmen [13.05.: Korollar dank SW klarer formuliert] File
- 04. Vorlesung (13.05.2019): Druckversion File
- 04. Vorlesung (13.05.2019): Video (Teil I – 22 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 04. Vorlesung (13.05.2019): Video (Teil II – 15 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 04. Vorlesung (13.05.2019): Video (Teil III – Beweis der Laufzeit von Edmonds-Karp, 22 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 05. Vorlesung (20.05.2020): Paarungen (Matchings) File
- 05. Vorlesung (20.05.2020): Druckversion File
- 05. Vorlesung (20.05.2020): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 05. Vorlesung (20.05.2020): Video (Teil II – Heiratssatz, 8 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 06. Vorlesung (27.05.2020): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden File
- 06. Vorlesung (27.05.2020): Druckversion File
- 06. Vorlesung (27.05.2020): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 06. Vorlesung (27.05.2020): Video (Teil II – Algorithmus von Christofides, 13 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 06. Vorlesung (27.05.2020): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 07. Vorlesung (03.06.2020): Minimale Wurzelspannbäume File
- 07. Vorlesung (03.06.2020): Druckversion File
- 07. Vorlesung (03.06.2020): Video (Teil I – Edmonds' Algorithmus, 18 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 07. Vorlesung (03.06.2020): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 08. Vorlesung (10.06.2020): Randomisierte Algorithmen für MinCut [10.6.: Plot hinzugefügt] File
- 08. Vorlesung (10.06.2020): Druckversion File
- 08. Vorlesung (10.06.2020): Video (45 Min.) Page
  Restricted Not available unless: Your ID number is not empty
- Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
- 09. Vorlesung (17.06.2020): Färbungen, Cliquen und unabhängige Mengen File
- 09. Vorlesung (17.06.2020): Druckversion File
- 09. Vorlesung (17.06.2020): Video Page
  Restricted Not available unless: Your ID number is not empty
- 10. Vorlesung (24.06.2020): Fest-Parameter-Berechenbarkeit File
- 10. Vorlesung (24.06.2020): Druckversion File
- 10. Vorlesung (24.06.2020): Video (42 Min.) Page
  Restricted Not available unless: Your ID number is not empty
- 11. Vorlesung (01.07.2020): Planare Graphen File
- 11. Vorlesung (01.07.2020): Druckversion File
- 11. Vorlesung (01.07.2020): Video (Teil 1, 35 Min.) Page
  Restricted Not available unless: Your Department is not empty
- 11. Vorlesung (01.07.2020): Video (Teil 3, 21 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 12. Vorlesung (08.07.2020): Färben planarer Graphen und Planaritätstest [08.08.: Folie "Anzahl der rekursiven Aufrufe" hinzugefügt] File
- 12. Vorlesung (08.07.2020): Druckversion File
- 12. Vorlesung (08.07.2020): Video (Teil I – Färben planarer Graphen, 18 Min.) File
  Restricted Not available unless any of:
  Your ID number is not empty
  You enter the correct password
- 12. Vorlesung (08.07.2020): Video (Teil II – Planaritätstest, 26 Min.) File
  Restricted Not available unless: Your ID number is not empty
- 13. Vorlesung (15.07.2020): PageRank und Power-Methode File
- 13. Vorlesung (15.07.2020): Druckversion File
- 13. Vorlesung (15.07.2020): Video (11 Min.) File
  Restricted Not available unless any of:
  Your ID number is not empty
  You enter the correct password
- The Mathematics of Google Search (von Raluca Tanase und Remus Radu) URL
- 14. Vorlesung (22.07.2020): Orthogonales Zeichnen mittels Flüssen (deutsch) File
- 14. Vorlesung (22.07.2020): Druckversion File
- 14. Vorlesung (22.07.2020): Orthogonale Zeichnungen mittels Flüssen (englisch, von Jonathan Klawitter) URL
- 14. Vorlesung (22.07.2020): Druckversion URL
- 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil I, Einleitung) URL
- 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil II, Orthogonale Repräsentation) URL
- 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Teil III: Orthogonale Zeichnung) URL
- 14. Vorlesung (22.07.2020): Video von Jonathan Klawitter (Bonustrack: NP-Schwere der Flächenminimierung) URL
Übung
Es wird ca. 11 Übungsblätter geben. Auf den bewerteten Blättern können jeweils bis zu 20 Punkte erreicht werden. Sie dürfen maximal in 2er-Gruppen abgeben. Bitte geben Sie die Namen aller Mitarbeiter an. Sie sollten Ihre Lösung während der Übung vorliegen haben.

Pro Gruppe ist das Übungsblatt von einem Gruppenmitglied auf WueCampus hochzuladen (bevorzugt mit Latex erstellt, bitte vermeiden Sie Fotographien von Abgaben). Der Abgabetermin ist dienstags um 12:00 Uhr.
- Wiederholung von wichtigen Graphalgorithmen aus der ADS-Vorlesung [24.04.: Betragsstriche bei BFS entfernt – Danke, JS! Laufzeit fürs Zählen der Zusammenhangskomponenten vermerkt]] File
- Wiederholung ADS – Druckversion File
- Wiederholung ADS – Video Page
- 1. Übungsblatt (Abgabe bis 28.04.2020) Assignment
  [PDF-Download]
- 2. Übungsblatt (Abgabe bis 05.05.2020) Assignment
  [PDF-Download]
- Einführung in OPL, Teil 1 File
- 3. Übungsblatt (Abgabe bis 12.05.2020) Assignment
  [PDF-Download]
  Bitte laden Sie hier zusätzlich zu der pdf-Abgabe den Quelltext zu Aufgabe 1 hoch.
- 4. Übungsblatt (Abgabe bis 19.05.2020) Assignment
  [PDF-Download]
- 5. Übungsblatt (Abgabe bis 26.06.2020) Assignment
  [PDF-Download]
- Einführung in OPL, Teil 2 File
- 6. Übungsblatt (Abgabe bis 02.06.2020) Assignment
  [PDF-Download]
- 7. Übungsblatt (Abgabe bis 09.06.2020) Assignment
  [PDF-Download]
- 8. Übungsblatt (Abgabe bis 16.06.2020) Assignment
  [PDF-Download]
- 9. Übungsblatt (Abgabe bis 23.06.2020) Assignment
  [PDF-Download]
- 10. Übungsblatt (Abgabe bis 30.06.2020) Assignment
  [PDF-Download]
- 11. Übungsblatt (Abgabe bis 07.07.2020) Assignment
  [PDF-Download]
- 12. Übungsblatt (Abgabe bis 14.07.2020) Assignment
  [PDF-Download]
- 1. Tutoriumsblatt (Gemeinsame Bearbeitung 24.07.2020) Assignment
  [PDF-Download]
- Lösungshinweise Tutoriumsblatt File
  Restricted Not available unless: Your Email address is not empty
- Quiz zur 1. Vorlesung

SS20: Algorithmische Graphentheorie

Topic outline

General

Vorlesung Algorithmische Graphentheorie

Kursbeschreibung

Inhalt

Lernziele

Weiterführende Veranstaltungen

Materialien zur Vorlesung

Übung