Algorithmen und Komplexität

Vorlesung: Graphen und Algorithmen 1

Dozent: Prof. Hans Jürgen Prömel

---

Termine

Beginn der Vorlesung: 20.10.1999
Beginn der Übung: 27.10.1999

VL	Montag	11:00 - 13:00	(RUD 25, 3.101)
	Mittwoch	13:00 - 15:00	(RUD 25, 3.101)
UE	Mittwoch	11:00 - 13:00	(RUD 25, 4.111) Dr. A. Taraz
PR	Montag	9:00 - 11:00	(RUD 25, 4.111) Dr. A. Taraz

Im Sommersemester 2000 folgt "Graphen und Algorithmen 2".

Zuordnung

• Hauptstudium, 1. Teil eines Kurses
• Theoretische Informatik

Inhalte und Lernziele

Ein Graph besteht aus einer Menge von Knoten, von denen einige durch sogenannte Kanten verbunden sind. Mit Hilfe dieser relativ einfachen Struktur lassen sich elementare Fragen der Informatik wie beispielsweise

• gibt es einen Weg durch eine Stadt, der jede Straße (oder jede Kreuzung) genau einmal benutzt?
• kann ich eine Menge von Prozessoren so durch Leiterbahnen verbinden, daß letztere sich nicht kreuzen?
• unter welchen Bedingungen kann ich innerhalb einer Gruppe von Leuten jedem genau einen anderen Partner zugeordnen, den er kennt?
• lassen sich die Länder einer Landkarte so mit 4 Farben färben, daß benachbarte Länder nie die gleiche Farbe erhalten?

in eleganter Weise formulieren und lösen. Besonders interessant ist die Art und Weise, in der algorithmische Probleme hier theoretische Fragen aufwerfen, deren Beantwortung dann wieder zu verbesserten Algorithmen führt.

Neben den Übungen findet zu diesem Kurs ein begleitendes Programmierpraktikum statt, in dem die Implementation von Graphenalgorithmen geübt wird.

Übungen

Leiter: Dr. A. Taraz

• Übungsblatt 1: Aufgaben 1 - 4
• Übungsblatt 2: Aufgaben 5 - 8
• Übungsblatt 3: Aufgaben 9 - 12
• Übungsblatt 4: Aufgaben 13 - 16
• Übungsblatt 5: Aufgaben 17 - 20 (und Lösung zu Aufgabe 12)
• Übungsblatt 6: Aufgaben 21 - 24
• Übungsblatt 7: Aufgaben 25 - 26
• Übungsblatt 8: Aufgaben 27 - 30
• Übungsblatt 9: Aufgaben 31 - 34
• Übungsblatt 10: Aufgaben 35 - 38
• Übungsblatt 11: Aufgaben 39 - 42
• Übungsblatt 12: Aufgaben 43 - 46
• Übungsblatt 13: Aufgaben 47 - 50
• Übungsblatt 14: Aufgaben 51 - 54

Programmierpraktikum

Betreuer: Dr. A. Taraz

• Aufgabenblatt
• BFS, DFS, Prim, Dijkstra
• Maximales Matching, Baum Matching
• Augmentiere bipartites Matching, Bipartites Matching, Hopcroft Karp
• Maximales gewichtetes bipartites Matching
• Euler und Hamilton
• Nearest-neighbor- und MST-Heuristik, Christofides

Empfohlene Literatur

• Bollobas, Modern Graph Theory, Springer
• Cormen, Leiserson, Rivest, Introduction to algorithms, MIT Press, 1990
• Diestel, Graphentheorie, Springer Verlag, 2000
• Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996

---

zuletzt geändert am 22.01.2006 (alkox-www)