Graphenalgorithmen WS 07/08

	Dr. Sigrid Knust, Christian Viergutz
	Graphenalgorithmen WS 07/08

Inhalt:

Graphen gehören zu den wichtigsten Modellen der Informatik die zahlreiche praktische Anwendungen haben (z.B. im Verkehrs- und Telekommunikationsbereich, der Produktionsplanung oder allgemein bei vielen kombinatorischen Optimierungsproblemen).

Nach einer Einführung in die Grundbegriffe der Graphentheorie sollen Suchverfahren, Zusammenhangs-Probleme, Bäume, Kürzeste Wege, Matching- und Routing-Probleme, Knoten- und Kantenfärbungen behandelt werden. Dabei steht die Entwicklung von effizienten Lösungsverfahren im Vordergrund. In den Übungen sollen einige Algorithmen auch praktisch implementiert werden.

Termine:

Vorlesung: Sigrid Knust

Tag Zeit Raum

Mo 10:15-11:45 31/E05

Mi 12:15-13:45 31/E05
Übung: Christian Viergutz

Tag Zeit Raum

Di 10:15-11:45 69/E18

Mi 14:15-15:45 69/E18
Klausur:

Tag Zeit Raum

4.2.08 10:00-12:00 31/E06

Übungsblätter :

Nr.	Abgabe	Inhalt
1	25.10.07	Eigenschaften unger. Graphen, chromatische(r) Zahl/Index, Spielgraphen (GEO)
2	01.11.07	Domino-Spiel, Kantengraph, spezielle Knoten- bzw. Kantenteilmengen
3	08.11.07	Graphenrepräsentationen, Heaps, Implementation von Graphenstrukturen
4	15.11.07	Suchverfahren für Graphen, Transitive(r) Abschluss/Reduktion, Implementierung Tiefensuche Graphen zu Programmieraufgabe P2
5	22.11.07	Modellierung Würfelspiel, Einseitiger Zusammenhang, Wege und Artikulationspunkte
6	29.11.07	Knoten- und Kantenzusammenhang in ungerichteten Graphen, Strukturgraph, Schiebepuzzle
7	06.12.07	Minimale Spannbäume, Algorithmus von Prim Graphen zu Programmieraufgabe P4 (korr. am 3.12.), Erläuterung zum Dateiformat
8	13.12.07	Kürzeste Wege, Bellmannsche Gleichungen, Zuverlässigste Verbindungen, Implementierung Dijkstra Graphen zu Programmieraufgabe P5
9	20.12.07	Wege maximaler Kapazität, Durchlaufzeiten, Wegezählung, Implementierung Bellmann-Ford & Floyd Graphen zu Programmieraufgabe P6
10	10.01.08	Matchings, Zuordnungsprobleme, Klausuraufgabe
11	17.01.08	Hamiltonsche Graphen, Problem des chin. Postboten, TSP mit Zeitfenstern
12	24.01.08	Heuristiken für das TSP, Färbungsprobleme Graphen zu Programmieraufgabe P7

Material aus den Übungen:

Nr.	Datum	PDF	Inhalt
1	16.10.07		Folien aus der ersten Präsenzübung

Material zur Vorlesung :

Literatur :

R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993
J.M. Aldous, R.J. Wilson: Graphs and applications, Springer, 2003
R. Diestel: Graphentheorie, Springer, 2000
J. Gross, J. Yellen: Graph theory and its applications, CRC Press, 1999
J. Gross, J. Yellen: Handbook of graph theory, CRC Press, 2004
D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI-Verlag, 1987
R. Sedgewick: Algorithms, Addison Wesley, 1988
V. Turau: Algorithmische Graphentheorie, Oldenbourg, 2004

Teilnahme :

Teilnehmen können alle interessierten Studierende aus den Studiengängen Mathematik/Informatik, Angewandte Systemwissenschaft, Cognitive Science.

Schein :

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der Übungsaufgaben (jeweils 50% der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche Absolvierung einer Klausur am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.

Weblinks :

Last update: 14.01.2008 (SK/CV)