Forschungsinstitut für Diskrete Mathematik

Vorlesung "Einführung in die Diskrete Mathematik"

Wintersemester 2007/08

Prof. Dr. S. Hougardy

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 Netzwerkalgorithmen werden die Themen Branchings, Netzwerkflüsse, minimale Schnitte, Zusammenhang, kostenminimale Flüsse, Anwendungen von Flüssen in Netzwerken, bipartites Matching, Multicommodity flows und disjunkte Wege behandelt.

Die Vorlesung wird zum großen Teil auf folgendem Buch basieren:

• B. Korte, J. Vygen : Combinatorial Optimization: Theory and Algorithms. Springer, Dritte Auflage 2006

• 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 2002
• A. Schrijver : Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003
• D. Jungnickel : Graphs, Networks and Algorithms. Springer 1999
• W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver : Combinatorial Optimization. Wiley 1997