Topic outline
Vorlesung Algorithmische Graphentheorie
Umfang: 5 ECTS, 2+2 SWS [T:2,P:0] Zeit & Ort: Vorlesung: dienstags, 10–12, HS 2 Übung: freitags, 8:30–10:00, 10–12, SE III Voraussetzung: Vorlesung 
Algorithmen und DatenstrukturenZielgruppe: Bachelor Informatik ab 2. Semester Dozent: Alexander Wolff Übung: Philipp Kindermann (E12) sowie Hiwis Matthias Mayer und Julian Behringer 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.
Voraussetzungen
- Vorlesung Algorithmen und Datenstrukturen
Weiterführende Veranstaltungen
- Vorlesung Algorithmische Geometrie (jedes WS)
- Vorlesung Approximationsalgorithmen (jedes ungerade SS außer SS'15)
- Vorlesung Exakte Algorithmen (jedes gerade SS)
- Vorlesung Visualisierung von Graphen (jedes SS)
- Seminar Visualisierung von Graphen (jedes WS)
- siehe auch unsere Veranstaltungsübersicht
Klausur
Studierende in der neuen Studienordnung Informatik / Mathematik benötigen keine Klausurzulassung. Studierende in der alten Studienordnung erhalten die Zulassung, wenn sie mindestens 50% der Übungspunkte erreichen.
Klausurtermine:
- Di, 14.07.2015, 10:00-12:00, HS 2
- Di, 06.10.2015, 10:00-12:00, Turing-HS
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 hier kapitelweise herunterladen kann, wenn man lokal an der Uni Würzburg eingeloggt ist. Eventuell muss man über den Katalog der UB auf die Verlagsseiten zugreifen.
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).
Übung
Es sind maximal zwei Bearbeiter pro Abgabe erlaubt.
Bitte geben Sie Ihre Lösungen zu Beginn der Vorlesung oder via WueCampus ab. Der Abgabetermin ist jeweils dienstags um 10:15 Uhr.