Let (G, u, s, t) be a network with n = |V| nodes and m = |E| edges and u(e) elementof Z_ greaterthanorequalto 0 for all e elementof E. Suppose that f* is the optimum max-flow. In this exercise, we want to develop a faster version of the Ford-Fulkerson algorithm. In fact, we want to modify the algorithm so that in each iteration the algorithm chooses the path P that maximizes the bottleneck capacity gamma = min{u_f (e) |e elementof P}. We call that algorithm "smart FF". a) Show that in the first iteration smart FF finds already a flow f with val(f) greaterthanorequalto 1/2m val(f*). b) Now suppose we already computed some s-t flow f. Show that there exists a flow g in G_f with val (g) greaterthanorequalto val (f*) - val(f). c) We want to generalize the claim in a). Consider any iteration of smart FF and say that f is the flow that we computed so far. Show that there exists always a path Pin G_f on which the bottleneck capacity min{u_f (e) |e elementof P} is at least 1/2m (val(f*) - val(f)). d) Show that smart FF needs at most o(m middot log(val(f*)) many iterations. Let (G, u, s, t) be a network with n = |V| nodes and m = |E| edges and u(e) elementof Z_ greaterthanorequalto 0 for all e elementof E. Suppose that f* is the optimum max-flow. In this exercise, we want to develop a faster version of the Ford-Fulkerson algorithm. In fact, we want to modify the algorithm so that in each iteration the algorithm chooses the path P that maximizes the bottleneck capacity gamma = min{u_f (e) |e elementof P}. We call that algorithm "smart FF". a) Show that in the first iteration smart FF finds already a flow f with val(f) greaterthanorequalto 1/2m val(f*). b) Now suppose we already computed some s-t flow f. Show that there exists a flow g in G_f with val (g) greaterthanorequalto val (f*) - val(f). c) We want to generalize the claim in a). Consider any iteration of smart FF and say that f is the flow that we computed so far. Show that there exists always a path Pin G_f on which the bottleneck capacity min{u_f (e) |e elementof P} is at least 1/2m (val(f*) - val(f)). d) Show that smart FF needs at most o(m middot log(val(f*)) many iterations