1.1 Falls G entgegengesetzte Kanten hätte, könnten wir in eine dieser einen Zwischenknoten einbauen. Es gibt dann einen Kreis, aber keine entgegengesetzten Kanten mehr
1.2) Nein, nur die Richtung kann sich umdrehen.
1.3) Bei der Kapazität, werden nur Kanten von Q nach S aufsummiert. Beim Fluss über den Schnitt werden die Rückkanten abgezogen.
1.4) Nein! Korollar 5 besagt "Für jeden maximalen Fluss gibt es einen ganzz. Fluss mit
gleichem Wert". Bsp:
mit
und
und
In diesem Flussnetzwerk gibt es einen Fluss mit Wert 1, der aber über die Kanten
nur jeweils 0.5 Einheiten fließen lässt. Dies ist zulässig, da der Fluss definiert ist als
1.5) Nein, FF hat mit Tiefensuche keine polynomielle Laufzeit, sondern nur eine pseudopolynomielle Laufzeitschranke durch
, wobei
die Summe der Kapazitäten aller Kanten ist.
Beispiel für ein solches Flussnetzwerk:
1.6) FF mit Breitensuche ist in
zu schaffen.
, da eine Iteration nach wie vor
lang dauert.
Kanten können gelöscht und wieder eingefügt werden. Eine Kante kann aber höchstens
mal entfernt werden es gibt im Restnetzwerk bis zu
Kanten. Da in jeder Iteration mindestens eine Kante entfernt wird ist die Anzahl der Iterationen höchstens
.
1.7) Beispiel:
parallele Kantenzüge von Quelle zu Senke. Zusätzlich vom obersten Kantenzug zum untersten diagonale Kanten,die alle Züge blockieren, falls etwas hindurchfließt. Dies ist dann ein nicht maximaler Sperrfluss.
2.1) Wir fügen von der alten Senke eine Kante zu einer neuen Senke ein, die die Kapazität
hat. Eine Lösung für das Max-Flow Problem liefert uns dann einen Fluss mit Wert
falls möglich.
2.2) Wenn ein Fluss
mit
gleichem Wert existiert, so lässt sich der Differenzfluss
bilden, welcher offensichtlich den Wert 0 hat. Daraus folgt direkt, dass dieser eine Zirkulation ist. Dass sich diese Zirkulation in Kreise teilen lässt, wovon mindestens einer negative Kosten hat, falls
kostenoptimaler ist als
muss getrennt gezeigt werden.
3.1) Ein Matching ist (inklusions-)maximal, wenn man keine Kante mehr hinzufügen kann, ohne dass dann es kein Matching mehr ist. Ein Matching ist ein maximum Matching, wenn es kein Matching mit mehr Kanten gibt.
3.2) Es gibt eine bijektive Abbildung zwischen Matchingproblemen und Flussnetzwerken. Außerdem entspricht der Wert des Flusses der Kardinalität des Matchings. Es folgt die Annahme.
3.3) Mit dem Algorithmus Maximum-Matching 1 haben wir gezeigt, dass wir das bipartite Matchingproblem in
lösen können. Wir haben auch festgestellt, dass der Algorithmus in jeder Iteration flussvergrößernde Wege sucht und somit Ford-Fulkerson entspricht. Also hat auch Ford-Fulkerson auf bipartiten Matchings eine Laufzeit von nur
.
3.4) Der Pfad hat höchstens Länge
, da er alternierend Nichtmatchingkanten und Matchingkanten besucht und mit freien Knoten beginnt und endet.
4.1) Angenommen der Schnitt
wäre nicht konvex. Dann gäbe es
, sodass ein Punkt
auf der Verbindungslinie von
und
nicht in
wäre.
ist also entweder nicht in
oder nicht in
. O.B.d.A sei
nicht in
. Da aber
und
offensichtlich in
sind, würde folgen, dass
nicht konvex ist. Widerspruch!
4.2) Die Nichtbasisvariablen haben stets den Wert 0. Es gibt
Nichtbasisvariablen, denen man jeweils eine Nebenbedingung zuordnen kann. Also liegt die Basislösung auf dem Schnitt von mindestens
Hyperebenen, was einem Knoten des Polyhedrons entspricht.
4.3) Das LP ist degeneriert. Es schneiden sich mehr als
Hyperebenen in einem Knoten.
4.4) Er gibt für jede Nichtbasisvariable an, wie sich der Zielfunktionswert in Abhängigkeit dieser Variable ändert. Ist der Wert positiv, so können wir den Zielfunktionswert verbessern, indem wir die Variable in unsere Basis aufnehmen. Sind alle Einträge negativ, haben wir eine optimale Lösung erreicht.
4.5) Die Gleichung
gibt uns für jede Basisvariable
an, welchen Wert sie beim Erhöhen der (Noch-)Nichtbasisvariable
annimmt. Offensichtlich erhöhen Basisvariablen mit negativem
ihren Wert und Basisvariablen mit positivem
verringern ihren Wert beim Erhöhen von
. (Das Erhöhen von
entspricht dem Entlanglaufen an einer Kante von einem Knoten/Basislösung zum/zur nächsten).
Mit dem Minimum von
bestimmen wir die Basisvariable, welche beim Erhöhen von
als erste den Wert 0 annimt (bevor sie negativ wird). So stellen wir sicher, dass wir
nicht zu weit erhöhen und die Lösung so durch eine negative Basisvariable ungültig machen. Wir suchen also den nächsten Knoten auf der gewählten Kante. Wenn wir
auf dieses Minimum setzen ergibt sich:
4.6) Diese Form ist nötig, damit wir sicher gehen können, dass die initiale Basis, die aus den Hilfsvariablen besteht gültig ist. Wäre das
einer Bedingung negativ, so wäre die (aus dem Null-setzen der Nichtbasisvariablen resultierende) Bedingung mit
wegen
nicht erfüllbar.
5.1) Die Knoten aus dem Set Cover Problem (Fähigkeiten) werden zu Hyperkanten von Hitting Set. Die Teilmengen aus Set Cover werden zu Knoten in Hitting Set, wobei diese Knoten genau dann zu einer Hyperkante gehören, wenn sie in der Set Cover Eingabe die entsprechende Fähigkeit abdecken.
5.2) Man erstellt aus der Hamiltonkreiseingabe einen vollständigen Graphen. Die Kosten der Kanten werden auf 1 gesetzt, falls die Kante in der Eingabe war, ansonsten auf
. Findet der Approximationsalgorithmus eine TSP-Tour der Länge
, so gibt es einen Hamiltonkreis.
Zusatzfrage: Warum kann es nicht passieren, dass
und so immer eine TSP-Tour der Länge
ausgegeben wird?
5.3)
und
5.4) Ein PTAS (
Polynomial Time Approximation Scheme) ist ein Algorithmus der für jedes
eine
-Approximaion in zur Eingabelänge polynomiell beschränkter Zeit liefert. Ist die Zeit zusätzlich polynomiell in
beschränkt, so nennen wir den Algorithmus einen FPTAS (
Fully Polynomial Time Approximation Scheme).