Dozenten: Stefan Hougardy und Mathias Schacht
Termine
Beginn der Vorlesung: 18.10.2006.| VL | Mittwoch | 9:00 - 11:00 | (RUD 26, 0'313) |
|---|---|---|---|
| Freitag | 9:00 - 11:00 | (RUD 26, 0'313) | |
| UE | Mittwoch | 11:00 - 13:00 | (RUD 26, 0'313) S. Kirchner |
| PR | Freitag | 11:00 - 13:00 | (RUD 26, 0'313) M. Zelke |
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
Wöchentlich werden Übungsaufgaben ausgegeben, die dazu dienen, sich intensiver mit dem Stoff der Vorlesung auseinander zu setzen. 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 ab sofort in Goya.
Im Folgenden werden Ein- und Ausgabeformat erläutert. Eine Graphendatei ist eine Textdatei, deren Inhalt in etwa wie folgt aussieht (hier die Datei g02.graph):
c C_6 c p 6 6 e 1 6 45 e 5 6 18 e 4 5 38 e 3 4 16 e 2 3 34 e 1 2 42
Die mit c beginnenden Zeilen sind Kommentare, die aus beliebigen Zeichenketten bestehen können, beispielsweise ist im Beispiel noch angegeben, dass es sich bei dem Graphen um einen C_6 handelt, einen Kreis auf 6 Knoten. Allerdings können Kommentarzeilen auch komplett fehlen. Es folgt eine mit p beginnende Zeile, die Knoten und Kantenzahl des Graphen angibt. Diese Zeile existiert auf jeden Fall. Es schließen sich die Angaben zu den Kanten des Graphen an. Jede Zeile der Form e 1.Knoten 2.Knoten Gewicht gibt eine Kante vom Gewicht Gewicht zwischen den Knoten 1.Knoten und 2.Knoten an. Die Kantengewichte sind ganze nicht negative Zahlen, deren Summe im Graphen niemals 2^30 überschreitet.
Die Knoten sind fortlaufend, von 1 beginnend, nummeriert, ihre Anzahl wird 2^30 nicht übersteigen. Eventuelle in der Datei vorkommende Leerzeilen sind zu ignorieren. Fehleingaben müssen nicht abgefangen werden, d.h., Graphendateien, die nicht dieser Spezifikation entsprechen, dürfen das Programm abstürzen lassen.
Bitte achten Sie auf genaue Einhaltung der Laufzeitbeschränkungen (auch für das Einlesen des Graphen) und auf etwaige Randfälle (Graph, der nur aus einem Knoten besteht).
Der Aufruf der Programme sollte in der Form java MeinProgramm g01.graph erfolgen, wobei der Programmname bzw. Klassenname natürlich frei wählbar ist. Das Programm sollte nach dem Aufruf keine Eingabe mehr verlangen,
sondern direkt das Ergebnis auf die Standardausgabe (System.out) liefern.
Da die Lösung der Aufgabe immer aus einer Zahl
oder einem booleschen Wert besteht, ist auch nur diese(r) auszugeben. Beispiel:
ich@computer> java MeinKruskal g02.graph 148 ich@computer> java MeinBipartit g02.graph true
Der abgegebene Quelltext sollte gut dokumentiert und strukturiert sein. Bitte verwenden Sie für Methoden, Klassen und Variablen selbstsprechende Namen und nehmen Einrückungen nur mit Leerzeichen vor.
Beispielgraphen
(mit Lösungen, diese allerdings ohne Gewähr!)Bei Fragen bezüglich des Praktikums wenden Sie sich sich per Mail an Mariano Zelke
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