Aufgabe 2: Dimension des Matching Polytops
Hier habe ich leider einen groben Fehler ‘reingeschludert: der Graph sollte vollständig sein 
— sorry!
Hier die Berechnung der Dimension des perfekten Matchingpolytops zu 
Zunächst ist die Dimension höchstens 
Nun müssen wir noch zeigen, dass es außer Linearkombinationen von der Gradgleichungen keine weiteren zulässigen Gleichungen für das Polytop gibt. Dazu benutzen wir Satz 3.19 (bzw. Edmonds Matching-Polytop-Theorem), indem wir zeigen, dass keine der Ungleichungen in der vollständigen Beschreibung des perfekten Matching Polytops insgeheim eine Gleichung ist.
Fangen wir an mit den Ungleichungen 
Nun zu den Blütenungleichungen 
![{G[U^-]}](http://l.wordpress.com/latex.php?latex=%7BG%5BU%5E-%5D%7D&bg=ffffff&fg=000000&s=0 "{G[U^-]}")
Aufgabe 3: Blütenfacetten
Auch hier hat sich ein kleiner Fehler eingschlichen: Wie oben schon beobachtet, sind die Blütenungleichungen 
Ausserdem beachte man, dass die beiden Ungleichungen 
Wie im Hinweis angegeben, suchen wir einen Punkt, der 
Dazu müssen wir die linke Seite der Blütenungleichung 
Aufgabe 4: Benachbarte Ecken auf dem Perfekten-Matching-Polytop
Für diese Aufgabe haben wir die eine Richtung schon in der Übung gesehen: Wenn die symmetrische Differenz zwischen 
Dazu seien 
Für Kanten, die entweder sowohl in 
unter den Nebenbedingungen 
für alle Knoten 
unter den Nebenbedingungen 
für alle 
. Das duale Problem besteht also darin, eine reele “Knoten-
-Packung” 
maximaler “reeler Kardinalität” zu finden. (Generell ist eine (nicht-negativ ganzzahlige mit 
) “Knotenpackung” eine Auswahl von Ecken, so dass in jeder Kante nur eine Ecke gewählt wurde — mit anderen Worten, eine unabhängige Menge.)
einen blockierenden Fluß im Level-Netzwerk?
und Restkapaziät 
. Suche einen 
-Weg in 
, der nur Bögen 
mit 
benutzt. Existiert keiner, so sind wir fertig. Existiert einer, so erhöhe 
wie üblich, und verkleinere 
. Beachte, dass dadurch für einen Bogen 
auf 0 fällt.
mal ein 
-
-Weg gesucht. Der Trick ist, dass man das Suchen eines solchen Weges in Zeit 
machen kann, denn jeder Knoten in 
, dass 
höchstens 
Zusammenhangskomponenten ungerader Kardinalität hat. Spasseshalber zeigen wir das für beliebige Graphen 
ein perfektes Matching und 
eine ungerade (d.h. ungerade Kardinalität) Zusammenhangskomponente von 
ungerade, verläuft mindestens eine Kante von 
. Bezeichnet man mit 
die Endecke dieser Kante in 
der Wald 
höchstens eine Zusammenhangskomponenten ungerader Kardinalität, so hat 
kein perfektes Matching von 
eine exponierte Ecke von 
der eindeutige 
-Weg in 
und endet mit einer Kante 
ist immer mindestens eine Kante 
mit der Eigenschaft, dass die erste und die letzte Kante nicht in 
mit ![{V = [n]}](http://l.wordpress.com/latex.php?latex=%7BV+%3D+%5Bn%5D%7D&bg=ffffff&fg=000000&s=0 "{V = [n]}")
, 
und 
wie folgt kodiert:
Inzidenzmatrix ist, und 
die 
Einheitsmatrix. Die Koeffizientenmatrix hat Rang 
, (das ist immer der Fall, wenn man drei Matrize 
hat (
, 
), und das Bild von 
, 
, sagen wir 
sein. Außerdem muss in der unteren Hälfte der Matrix in jeder Zeile mal eine 1 vorkommen, also braucht man 
. Aber man braucht auch, dass 
keine Kreise enthält: denn sonst hätte man für die Matrix 
schließt man 
, und schließlich, dass 
in der linken Hälfte, die zu 
gehören, und genauso die Werte der Variablen in der rechten Hälfte 
, die zu 
gehören, sofort ablesbar: Sie haben den gleichen Wert, wie die jeweilige rechte Seite in der zugehörigen Zeile der unteren Hälfte der Matrix, also 
oder 
zu den Bögen im Baum 
in der linken Hälfte der Matrix dadurch bestimmt, dass die Gleichung 
hat vollen Spaltenrang. Die Werte der Variablen 
zu den Bögen in 
, wir müssen also sicherstellen, dass in~
herauskommt, und dass dieses dann zu einem 
führt. Letzteres ist äquivalent zu 
für 
und 
für 
. Puh! Gibt’s eine kurze Lösung für die Aufgabe?!???
von 
) auf die obere Schranke setzen, und erhält, wenn man 
nach 
löst, ein 
und den oberen Schranken?
folgendermaßen bestimmen kann: Entfernt man 
der Knotenmenge, sagen wir mit dem Anfangsknoten (
-Inzidenzmatrixeintrag) von 
. Wegen 
gilt 
. Ok, das war schneller ausgerechnet als ich dachte. Super. Wenn ich mich nicht irre (was eher wahrscheinlich ist) brauchen wir also für jeden Bogen 
oder 
; 
und 
, 
; 
; 
und 
.
), also entsprechen die zulässigen Basen Bäumen 
gilt und ausserdem
über alle x in der n-dimensionalen (euklidischen) Einheitskugel.
erfüllen, und für die (bei geeigneter Umnummerierung der Indizes) 
konstant ist. Wenig beeindruckend.
Primteiler.
ist. Dann berechnet man die Standardabweichung, und kommt auf 
. Schließlich wendet man die bekannte 
nicht hat. Wenn die Eigenschaften “statistisch” unabhängig wären, würde man einfach argumentieren, dass das Produkt der Wahrscheinlichkeiten 
(dass 
nicht eintritt) strikt größer 0 ist. Aber was, wenn das Eintreten eines 
wahrscheinlicher macht? Das Local-Lemma gibt eine Antwort auf diese Frage: Unter bestimmten Bedingungen an die Abhängigkeiten und die Wahrscheinlichkeiten der 