Herzlich willkommen zur heutigen Vorlesung. Wir sind mittendrin stehen geblieben in diesen

Preflow-Push oder Preflow-Push oder Präfluss-Algorithmen und da wollen wir heute fortfahren. Wir haben

abgeschlossen den Klassiker unter den maximalen Flussalgorithmen sozusagen, augmentierende Wege-

Algorithmen. Wir haben gesehen, dass wenn man einen kürzesten, also kürzester bezüglich der

Anzahl Bogengewichte augmentierenden Weg wählt, dass man mit Breast-For-Search tun kann, dann

kriegt man streng polynomialer Laufzeit hin, also N mal M². Das war das Ergebnis der letzten Stunde

und dann haben wir angefangen und haben gesehen, was ist eigentlich der Nachteil von diesem Verfahren

und da haben wir gesehen, dass wir eigentlich jedes Mal einen Weg suchen müssen und wenn es dumm

läuft, entlang von dem Weg nur kleine Einheiten schieben. Und dieses Wegsuchen kostet uns jedes

Mal mindestens ein O von N oder ein O von M, wenn es dumm läuft und es macht in Anführungszeichen

ein bisschen die Laufzeit kaputt und die Idee war zu sagen, hey lass uns mal so viel schieben, wie es

nur geht, völlig wurscht, ob wir jetzt unterwegs zulässig sind oder nicht. Wir haben dann so was da

einen sogenannten Pseudofluss genannt, also wir erlauben dann an Zwischenknoten Überschüsse und

haben aber dann gesagt, das Problem ist, es ist ja lieber und recht, wenn wir Überschüsse haben, aber

es ist dann die Frage, wenn ich so einen Überschussknoten habe, wo baue ich denn das hin ab? Also ich

muss ja wissen, wohin ich das weiter schiebe. Deswegen haben wir so eine Markierung eingeführt und

da haben wir gesehen, dass diese Markierung eine untere Schranke für die Distanz zur Senke ist,

also zu dem T. Das heißt, wo immer sozusagen dieses D abnimmt, dahin wollen wir sozusagen

Fluss schicken. Das war die Idee und dann haben wir gesagt, wenn wir einen Pseudofluss haben und

also die ganze Zeit während dem Algorithmus wollen wir einen Pseudofluss haben plus eine gültige

Markierung, dann erfüllt das die Optimalitätsbedingungen, sprich der Wert dieses Flusses,

entspricht genau dem Wert eines Schnittes. Das hat man gestern auch festgehalten. So und wenn

wir es jetzt schaffen, aus dem Pseudofluss einen Fluss zu machen, sprich alle Überschüsse,

alle aktiven Knoten abzubauen, dann ist das ein Fluss, der die Optimalitätsbedingungen erfüllt und

damit wissen wir, wir haben einen optimalen Fluss auf diese Art und Weise auch gefunden. Also in dem

Sinn, komplementär oder dual, zu dem anderen Ansatz, da hatten wir immer eine zulässige Lösung

und haben versucht, Optimalität zu erreichen, also einen Schnitt zu finden, der den Wert von diesem

Schnitt erfüllt. Jetzt haben wir immer Optimalität, sind aber unzulässig und versuchen diesen

unzulässigen Fluss, also diesen Pseudofluss zulässig zu machen. Und dieses Konzept, diese unterschiedliche

Herangehensweise, einmal sich auf die Zulässigkeit zu konzentrieren und versuchen optimal zu werden

oder umgekehrt, sich auf Optimalität zu konzentrieren und Zulässigkeit zu erreichen, diese unterschiedliche

Herangehensweise zur Lösung von Problemen, da wird uns noch öfters begegnen und hier ist ein

klassisches Beispiel, wo das sehr gut funktioniert. Gibt es bis dahin noch Fragen zu gestern?

Dann würde ich jetzt einfach an dieser Stelle weitermachen von gestern, vielleicht nochmal

zwei wichtige Begriffe, die wir das letzte Mal hatten, dass wir die nochmal hinschreiben. Das

war einmal der Pseudofluss und das einer Markierung. Also wir hatten nochmal

Pseudofluss x, wenn sozusagen alles zwischen den Kapazitäten ist und wenn x Delta minus von v

minus x Delta plus von v größer gleich Null ist und das Ding hat man als Überschussfunktion definiert. Und wir hatten eine Markierung,

Markierung D, wenn einmal D von S gleich N und D von T gleich Null ist und gleichzeitig D von v

kleiner gleich D von v plus eins ist für alle v, w in A von x. Das war das Kriterium, wo wir gesagt haben,

also wir gucken jetzt sozusagen, was ist der Abstand, wie komme ich zu dem T, wenn hier der v ist und hier der w,

dann sollte, wenn ich auf dem Weg zum T, das ist die optimale Petzbedingung, soll es vom V höchstens so

weit sein, als wenn ich über den V laufe. Das ist genau das kürzeste Weggetäum, was wir hatten, auch als wir

kürzeste Wege uns angeguckt haben. So jetzt haben wir festgestellt in gestern, dass das letzte Ergebnis,

dass die Distanz von, bezüglich x, von v zum T, dass es immer größer gleich ist als das D von v, wenn ich eine

Markierung habe. Das war die letzte Aussage, die wir gestern hatten. So jetzt, also die Frage ist, also wo

wollen wir jetzt schieben? Also wir wollen natürlich jetzt entlang von Bögen schieben, die näher an dem T liegen.

Also die Idee ist, Fluss, Idee, Fluss von aktiven Knoten zu Nachbarn schieben oder im englischen Push, die näher an

T liegen. Also das heißt, zu Nachbarn aktive Knoten, v zu Nachbarn, w zu schieben, sozusagen, sodass das

Distanzlabel kleiner wird. Also das heißt, D von v sollte größer sein als D von v. Das ist das, was wir wollen.