Dozent: Stefan Hougardy
Termine
Beginn der Vorlesung: 18.10.2005.| VL | Dienstag | 15:00 - 17:00 | (RUD 26, 1.306) |
|---|---|---|---|
| Donnerstag | 13:00 - 15:00 | (RUD 26, 1.306) | |
| UE | Donnerstag | 15:00 - 17:00 | (RUD 26, 1.306) |
| PR | semesterbegleitend | Michael Behrisch | |
| Sprechzeit | nach Absprache | (RUD 25, 3.314) Stefan Hougardy |
Zuordnung
- Hauptstudium, Halbkurs oder 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
- wie findet man den kürzesten Weg von einem Ort zu einem anderen?
- wie färbt man eine Landkarte mit möglichst wenigen Farben so, dass benachbarte Länder verschiedene Farben erhalten?
- wie plant man eine Rundreise durch n Städte so, dass die insgesamt zurückgelegte Strecke möglichst kurz wird?
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
- Minimal spannende Bäume
Übungen
Den Stoff der Vorlesung können Sie nur verstehen, wenn Sie sich aktiv damit beschäftigen. Die Übungen werden Sie dabei unterstützen. Jeden Dienstag gibt es ein neues Übungsblatt. Die Lösungen werden in der darauffolgenden Woche am Ende der Vorlesung abgegeben, und gleich besprochen. In der nächsten Woche werden die korrigierten Übungen zurückgegeben, und bei Bedarf können sie dann nochmal besprochen werden.
Um die Prüfungszulassung zu erhalten, benötigen Sie 50% der in den Übungsaufgaben erreichbaren Punkte. Außerdem ist die erfolgreiche Teilnahme am Programmierpraktikum notwendig.
Praktikum
Die Aufgaben des Praktikums finden sich zur gegebenen Zeit in Goya.
Hier werden Ein- und Ausgabeformat erläutert. Eine Graphendatei ist eine Textdatei, deren Inhalt in etwa wie folgt aussieht
(hier die Datei g01.graph):
c C_5 c p 5 5 e 1 5 33 e 4 5 15 e 3 4 8 e 2 3 18 e 1 2 21
Die mit c beginnenden Zeilen sind Kommentare, es folgt eine mit "p" beginnende Zeile, die Knoten und Kantenzahl des Graphen vorgibt,
anschließend die Kanten in der Form e 1.Knoten 2.Knoten Gewicht. Die Knoten sind fortlaufend, von 1 beginnend, nummeriert, die
Kantengewichte sind ganze nicht negative Zahlen und können auch fehlen (was dem Kantengewicht 1 entsprechen soll). Eventuelle in der Datei vorkommende Leerzeilen sind zu
ignorieren. Fehleingaben müssen nicht abgefangen werden, d.h., Graphen, die nicht dieser Spezifikation entsprechen,
dürfen das Programm abstürzen lassen. Die Anzahl der Knoten liegt bei maximal 10000, die Summe der Kantengewichte
in einem Graph überschreitet nie 2^30. Bitte achten sie auf genaue Einhaltung der Laufzeitbeschränkungen
(auch für das Einlesen des Graphen) und auf etwaige Randfälle (leerer Graph).
Der Aufruf der Programme sollte bei C und C++ in der Form graphalg < g01.graph erfolgen, bei Java in der Form
java GraphAlg < g01.graph, wobei der Programmname bzw. Klassenname natürlich frei wählbar ist.
< bezeichnet hierbei eine Eingabeumleitung, d.h. der Graph wird von der Standardeingabe (stdin bzw. System.in)
gelesen. Die Ausgabe erfolgt in jedem Fall auf die Standardausgabe (stdout bzw. System.out).
Das Programm sollte nach dem Aufruf keine Eingabe mehr verlangen,
sondern direkt das Ergebnis liefern. Da die Lösung der Aufgabe immer aus einer Zahl
oder einem booleschen Wert besteht, ist auch nur diese(r) auszugeben
(bei mehreren Teilaufgaben durch Zeilenvorschübe getrennt). Beispiel:
ich@computer> java Aufgabe29 < g01.graph true false true false
Der abgegebene Quelltext sollte gut dokumentiert sein. Bitte verwenden Sie für Methoden, Klassen und Variablen selbstsprechende Namen und nehmen Einrückungen nur mit Leerzeichen vor.
Beispielgraphen und Anmerkungen zu den einzelnen Aufgaben
Literatur
- , Graphen und Algorithmen 1 (Link funktioniert nur von Rechnern des Instituts für Informatik)
- , Einführung in Graphen und Algorithmen
- , Graphentheorie, Springer Verlag, 2000
- , Introduction to Graph Theory, Prentice Hall, 1996
English