Dr. E. Dahlhaus
Vorlesung Graphentheorie 4 St. Mo. 11-13, Do. 9-11 im Hörsaal Pohligstraße Übungen 2 St. Nach Vereinbarung Seminar Ausgewählte Kapitel aus der algorithmischen Graphentheorie Termine nach Vereinbarung
Die Vorlesung beschäftigt sich mit grundlegenden Problemen auf Graphen bzw. Kantenzügen. Ein klassisches Problem ist zum Beispiel die Färbung der Punkte (bzw. Ecken) derart, daß benachbarte Punkte verschieden gefärbt sind. Ein Spezialfall davon ist die Färbung von Graphen mit vier Farben, wenn der Graph auf die Ebene einbettbar ist. Ein anderes Beispielproblem ist das "maximale Flußproblem". Gegeben sind zwei Punkte, und es sollen möglichst viele Wege von a nach b bestimmt werden, die keine Kante (Verbindung zwischen zwei Punkten) gemeinsam haben.
Literatur wird in der ersten Vorlesungsstunde bekanntgegeben.
Eine zweistündige Übung ist vorgesehen. Der Übungsschein kann für das Fach Mathematik verwendet werden.
Das Seminar beschäftigt sich mit Algorithmen auf Graphen. Es ist in diesem Semester beabsichtigt, verschiedene Verfahren, Graphen nach bestimmten Kriterien in Komponenten zu zerlegen, zu behandeln.
Der Seminarschein kann für das Fach Informatik verwendet werden.