Algorithms and Complexity - Main page Algorithms and Complexity

Vorlesung: Graphen und Algorithmen 1

Dozent: Mathias Schacht

Termine

Beginn der Vorlesung: 15.10.2008.
VL Mittwoch 9:30 - 11:00 (RUD 26, 0'313)
Freitag 9:30 - 11:00 (RUD 26, 0'313)
UE Freitag 11:00 - 13:00 (RUD 26, 0'313) H. Han und Y. Person
PR 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:

Petersen-Graph ein Baum-Graph Heawood-Graph
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

Themenübersicht

  • 15.10.-31.10.: Kapitel 1 (Hougardy) und Cayleys Formel
  • 05.11.-19.11.: Kapitel 2 (Hougardy) kürzeste Wege, amortisierte Analyse, Fibonacci-Heaps
  • 21.11.-28.11.: Kapitel 3 (3.1-3.3, Hougardy) MST, Kruskal, Prim, Matroide
  • 03.12.-17.12.: Kapitel 4 (ohne 4.7, Hougardy) Flüsse, Zusammenhang
  • 20.12.-16.01.: Kapitel 5 (Hougardy) Matchings in bipartiten Graphen, Sätze von Hall, König, Berge und Tutte
  • 21.01.-23.01.: Kapitel 6 (Hougardy) und Kapitel 18 (Bondy-Murty); Eulertouren, Hamiltonkreise, toughe/robuste Graphen, TSP
  • 27.01.-06.02.: Kapitel 7 (ohne 7.8 und 7.9, Hougardy) Färbungen
  • 11.02.-13.02.: Kapitel 8 (Hougardy) planare Graphen

Übungen

Leiter: Hiep Han und Yury Person

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 Übungs- und Praktikumsaufgaben erreichbaren Punkte. Die Übungsblätter können in Zweiergruppen bearbeitet werden.

Praktikum

Leiter: Mariano Zelke

Die Aufgaben des Praktikums finden sich ab sofort in Goya und hier.

Im Folgenden werden Ein- und Ausgabeformat erläutert. Eine Graphendatei ist eine Textdatei, deren Inhalt folgende Form hat (hier die Datei g01.graph):

c Das ist ein Kommentar
c
p 8 13
e 1 2 4
e 1 3 2
e 1 4 3
e 2 4 1
e 2 3 5
e 3 4 6
e 5 6 4
e 5 7 2
e 5 8 3
e 6 8 1
e 6 7 5
e 7 8 6
e 4 5 -14

Die mit c beginnenden Zeilen sind Kommentare, die aus beliebigen Zeichenketten bestehen können. 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 u v w gibt eine Kante vom Gewicht w zwischen den Knoten u und v an. Ist der Graph als gerichteter Graph zu interpretieren, so bezeichnet die Zeile die Kante von u nach v mit Gewicht w. Der Eingabegraph enthält weder Multikanten noch Schleifen. Die Kantengewichte sind Elemente der ganzen Zahlen. Das Gesamtgewicht jeder Teilmenge der Kanten liegt zwischen -(2^30) und 2^30. 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 [Eingabedatei]

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 besteht, ist auch nur diese auszugeben, siehe dazu die folgenden Beispiele.

Für die erste Aufgabe ist die Eingabe als gewichteter und ungerichteter Graph zu betrachten. Ist der Graph unzusammenhängend, kann Ihr Programm beliebig reagieren, andernfalls ist das Gewicht eines minimal spannenden Baumes zu berechnen. Dieses Gewicht kann aufgrund der Kanten negativen Gewichtes im Graphen auch selbst negatives Gewicht haben. Für den Beispielgraphen g01.graph ergibt sich:

ich@computer> java MeinMST g01.graph
-2
Für die zweite Aufgabe ist die Eingabe als gewichteter und gerichteter Graph aufzufassen. Ist der Graph nicht azyklisch, so ist eine -1 auszugeben, ansonsten die Länge eines längsten gerichteten Pfades. 
ich@computer> java MeinLaengsterGewichteterPfad g01.graph
16
Die dritte Aufgabe verlangt die Ausgabe der minimalen Anzahl von Kanten (nicht die Kanten selber!), die in den Eingabegraphen eingefügt werden müssen, um ihn 2-zusammenhängend zu machen. Die angegebenen Kantengewichte spielen hier keine Rolle, auch die Kantenorientierungen sind bedeutungslos. 
ich@computer> java MeineAufgabe3 g01.graph
1

Der abgegebene Quelltext sollte gut dokumentiert und strukturiert sein. Bitte verwenden Sie für Methoden, Klassen und Variablen selbstsprechende Namen und nehmen Sie 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

last modified 09/23/09 (alkox-www)