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.