Aufgabe:
Text erkannt:
Sei \( (G, u, s, t) \) ein Netzwerk mit einem azyklischen Digraphen \( G \). Zur Berechnung blockierender Flüsse betrachten wir folgenden Advance-Ret reat-Augment-Algorithmus:
Eingabe: \( \operatorname{Netzwerk~}(G, u, s, t) \) mit \( G \) azyklisch
Ausgabe: Blockierender Fluss \( f \)
\( \begin{array}{l} \text { 1: } f(a)=0 \quad \forall a \in A(G) \\ \text { 2: } P=(s) \end{array} \)
3: loop
4: \( \quad \) if Weg \( P \) kann in \( G \) verlängert werden then
5: Advance: Verlängere Weg \( P \) um einen Pfeil
7: \( \quad \) if \( P=(s) \) then
8: \( \quad \) Rückgabe des blockierenden Flusses \( f \)
9: Retreat: Verkürze den Weg \( P \) um seinen letzten Pfeil \( a \) und entferne \( a \) aus \( G \)
10: if \( P \) ist ein \( s-t \)-Weg then
11: Augment: Augmentiere \( f \) maximal entlang \( P \)
12: Entferne alle Pfeile \( a \) aus \( G \), für die \( f(a)=u(a) \) gilt
13: \( \quad P=(s) \)
1.1 Zeigen Sie, dass der Algorithmus korrekt funktioniert.
1.2 Zeigen Sie, dass der Algorithmus eine Laufzeit von \( O(m n) \) hat.
Hinweis: Schätzen Sie die Anzahl der Augment-, Advance- und Retreat-Schritte und deren jeweilige Laufzeit nach oben hin \( a b \).
