1. Mittwoch, 9. April 2014 (pdf)
TEIL I: KOMBINATORISCHE GRAPHEN-ALGORITHMEN
Kapitel 1 Einführung: Stabile Matchings
1.1 Grundbegriffe
Def: Matching
Interpretation als Massenhochzeit
Def: Stabiles Matching
Naiver Algorithmus mit Laufzeit n!
Algorithmus
Beispiel
Satz: Gale-Shapley Algorithmus berechnet stabiles Matching. Insbesondere gibt es immer eines.
2. Freitag, 11. April 2014 (pdf)
Bem: Nur $n^2$ Heiratsanträge im Gale-Shapley Algorithmus.
Satz: Der Gale-Shapley Algorithmus berechnet das für die Männer beste stabile Matching
1.3 Geometrische Modellierung
Vor- und Nachteile kombinatorischer Algorithmen
Vor- und Nachteile geometrischer Modellierung mit linearen Ungleichungen
Codierung von stabilen Matchings mit Hilfe von Permutationsmatrizen
Satz: Charakterisierung von stabilen Matchings mit linearen Ungleichungen
Ausblick: Lineare Optimierung über das Stabile Matching Polytop
Kapitel 2 Kürzeste Wege
2.1 Nichtnegative Kantenlängen
Notation: gerichteter Graph, Knoten, gerichtete Kanten, Kantenlängen, Kantenfolge,
s-t-Weg, Abstand, s-t-Schnitt
Satz: min-max Charakterisierung kürzester Weg
3. Mittwoch, 16. April 2014 (pdf)
Satz: min-max Charakterisierung kürzester Weg
2.2 Beliebige Kantenlängen
Bsp: Rucksackproblem
Algorithmus von Bellman-Ford
Satz: $d_k($v$) = \min\{l(P) : P$ ist s-v-Kantenfolge mit $\leq k$ Kanten$\}$
Def: gerichteter Kreis
Satz: Existenz kürzester s-t-Kantenfolgen, die Wege sind, falls Graph keine Kreise negativer Länge enthält
4. Mittwoch, 23. April 2014 (pdf)
Bemerkungen zu Algorithmus von Bellman-Ford
Satz: $d_n = d_{n-1}$ genau dann, wenn alle von s aus erreichbaren gerichteten Kreise nicht-negative Länge haben
2.3 Geometrische Modellierung, Potentiale
Def: Potential
Satz: Es existiert ein Potential genau dann, wenn alle gerichteten Kreise nicht-negative Länge haben
Satz: geometrische Modellierung kürzester Wege mit linearen Ungleichungen
Kapitel 3 Matchings in bipartiten Graphen
3.1 Definitionen
gerichteter Graph, Knoten, Kanten, Kantenfolge, Weg, Kreis, Nachbar, wegzusammenhängend, Zusammenhangskomponente, zusammenhängend, bipartit
5. Freitag, 25. April 2014 (pdf)
3.2 Matchings mit maximaler Kardinalität
3.2 Matchings mit maximaler Kardinalität
Def: M-augmentierender Weg
Satz: Entweder ist M Matching mit maximaler Kardinalität oder es gibt einen M-augmentierenden Weg
Algorithmus zur Bestimmung eines Matchings mit maximaler Kardinalität
Algorithmus zur Bestimmung eines Matchings mit maximaler Kardinalität
Residualgraph zur Bestimmung eines M-augmentierenden Wegs in bipartiteten Graphen
3.3 Das Matching Theorem von König
Def: Knotenüberdeckung
Satz: Sei G bipartiter Graph, dann ist die maximale Kardinalität eines Matchings in G gleich der minimalen Kardinalität einer Knotenüberdeckung in G
6. Mittwoch, 30. April 2014 (pdf)
3.4 Matchings mit maximalem Gewicht
Def: extremes Matching
Def: Längenfunktion
Satz: Augementierung eines extremen Matchings mit Hilfe eines M-augmentierenden Weg minimaler Länge
Algorithmus: Die ungarische Methode
Satz: Residualgraph hat keine gerichteten Kreise negativer Länge
7. Freitag, 2. Mai 2014 (pdf)
Kapitel 4 Flüsse in Netzwerken
4.1 Das Max-Flow-Min-Cut Theorem
Def: s-t-Fluss
Lemma: Wert eines s-t-Flusses ist durch Kapazität eines s-t-Schnitts beschränkt
Def: Residualgraph
Lemma: Erkennung eines maximalen Flusses durch Residualgraph
Theorem: Max-Flow = Min-Cut
Korollar: ganzzahlige Kapazität => ganzzahliger maximaler Fluss
Algorithmus von Ford-Fulkerson
8. Mittwoch, 7. Mai 2014 (pdf)
Satz: Endlichkeit des Ford-Fulkerson-Algorithmus für rationale Kapazitäten
4.2 Verbesserung des Ford-Fulkerson-Algorithmus
Satz: (Dinits 1970, Edmonds-Karp 1972) Falls immer kürzeste s-t-Wege zur Flussverbesserung gewählt werden, ist die Anzahl der Iterationen höchstens |V| |A| (insbesondere unabhängig von den Kapazitäten)
9. Freitag, 9. Mai 2014 (pdf)
Teil II: THEORIE DER LINEAREN OPTIMIERUNG
Kapitel 5 Polyedertheorie
Kapitel 5 Polyedertheorie
Lineares Programm
5.1 Konvexe Mengen
Def: Konvexkombination, Verbindungsstrecke, konvexe Menge
Satz: Charakterisierung von konvexen Mengen
10. Mittwoch, 14. Mai 2014 (pdf)
Bsp: Einheitskugel bzgl. einer Norm
Def: konvexe Hülle
Satz: Charakterisierung der konvexen Hülle
Def: Polytop
Def: affine Unabhängigkeit, Dimensions
Satz: Caratheodory
11. Freitag, 16. Mai 2014 (pdf)
5.2 Trenn- und Stützhyperebenen
Def: Hyperebene, Halbraum, Trennhyperebene, Stützhyperebene
Lemma: metrische Projektion
Theorem: Existenz von Trennhyperebenen
12. Mittwoch, 21. Mai 2014 (pdf)
Def: Polyeder
5.3 Extrempunkte und Ecken
Def: Extrempunkt, Ecke
Satz: Charakterisierung von Ecken eines Polyeders
Korollar: Polyeder besitzen nur endlich viele Ecken
13. Freitag, 23. Mai 2014 (pdf)
Theorem: (Minkowski) Beschränktes Polyeder ist Polytop
Def: Polare
Lemma: Eigenschaften der Polaren
Theorem: (Weyl) Polytop ist beschränktes Polyeder
14. Mittwoch, 28. Mai 2014 (pdf)
Def: konvexer Kegel
Def. und Satz: konische Hülle
Theorem: Polyeder sind genau die Minkowskisummen von Polytopen und konvexer Kegel
5.4 Lemma von Farkas
Satz: Lösbarkeitskriterium für lineare Gleichungssysteme
Satz: Farkas Lemma
Korollar: Variante von Farkas Lemma
15. Freitag, 30. Mai 2014 (pdf)
5.5 Lineare Programmierung
Def: Lineares Programm (LP)
Satz: Optimale Lösungen werden in Ecken angenommen
Def: Primales, duales LP
Satz: schwache Dualität
Satz: Optimalitätsbedingung, Komplementaritätsbedingung
16. Mittwoch, 4. Juni 2014 (pdf)
Theorem: Starke Dualität
Korollar: Variante des Dualitätstheorems
Kapitel 6 Ganzzahlige Optimierung und vollständig unimodulare Matrizen
6.1 Ganzzahlige lineare Programme
Def: Ganzzahliges LP in Standardform
Bsp: Matchingzahl eines Graphen als ganzzahliges LP
Dualitätsbeziehungen und P vs. NP-Problem (Millenium Prize)
Def: Ganzzahliges Polytop
17. Freitag, 6. Juni 2014 (pdf)
6.2 Vollständig unimodulare Matrizen
Def: Vollständig unimodulare (VU) Matrix
Satz: $A$ VU, $b$ ganzzahlig, dann ist jede Ecke von $P = \{x : Ax \leq b\}$ ganzzahlig
Def: Ganzzahliges Polyeder
Satz: $A$ VU, $b$ ganzzahlig, dann ist Polyeder $P = \{x : Ax \leq b\}$ ganzzahlig
Korollar: Ganzzahlige LP Dualität
Satz: (Hoffman-Kruskal) Charakterisierung von vollständig unimodularen Matrizen
18. Mittwoch, 18. Juni 2014 (pdf)
6.3 Vollständig unimodulare Matrizen und bipartite Graphen
Satz: Graph ist bipartit genau dann wenn seine Inzidenzmatrix vollständig unimodular ist
Korollar: Matchingtheorem von König
Korollar: Ungleichungsbeschreibung des Matchingpolytops von bipartiten Graphen
19. Freitag, 20. Juni 2014 (pdf)
Korollar: Theorem von Egervary über gewichtete Matchings in bipartiten Graphen
6.4 Vollständig unimodulare Matrizen und gerichtete Graphen
Satz: Inzidenzmatrizen von gerichteten Graphen sind vollständig unimodular
Korollar: Max-flow-min-cut Theorem
20. Mittwoch, 25. Juni 2014 (pdf)
TEIL III: ALGORITHMEN DER LINEAREN OPTIMIERUNG
TEIL III: ALGORITHMEN DER LINEAREN OPTIMIERUNG
Kapitel 7 Das Eliminationsverfahren von Fourier und Motzkin
7.1 Fourier-Motzkin Elimination
7.2 Das Lösen von linearen Programmen mit Fourier-Motzkin Elimination
7.3 Farkas Lemma mit Fourier-Motzkin
21. Freitag, 27. Juni 2014 (pdf)
Kapitel 8 Das Simplexverfahren
Kapitel 8 Das Simplexverfahren
Algorithmus
22. Mittwoch, 2. Juli 2014 (pdf)
Satz: Simplexalgorithmus terminiert in endlich vielen Schritten
Finden einer Startecke
Zur praktischen und theoretischen Effizienz
23. Freitag, 4. Juli 2014 (pdf)
Kapitel 10 Die Innere-Punkte-Methode