WS 10: VL Matroidtheorie an der TUB

gehalten von Dr. Jácint Szabó (Zuse Institut Berlin)

Ort: MA 542

Zeit: Dienstag, 16.30 Uhr - 18.00 Uhr (Erstes Mal: 19/10)

Sprechstunde: 4/3, 9.30-11.00 Uhr, MA 548.

Mündliches Examen: 8/3, 9.30 Uhr, MA 645.

Oder: Zuse Institut, Raum 3103. Terminverabredung notwendig.

Aufgaben

Zusammenfassung

Die Matroidtheorie bildet in der kombinatorischen Optimierung ein Konzept von zentraler Bedeutung mit einer großen, schönen und sehr interessanten Theorie. Der Begriff des Matroids fasst sehr gut den Aspekt der Unabhängigkeit, der in verschiedenen Formen auftreten kann: unabhängige Vektoren in der linearen Algebra, Bäume in Graphen und submodulare Funktionen. Deshalb findet die Matroidtheorie vielfache Anwendungen in der kombinatorischen Optimierung.

In der Vorlesung werden die grundlegenden Begriffe und (meistens angewandte) Ergebnisse der Matroidtheorie tiefliegend behandelt. Unter anderem werden folgende Themen dargestellt: Matroidpolyeder, submodulare Funktionen, Dilworth Truncation, Matroiddurchschnittssatz, Summe von Matroiden, Representierbarkeit. Die betrachteten Anwendungen umfassen Zusammenhang, Rigidität, Packen und Überdecken mit Bäumen, Matching.

Thematik:

19/10 Unabhängigkeitsaxiome, Kreisaxiome, lineare und graphische Matroide

26/10 Rangaxiome, Abschluss, Basistauschaxiome

2/11 Geometrische Repräsentation, Zusammenhang

9/11 Minoren, Dual

16/11 Gieriger Algorithmus

23/11 Orakel, Matchingmatroide

30/11 Deltoide und Gammoide

8/12 Induziertes Matroid, homomorphes Bild, Summe von Matroiden

14/12 Edmonds Algorithmus für Matroidpartition, Tuttes Satz über disjunkte aufspannende Bäume, Nash-Williams Satz über Baumpackung

4/1 Hypergraphische Matroide, durch eine submodulare Funktion dargestelltes Matroid

18/1 Steifigkeit

25/1 Matroidpolyeder, Linking

1/2 Matroiddurchschnitt

8/2 Gewichteter Matroiddurchschnitt, Repräsentierung

Leistungspunkte: 5

Voraussetzungen: Grundbegriffe der Graphentheorie und Linearen Algebra

Geplante Fortsetzung: keine

Übungen: keine. Einige Hausaufgaben an der Vorlesung, Übungsschein am Ende des Jahres.

Scheinkriterien: keine

Literatur zur Vorlesung:

Oxley, James G.: Matroid theory; Oxford University Press; 1992
Truemper, K.: Matroid decomposition; Academic Press, Inc., Boston; 1992
Welsh, D. J. A: Matroid theory; L.M.S. Monographs. Vol. 8. London - New York - San Francisco: Academic Press; 1976