Vorlesung Graphentheorie
Dozent:
Prof. Dr. R. Schrader
Zeit und Ort: Di und Mi 10 - 11:30 im HS (301) der Pohligstrasse 1.
Vorlesungsbeginn: 16. Oktober 2007
Übungen
Die Vorlesung wird 4-stündig mit
Übungen
(2-stündig) angeboten. Ein Schein kann durch Teilnahme an den Übungen
und eine Abschlussklausur erworben werden.
Inhalt der Vorlesung
Die Graphentheorie hat sich zu einem eigenständigen Gebiet im Schnittpunkt der Kombinatorik und der Informatik entwickelt. Ihre Konzepte und Modelle
werden sowohl unter strukturellen als auch algorithmischen Aspekten anaylsiert. Daneben haben sich die Sprache der Grapentheorie und die von ihr verwandten Techniken in der Modellierung, der Anlayse und der Problemlösung komplexer Systeme bewährt. Die vorlesung soll einen Überblick über die Konzepte, Modelle und Techniken der Graphentheorie geben.
Nach einer kurzen Einführung sollen u.a. folgende Themen behandelt werden:
Matchings, Zusammenhang, Färbungen, planare Graphen, perfekte Graphen, Minoren und Baumzerlegungen.
Die Vorlesung wendet sich an Studierende des Hauptstudiums.
Literatur
| [1] |
Reinhard Diestel. "Graphentheorie". Springer-Verlag, Berlin, 2006.
(Die "Elektronische Ausgabe 2000" ist im pdf-Format in Deutsch und Englisch erhältlich) |
| [2] |
Bernhard Korte und Jens Vygen. "Combinatorial Optimization".
Springer-Verlag, Berlin, 2006. |
| [3] |
László Lovász und Michael D. Plummer. "Matching Theory".
North-Holland Publishing Co., Amsterdam, 1986. |
| [4] |
Alexander Schrijver. "Combinatorial Optimization. Polyhedra and Efficiency. Vol. A/B/C".
Springer-Verlag, Berlin, 2003. |
Skript
- 1. Kapitel PDF (Stand 23.10.07)
- 2. Kapitel PDF (Stand 25.10.07)
- 3. Kapitel PDF (Stand 24.10.07)
- 4. Kapitel PDF (Stand 31.10.07)
- 5. Kapitel PDF (Stand 13.11.07)
- 6. Kapitel PDF (Stand 14.11.07)
- 7. Kapitel PDF (Stand 28.11.07)
- 8. Kapitel PDF (Stand 11.12.07)
- 9. Kapitel PDF (Stand 28.01.08)
- 10. Kapitel PDF (Stand 22.01.08)
- 11. Kapitel PDF (Stand 23.01.08)
Seminar
Im Seminar Ausgewählte Kapitel der Informatik und des Operations Research
werden Artikel zu aktuellen Themen der Algorithmenentwicklung und der Theroretischen Informatik behandelt.
Anmeldung bis 28.9.2007 an
Prof. Dr. R. Schrader
Oberseminar
Im Oberseminar Diskrete Algorithmen und Informatik der Arbeitsgruppe Faigle/Schrader werden in unregelmässiger Reihenfolge Vorträge zu den genannten Themen präsentiert.
Teilnahme ist allen Interessenten offen. Detailliertere Information zum konkreten Programm kann z.B.
über die Leitseite der Arbeitsgruppe (www.zaik.uni-koeln.de/AFS) erworben werden.
