186.181 Algorithms in Graph Theory
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2016S, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

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.

Inhalt der Lehrveranstaltung

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.

Weitere Informationen

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!


Vortragende

  • Fleischner, Herbert

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mi.11:00 - 13:0002.03.2016 Seminarraum 186 (Favoritenstrasse 9-11, 5.Stock)Vorbesprechung (mit Terminfindung)
Di.12:00 - 14:0008.03.2016 - 28.06.2016Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Algorithms in Graph Theory - Einzeltermine
TagDatumZeitOrtBeschreibung
Mi.02.03.201611:00 - 13:00 Seminarraum 186 (Favoritenstrasse 9-11, 5.Stock)Vorbesprechung (mit Terminfindung)
Di.08.03.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.15.03.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.05.04.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.12.04.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.26.04.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.03.05.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.10.05.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.24.05.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.31.05.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.07.06.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.14.06.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.21.06.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture
Di.28.06.201612:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Algorithms in Graph Theory Lecture

Leistungsnachweis

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.

LVA-Anmeldung

Nicht erforderlich

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

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

Begleitende Lehrveranstaltungen

Sprache

bei Bedarf in Englisch