Dozent: Amin Coja-Oghlan
Termine
Beginn der Vorlesung: 23.10.2003| VL | Dienstag | 09:00 - 11:00 | (RUD 26, 1.307) |
|---|---|---|---|
| Donnerstag | 09:00 - 11:00 | (RUD 26, 1.307) | |
| UE | Dienstag | 11:00 - 13:00 | (RUD 26, 1.307) |
| PR | n.V. | Martin Thimm | |
| Sprechzeit | Dienstag | 12:30 - 13:30 | (RUD 25, 3.415) |
Zuordnung
- Hauptstudium, 1. Teil eines Kurses
- Theoretische Informatik
Inhalte und Lernziele
Ein Graph besteht aus einer Menge von Knoten, von denen einige durch Kanten verbunden sind. Hier sind Beispiele für Graphen:
 |
 |
 |
| Der "Petersen Graph" | Ein Baum | Der "Heawood Graph" |
Mit Hilfe dieser relativ einfachen Struktur lassen sich viele fundamentale Probleme modellieren und mittels geeigneter Graphenalgorithmen auch effizient lösen, wie beispielsweise
- was ist die kürzeste/schnellste Verbindung von einem Ort zu einem anderen (Routenplaner)?
- wie packt man 3 Millionen Transistoren so auf einen Chip, daß die Gesamtleitungslänge möglichst gering bleibt (Chipdesign)?
- wieviele Telefongespräche können gleichzeitig über super24 von Berlin nach Bonn geführt werden?
- was ist die effizienteste Art multicasting im Internet durchzuführen?
- lassen sich die Länder einer Landkarte so mit 4 Farben färben, daß benachbarte Länder nie die gleiche Farbe erhalten (4-Farben-Satz)?
- ...
Besonders interessant ist die Art und Weise, in der algorithmische Probleme strukturelle Fragen über Graphen aufwerfen, deren Beantwortung dann zu verbesserten Algorithmen führt.
Folgende Themen sollen im Wintersemester behandelt werden:- Grundlagen
- Zusammenhang
- Flüsse
- Matchings
- Eulersche/Hamiltonsche Graphen
- Das Traveling-Salesman-Problem
- Färbungen
- Planarität
- Steinerbäume
Übungen
Lösung zu Aufgabe 3, Serie 5Programmierpraktikum
AufgabenblattEmpfohlene Literatur
- , Graphen und Algorithmen 1
- , Einführung in Graphen und Algorithmen
- , Graphentheorie, Springer Verlag, 2000
- , Introduction to Graph Theory, Prentice Hall, 1996
English