Forschungsinstitut für Diskrete Mathematik

Vorlesung
"Einführung in die Diskrete Mathematik"

Wintersemester 2012/13

Diese Vorlesung eignet sich für das 3. Semester im Rahmen des Bachelorstudiengangs Mathematik und ist als Einstieg in den Bereich C (Diskrete Mathematik) gedacht. Ferner kann die Vorlesung im Rahmen der Studiengänge Informatik besucht werden. Nähere Informationen finden sich unter http://www.or.uni-bonn.de/teaching.de.html.

In dieser Vorlesung werden grundlegende Themen der diskreten Mathematik behandelt. Der Schwerpunkt liegt dabei auf Netzwerkproblemen. Nach einer kurzen Einführung in Graphen und elementare Algorithmen werden die Themen Bäume, Branchings, Netzwerkflüsse, minimale Schnitte, Zusammenhang, kostenminimale Flüsse, Anwendungen von Netzwerkflüssen, bipartites Matching, Multicommodity flows und disjunkte Wege sowie NP-Vollständigkeit behandelt.

Die Vorlesung findet in deutscher Sprache statt und basiert zum großen Teil auf folgendem Buch:

• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer. Fifth edition, 2012

Weitere empfehlenswerte Bücher für Teile der Vorlesung:

• R. Diestel: Graphentheorie. Springer. Vierte Auflage, 2010
• R. Ahuja, T. Magnanti, J. Orlin: Network Flows. Prentice-Hall, 1993
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. McGraw-Hill. Third edition, 2009
• D. Jungnickel: Graphs, Networks and Algorithms. Springer. Third edition, 2007
• W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver: Combinatorial Optimization. Wiley, 1997
• A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003

Zeit:	Dienstags und donnerstags 16-18 Uhr (c.t.)
Ort:	Gerhard-Konow-Hörsaal, Lennéstr. 2
Übungen:	2st, n.V.