Aufgabe:
In einem Netzwerk \( (G, u, s, t) \) bezeichne \( v^{*} \) den Wert eines maximalen \( s \)-t-Flusses. Wir nennen einen Pfeil in \( G \) einen wichtigen Pfeil, wenn sein Entfernen zu einer maximalen Verringerung von \( v^{*} \) führt. Im Folgenden sei \( f \) ein beliebiger maximaler s-t-Fluss.
Zeigen oder widerlegen Sie die folgenden Aussagen:
1.1 Ein wichtiger Pfeil ist ein Pfeil \( a \) mit maximaler Kapazität \( u(a) \) unter allen \( a \in A(G) \).
1.2 Ein wichtiger Pfeil ist ein Pfeil \( a \) mit maximalem Flusswert \( f(a) \) unter allen \( a \in A(G) \).
1.3 Ein wichtiger Pfeil ist ein Pfeil \( a \in A(G) \) mit maximalem Flusswert \( f(a) \) unter allen Pfeilen, die zu einem minimalen \( s \)-t-Schnitt gehören.
1.4 Ein Pfeil, der nicht zu einem minimalen Schnitt gehört, ist kein wichtiger Pfeil.
1.5 Ein Netzwerk kann mehrere wichtige Pfeile enthalten.
