Zur
  Seite der TU

Graphen- und Netzwerkalgorithmen

(ADM I)

Zur Seite des Instituts für Mathematik
 

Sommersemester 2003

 
LV-Nr.: 0230 L 148
 

Prof. Dr. Martin Grötschel
 


Inhalt

Viele praxisrelevante Fragestellungen in Wirtschaft, Technik und in anderen Wissenschaften können als Optimierungsprobleme in Graphen modelliert werden. Beispiele, die in der Vorlesung angesprochen werden, kommen aus den Bereichen Telekommunikation, Produktions- und Verkehrsplanung, Informatik, Biologie und Physik.

In dieser Vorlesung werden grundlegende Algorithmen zur Lösung von Problemen in Graphen behandelt. Unter anderem werden Algorithmen vorgestellt und analysiert, die folgende Fragen beantworten: Wie komme ich möglichst schnell von A nach B, wie pumpe ich möglichst viel Wasser durch ein bestehendes Leitungssystem, wie löse ich das Heiratsproblem?

Es werden dabei relevante Teile der Graphentheorie eingeführt sowie wichtige algorithmische Suchtechniken und Grundprinzipien wie Greedy- oder Augmentierungsverfahren. Mit diesen Methoden können die oben genannten Probleme effizient gelöst werden.

Es gibt (natürlich) auch Graphenprobleme, für die noch keine effektiven Lösungsverfahren bekannt sind. Beispiele hierfür sind das Travelling-Salesman und das Stabile-Mengen-Problem. Aber auch die Aufgabe, ein ausfallsicheres Kommunikationsnetzwerk zu entwerfen, gehört dazu. In der Vorlesung wird gezeigt, wie man mit sogenannten primalen und dualen Heuristiken "gute" Lösungen für derartige Probleme finden kann.

Voraussetzungen:

keine

Geplante Fortsetzung:

Diese Vorlesung ist die Einführungsveranstaltung und Grundvorlesung für den Schwerpunkt "Algorithmische Diskrete Mathematik" in den Studiengängen Mathematik und Techno- und Wirtschaftsmathematik. Im nächsten Semester wird die Reihe durch die Vorlesung Lineare Optimierung fortgesetzt.

Zur Vertiefung der Themen aus der Vorlesung ``Graphen- und Netzwerkalgorithmen'' wird im Wintersemester 2003/2004 ein Seminar über Matchings, Flüsse und Verallgemeinerungen angeboten.


Literatur

R.K. Ahuja, T.L. Magnanti, J.B. Orlin:
Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
Combinatorial Optimization, Wiley, 1998

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein:
Introduction to Algorithms, McGraw-Hill, 1990 (2. Auflage, 2001)

M. Grötschel:
P= NP?,
Elemente der Mathematik, 57 (2002) 96-102

M. Grötschel, L. Lovasz:
Combinatorial Optimization,
in R. L. Graham, M. Grötschel, L. Lovasz: "Handbook of Combinatorics", Band 2,
Amsterdam, North-Holland, 1995, S. 1541-1597

M. Grötschel, M. Padberg:
Die optimierte Odyssee,
Spektrum der Wissenschaft, 4 (1999) 76-85

D. Jungnickel:
Graphs, Networks and Algorithms, Springer, 1999
(englische Übersetzung der deutschen Version aus dem Jahre 1994)

B. Korte, J. Vygen:
Combinatorial Optimization, Theory and Algorithms, Springer, 2000 (2. Auflage, 2002)

A. Schrijver:
Combinatorial Optimization, Springer, 2003

Vorlesungsskriptum  (aktualisierte Version vom 21. August 2003, Kapitel 1 - 12, ps-File, pdf-File)


Kontakte

   
Sprechstunde
Raum Telefon email
Dozent: Prof. Dr. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de
Assistent: Dr. Frank Lutz Do   10:00 - 11:30 Uhr MA 624 314-25 751 lutzmath.tu-berlin.de
Tutoren: Dr. Vanessa Kääb Do   13:30 - 15:00 Uhr MA 613 314-25 735 kaeaebmath.tu-berlin.de
Daniel Schmidt s. Rechnerbetreuung schmidtpool.math.tu-berlin.de
Sekretariat (TU): Elke Pose Mo - Do   9:30 - 11:30 Uhr MA 627 314-23 354 posemath.tu-berlin.de
Sekretariat (ZIB): Bettina Kasse n.V. 3025 84185-209 kassezib.de


Zeiten

Vorlesung: Di 16:00 - 17:30 MA 041 Prof. Dr. Martin Grötschel
Mi 14:15 - 15:45 MA 041
Übung: Do 16:00 - 17:30 MA 043 Dr. Frank Lutz
Tutorien: Mo 12:15 - 13:45 MA 744 Daniel Schmidt
Di 10:05 - 11:35 MA 744 Dr. Vanessa Kääb
Di 12:15 - 13:45 MA 744
Rechnerbetreuung: Mo 10:15 - 11:45 Unix Pool Daniel Schmidt
Mo 16:15 - 17:45 Unix-Pool


Übungsblätter:


Programmieraufgaben:

Die für diesen Kurs zu lösenden Programmieraufgaben sollen in Java unter Benutzung der Graphenklasse (jGABL) implementiert werden.


jGABL für Zuhause:   http://www.math.tu-berlin.de/jGABL.

Beispielgraphen

Beispielprogramme


Hinweise zur Benutzung von jGABL im Unix-Pool

Im Unix-Pool ist die Bibliothek jGABL.jar und die dazugehörende Dokumentation jGABL_doc.jar bereits im Verzeichnis /net/gna/jGABL installiert. Im Verzeichnis /net/gna/examples liegt das Beispielprogramm PrintAdjacencyList.java aus der Übung und unter /net/gna/graphs gibt es Beispielgraphen für die 1. Programmieraufgabe. Das Programm PrintAdjacencyList.java könnt ihr zum Testen bei euch in ein eigenes Verzeichnis schreiben und dort mit

javac -classpath /net/gna/jGABL/jGABL.jar:. PrintAdjacencyList.java

übersetzen und mit

java -classpath /net/gna/jGABL/jGABL.jar:. PrintAdjacencyList /net/gna/graphs/graph_comp.1.gml

z.B. für den Beispielgraphen graph_comp.1.gml ausführen.


Scheinkriterien

50% der Punkte aus den Übungsblättern 1 bis 6 und 50% der Punkte aus den Übungsblättern 7 bis 12 sowie die erfolgreiche Bearbeitung aller Programmieraufgaben. Außerdem wird die aktive Mitarbeit in den Tutorien vorausgesetzt.


Valid HTML 4.0! Zuletzt aktualisiert: 26. Februar 2004