Dozent: Dr. Stefan Hougardy
Termine
Beginn der Vorlesung: 18.10.2000| VL | Montag | 11:00 - 13:00 | (RUD 25, 3.101) |
|---|---|---|---|
| Mittwoch | 11:00 - 13:00 | (RUD 25, 3.101) | |
| UE | Mittwoch | 13:00 - 15:00 | (RUD 25, 3.101) |
| PR | n.V. | ||
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
Empfohlene Literatur
- , Graphen und Algorithmen 1
- , Einführung in Graphen und Algorithmen
- , Graphentheorie, Springer Verlag, 2000
- , Introduction to Graph Theory, Prentice Hall, 1996
English