Algorithmische Graphentheorie

SS 2009, 3 VO/1 UE (502.754/502.755)

LV-Modus und - Unterlagen (pdf)

Die Vorlesung wird in Form eines klassischen Tafelvortrags gehalten.
Es gibt kein Skriptum zu dieser Vorlesung und es ist daher ratsam während des Vortrags mitzuschreiben.
Zu bestimmten Themen werden in der Vorlesung Präsentationsfolien verwendet.
Die dazugehörigen Files werden auf dieser Seite zur Verfügung gestellt.

Knotenfärbung:
- Backtracking nach Brown zur Bestimmung einer optimalen Knotenfärbung (pdf)
- Die Recursive-Largest-First Heuristik (pdf)
Kantenfärbung
Zwei Routinen aus dem Beweis des Satz von Vizing (pdf)
Test auf Planarität
Routinen eines "vertex addition"-Algorithmus (pseudo code) (pdf)
Test auf Planarität
Die sogenannten Template Matchings und ein Beispiel derer Anwendung zur Transformations eines PQ-Tree (pdf)

Jede zweite Woche wird eine doppelstundige Übungseinheit gehalten. Ca. eine Woche vor der jeweiligen Übungseinheit wird auf der LV-Homepage ein Übungsblatt veröffentlicht. Die darin enthaltenen Übungsbeispiele werden in der Übungseinheit besprochen; die Lösungen werden idealerweise von den Studierenden selbst vorgeführt.

cela@opt.math.tu-graz.ac.at.

Zurück zur Hauptseite der Lehrveranstaltung

Letzte Änderung: Juni 2009