Ziel der Vorlesung i.a. ist die Herleitung von theoretischen Grundlagen fuer gewisse Algorithmen sowie die Entwicklung dieser Algorithmen selbst. Daraus ergeben sich auch polynomielle Abschaetzungen fuer die Laufzeiten dieser Algorithmen. Die hergeleiteten Algorithmen haben Anwendungen im OR aber auch in der Biomathematik. Ziel der Vorlesung ist es aber auch, den Studenten eine bestimmte Forschungsrichtung nahezubringen, in der sie auch Diplomarbeiten und schliesslich auch Doktorarbeiten angehen koennen.

Diese Vorlesung behandelt algorithmische Aspekte aus der Graphentheorie, allerdings von einem mehr theoretischen Standpunkt (es geht also nicht um Fragen der Implementierung von Algorithmen).
Zentrales Thema der Vorlesung sind verschiedene Typen kantenueberdeckender Wanderungen auf Graphen. Eulersche Linien sind in diesem Zusammenhang nur ein Spezialfall (hier soll jede Kante genau einmal durchlaufen werden), doch lassen sich viele Typen kantenueberdeckender Wanderungen auf das Auffinden eulerscher Linien in uebergeordneten Graphen zurueckfuehren. Das gilt insbesondere für das Chinesische Brieftraeger Problem (wo auch Elemente der Matching Theorie benoetigt werden), aber auch für die Durchlaufung von Labyrinthen (wo nur ueber lokale Information bei der jeweiligen Ankunft in einem Knoten verfuegt werden kann).

Inhaltlich ergibt sich die Struktur der Vorlesung dementsprechend:

• Charakterisierung Eulerscher Graphen
• Der Satz von Menger und das Spaltungs-Lemma, Knotenabspaltungen, spannende Baeume in ungerichteten und gerichteten Graphen (dieser Abschnitt dient quasi als theoretischer Hintergrund, aufgrunddessen das Funktionieren diverser Algorithmen in polynomieller Zeit begruendet werden kann)
• Algorithmen zur Erzeugung diverser Typen Eulerscher Linien
• Das Chinesische Briefträgerproblem
• Labyrinthe

Außerdem wird auf verschiedene Vermutungen hingewiesen werden, die u.a. mit der Charakterisierung Eulerscher Graphen in Zusammenhang stehen.

ECTS-Breakdown: 3 ECTS = 75 Stunden

25 h Vorlesung
20 h Uebungsvorbereitung
29 h Pruefungsvorbereitung
  1 h Pruefung
----
75 h gesamt

Achtung! Am 19.04.2016 findet keine Vorlesung statt!

Die Beurteilung der Lehrveranstaltung setzt sich aus aktiver Mitarbeit, der Bearbeitung von Uebungsbeispielen und einer muendlichen Abschlusspruefung zusammen. Stoff der Pruefung ist der gesamte waehrend der Lehrveranstaltung (Vorlesungs- und Uebungsteil) durchgenommene Lehrinhalt.

Grundkenntnisse aus der Graphentheorie sind wünschenswert, jedoch nicht unbedingt Voraussetzung.