Lehrinhalte
Graphen und Digraphen: bipartite Graphen, Netzwerke, Zusammenhang, Bäume, Graphensuche.
Lineare Programme: Struktur, Modellierung, Transformation auf Standardform, Basen primale und duale Zulässigkeit, ökonomische Interpretation (Schattenpreise)
Simplex-Verfahren: Grundversion/Tableaux und geometrische Interpretation Dualitätstheorie, komplementärer Schlupf
Polynomiale Algorithmen für Basisprobleme in Netzwerken: aufspannende Bäume, kürzeste Wege, maximale Flüsse, Minimalkostenflüsse
Komplexitätstheorie: Die Klassen P und NP, NP-Vollständigkeit.
NP-schwere Probleme: Cliquen-, Travelling Salesman-, Maximalschnitt- und Färbungsprobleme.