Vorlesung Graphentheoretische Methoden und Algorithmen (SS 2001)

• Inhalt der Vorlesung
• Literatur
• Termine und Ort
• Übungen - Organisatorisches
• Übungsblätter zum Download

Inhalt der Vorlesung

1. Einleitung (Das Königsberger Brückenproblem - Das Haus vom Nikolaus - Labyrinth - Literatur - Organisation)
2. Grundbegriffe (Gerichtete Graphen - Teilgraphen und Obergraphen - Ungerichtete Graphen - Speicherung von Graphen)
3. Wege, Kreise und Zusammenhang (Wege - Zusammenhang - Der Satz von Euler - Hamiltonsche Kreise)
4. Bestimmung von Zusammenhangskomponenten (Transitive Hülle und irreduzible Kerne - Der Tripelalgorithmus - Der Reduzierte Graph - Irreduzible Kerne)
5. Bäume, Wälder und Matroide (Bäume und Wälder - Minimal spannende Bäume - Steinerbäume und andere Dilemmas - Spannende Wurzelbäume in gerichteten Graphen)
6. Suchstrategien (Untersuchung von Graphen mit Tiefensuche - Anwendungen von DFS - Tiefensuche für ungerichtete Graphen - Breitensuche)
7. Bestimmung kürzester Wege (Kürzeste Wege - Kürzeste-Wege-Bäume - Der Algorithmus von Dijkstra - Der Algorithmus von Bellman und Ford - Die Bellmannschen Gleichungen und kreisfreie Graphen - Längste Wege)
8. Flüsse (Strömungen und Schnitte - Zulässige und maximale Strömungen - Das Max-Flow-Min-Cut Theorem - Der Algorithmus von Ford und Fulkerson - Kombinatorische Anwendungen - Kostenminimale Strömungen)
9. Planare Graphen (Einbettungen - Die Eulersche Polyederformel - Triangulationen - Grade in planaren Graphen - Kriterien für Planarität)
10. Graphtransformationen (Tripeldarstellung von Graphen - Homomorphismen - Das Graphenisomorphieproblem - Automorphismen - Ähnlichkeit von Graphen - Edit-Operationen - Graph-Grammatiken)

Literatur und Skript

• R. Diestel. Graphentheorie. Springer, 1997.
• R.K. Ahuja, T.L. Magnanti, B. Orlin Network Flows . Prentice Hall, 1993
• T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, 1990.
• S. Even. Graph Algorithms. Computer Science Pr., 1979.
• E. Lawler. Combinatorial  Optimization: Networks and Matroids . Holt, Rinehart & Winston 1976.
• H. Noltemeier. Graphentheorie: mit Algorithmen und Anwendungen. de Gruyter Lehrbuch, 1975.
• C. Berge. Graphs and Hypergraphs. North Holland Publ., 1973.
• F. Harary. Graph Theory. Addison-Wesley-Publishing Company, Inc., 1973.

Termine und Ort

• Zugelassen sind alle Vorlesungsteilnehmer, die in den Übungen zusammen mindestens 40 % der maximal erreichbaren Punktesumme erreicht haben. Eine Liste der zugelassenen Teilnehmer liegt nach der Korrektur des letzten Übungsblattes bei Ingo Demgensky aus (Zimmer E33).
• Bei der Klausur sind außer Schreibzeug keine weiteren Hilfsmittel zugelassen.
• Bitte bringen Sie einen Lichtbildausweis zur Klausur mit.

Hinweise zum Semesterende:

• Die Besprechung der Klausurergebnisse findet zu den normalen Übungszeiten am Freitag, 20. Juli, und am Montag, 23. Juli, statt.
• Die Scheine werden am Mittwoch, 25. Juli, nach der Vorlesung ausgegeben.
• Eine Liste der Teilnehmer, die die Klausur bestanden haben und somit einen Übungsschein erhalten, ist am schwarzen Brett ausgehängt. Für die übrigen Teilnehmer besteht die Möglichkeit einer mündlichen Nachprüfung; Näheres auf Anfrage.

Übungen - Organisatorisches

• Die Anmeldung zu den Übungen erfolgte in der Vorlesung. Nachmeldungen bitte an Ingo Demgensky.
• Die Einteilung in die Übungsgruppen entnehmen Sie bitte den Aushängen am schwarzen Brett.
• Bis zu zwei Übungsteilnehmer dürfen gemeinsam ein Übungsblatt abgeben.
• Voraussetzung für die Zulassung zur Klausur ist das Erreichen einer Punktesumme von 40% der insgesamt in den Übungen erreichbaren regulären Punkte

• Dipl.-Inform. Ingo Demgensky (Zimmer E33, Telefon 888-4943)
• Dipl.-Inform. Hans-Christoph Wirth (Zimmer E14, Telefon 888-5058)
• cand. Inform. Sven Fuhrmann

Übungsblätter zum Download

Übungsblatt	Download
1. Blatt vom 02.05.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
2. Blatt vom 09.05.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
3. Blatt vom 16.05.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
4. Blatt vom 23.05.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
5. Blatt vom 30.05.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
6. Blatt vom 13.06.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
7. Blatt vom 20.06.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
8. Blatt vom 27.06.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)
9. Blatt vom 04.07.01	Aufgaben (Postscript) (PDF)	Aufgaben mit Lösungen (Postscript) (PDF)

Es werden keine weiteren Übungsblätter ausgegeben.