Given the flow network below, run the Capacity Scaling Max-Flow algorithm (see below) and show the flow in the network G and the residual graph Gf after each -scaling phase. In addition, state the max flow and the min cut once the algorithm terminates.

Scaling Max Flow Initially f(e) for all e in G Initially set A to be the largest power of 2 that is no larger than the maximum capacity out of s: A s maxe out of s Ce While A21 (A) While there is an s-t path in the graph Gf Let P be a simple s-t path in Gf(A)