Wir wollen jetzt besser verstehen, warum es genügt, dass wir nur augmentierende Pfade

in diesem Residualnetzwerk suchen müssen und wenn das hier nicht mehr erfüllt ist, wir

aufhören können mit diesem Axflow Algorithmus.

Und dazu definieren wir st-Schnette.

Wir haben also jetzt wieder hier so ein Flussnetzwerk mit einer Quelle und einer Senke.

Hier sind diese Kanten, die gerechnet sind und die Gewichte haben.

Und ein st-Schnitt ist eine Partition der Knotenmenge in zwei Teilmengen.

Also zum Beispiel können wir jetzt hier durchteilen, das ist das hier, das ist jetzt die Menge

Groß S und die andere Menge ist die Menge T.

Das heißt, genauso wie auch schon bei ungerichteten Grafen ist, oder bei dem bisherigen Schnittkonzept,

das wir vorher schon hatten, ist eine Partition in zwei Teilmängern.

Eine bunte Partition in zwei Teilmängern, nur fordere mir es hier explizIt, dass die

Quelle und die Senke in den beiden Kategorien landen, also s muss in s sein und t muss in

t sein.

Und zu diesem s-t-Schnitt definieren wir jetzt noch ein paar Zahlen, das Paper-Zahl

ist der Nettofluss.

f von st über den schnitt das ist

ich habe diesen ersten terren

das ist die summe über alle flüsse

wo der anfangspunkt einer kante

es liegt und der endpunkt an der kante in t. das heißt wir schauen uns alle pfeile an

die über die kante drüber laufen

von s nach t

addieren diese diese diese werte auf

und

alle kanten die umgekehrt laufen die also von t nach s laufen

deren flüsse ziehen wir ab

ich mach das mal ein bisschen

spannender hier in dieser grafik

wir sagen jetzt einfach mal dass diese kante in die andere richtung geht

das heißt

wir

addieren also

diese beiden auf

ziehen

das hier

das ist dann der netto fluss über den schnitt also netto weil wir

quasi alles in der richtigen

vorzeichen addieren oder abziehen

und die kapazität des schnittes

ist jetzt also das waren die flüsse

fluss f hier geben

und da können wir den netto fluss berechnen

die kapazität ist von einem fluss völlig unabhängig das ist einfach nur was in eignenschaft des

schnittes

da addieren wir nämlich alle

kapazitäten

von kanten die von s nach t gehen also hier nicht

wir ziehen jetzt hier nichts ab was von t nach s geht

das heißt