Graphentheoretische Konzepte und Algorithmen (SS 1997)

Die Vorlesung bietet eine Einführung in die Theorie der gerichteten und ungerichteten Graphen. Darüberhinaus behandelt die Vorlesung den graphentheoretisch formulierbaren Teil der Kombinatorischen Optimierung, wobei der Schwerpunkt auf der Darstellung effizienter Algorithmen liegt.

Voraussichtlicher Inhalt der Vorlesung

1. Einleitung

1.1 Das Königsberger Brückenproblem
1.2 Das Haus vom Nikolaus
1.3 Labyrinth
1.4 Literatur
1.5 Organisation
2. Grundbegriffe

2.1 Gerichtete Graphen
2.2 Teilgraphen und Obergraphen
2.3 Ungerichtete Graphen
2.4 Speicherung von Graphen
3. Wege, Kreise und Zusammenhang

3.1 Wege
3.2 Zusammenhang
3.3 Der Satz von Euler
3.4 Hamiltonsche Kreise
4. Bestimmung von Zusammenhangskomponenten

4.1 Transitive Hülle und irreduzible Kerne
4.2 Der Tripelalgorithmus
4.3 Der Reduzierte Graph
4.4. Irreduzible Kerne
5. Bäume, Wälder und Matroide

5.1 Bäme und Wälder
5.2 Minimal spannende Bäume
5.3 Steinerbäume und andere Dilemmas
5.4 Spannende Wurzbelbäume in gerichteten Graphen
6. Tiefensuche (Depth-First Search)
7. Bestimmung von Wegen
8. Flüsse

7.1 Strömungen, Schnitte und Potentiale
7.2 Der Algorithmus von Ford und Fulkerson
7.3 Das Max-Flow-Min-Cut Theorem
7.4 Kombinatorische Anwendungen
9. Homomorphismen
10. Planare Graphen

Literatur

Die Notationen der Vorlesung sowie der Aufbau sind weitgehend [1] entnommen. Das Buch von Jungnickel [2] behandelt ebenfalls im wesentlichen die gleichen Themengebiete. Aus [3] stammen die Notationen f¨er ungerichtete Graphen.

Das Buch von Harary [4] ist ein "Klassiker" der Graphentheorie. Es behandelt aber mehr die strukturelle als die algorithmische Graphentheorie.

Im Buch von Cormen et al. [5] findet sich neben den zahlreichen Informationen zu allgemeinen Datenstrukturen und Algorithmen ebenfalls ein Kapitel über Graphenalgorithmen.

Als weiterführende Literatur im Bereich der NP-Vollständigkeit möchte ich auf [6] verweisen.

[1] H. Noltemeier. Graphentheorie: mit Algorithmen und Anwendungen. de Gruyter Lehrbuch, 1975.
[2] D. Jungnickel. Graphen, Netzwerke und Algoriithmen. BI-Wissenschaftsverlag, 2. Auflage, 1990.
[3] L. Volkmann. Graphen und Digraphen. Springer Verlag, Wien - New York, 1991.
[4] F. Harary. Graph Theory. Addison-Wesley-Publishing Company, Inc., 1973.
[5] T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, 1990.
[6] M.R. Garey and D.S. Johnson. Computers and Intractability (A guide to the theory of NP-completeness). W.H. Freeman and Company, New York, 1979.

Übungsblätter

1. Übungsblatt Ausgabe: 14. Mai Abgabe: bis 21. Mai Musterlösung
2. Übungsblatt Ausgabe: 21. Mai Abgabe: bis 28. Mai Musterlösung
3. Übungsblatt Ausgabe: 28. Mai Abgabe: bis 4. Juni
4. Übungsblatt Ausgabe: 4. Juni Abgabe: bis 11. Juni
5. Übungsblatt Ausgabe: 11. Juni Abgabe: bis 18. Juni
6. Übungsblatt Ausgabe: 18. Juni Abgabe: bis 25. Juni
7. Übungsblatt Ausgabe: 25. Juni Abgabe: bis 2. Juli
8. Übungsblatt Ausgabe: 2. Juli Abgabe: bis 9. Juli

Errata zur Vorlesung

Errata als Postscript Datei (Letzte Aktualisierung: 18. Juni)

Skript zur Vorlesung

Hier ist das vorläfige Skript endlich! Über Verbesserungsvorschläge würde ich mich freuen.

Kommentare zur Vorlesung und zu den Übungen

Über Kommentare und Verbesserungsvorschläge zur Vorlesung oder den Übungen freue ich mich jederzeit.