Graphen gehören zu den wichtigsten Modellen der Informatik die
zahlreiche praktische Anwendungen haben (z.B. im Verkehrs- und
Telekommunikationsbereich, der Produktionsplanung oder allgemein bei
vielen kombinatorischen Optimierungsproblemen).
Nach einer Einführung in die Grundbegriffe der Graphentheorie sollen
Suchverfahren, Zusammenhangs-Probleme, Bäume, Kürzeste Wege, Matching-
und Routing-Probleme, Knoten- und Kantenfärbungen behandelt werden.
Dabei steht die Entwicklung von effizienten Lösungsverfahren im Vordergrund.
In den Übungen sollen einige Algorithmen auch praktisch implementiert werden.
J.M. Aldous, R.J. Wilson: Graphs and applications, Springer, 2003
R. Diestel: Graphentheorie, Springer, 2000
J. Gross, J. Yellen: Graph theory and its applications, CRC Press, 1999
J. Gross, J. Yellen: Handbook of graph theory, CRC Press, 2004
D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI-Verlag, 1987
R. Sedgewick: Algorithms, Addison Wesley, 1988
V. Turau: Algorithmische Graphentheorie, Oldenbourg, 2004
Teilnahme:
Teilnehmen können alle interessierten Studierende aus den Studiengängen
Mathematik, Angewandte Systemwissenschaft, Cognitive Science.
Insbesondere können im Anschluss an die Veranstaltung Bachelor- oder
Diplomarbeiten vergeben werden.
Schein:
Voraussetzung für den Erwerb eines Scheins zur Veranstaltung
ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung
der Übungsaufgaben (jeweils 50% der Maximalpunkte in theoretischen und 50%
der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche
Absolvierung einer Klausur am Ende des Semesters.
Zusätzlich sollte jede Gruppe in den Übungen mindestens einmal eine Lösung
einer Programmieraufgabe vorstellen und eine Webseite zu einem speziellen
Thema erstellen.
Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen
aus den Übungen.
