Consider the flow network shown on the right.

1. (3 points) Identify the values of the missing flows and justify

your answer.

2. (5 points) Show the residual network and an augmenting path

in the residual network (always pick the shortest path).

3. (8 points) Show the resulting new flow (4 pts). Is it maximum? If not keep finding short augmenting paths to increase the flow

until it becomes maximum. (4 pts). What is the max flow?

4. (4 points) Show a cut whose capacity is equal to the maximum

flow value from part (3).

4/4 0/2 715 216 Problem 1 (20 points) Consider the flow network shown on the right. 1. (3 points) Identify the values of the missing flows and justify your answer. 2. (5 points) Show the residual network and an augmenting path in the residual network (always pick the shortest path). 3. (8 points) Show the resulting new flow (4 pts). Is it maximum? If not keep finding short augmenting paths to increase the flow until it becomes maximum (4 pts). What is the max flow? 4. 4 points) Show a cut whose capacity is equal to the maximum flow value from part (3). 2/5 2/3 2/3 014 4/4