Q$-2(20$ pts$).$ Maximum flow. Consider the following network where $1$ is the source and $5$ is the sink.

Some of the flows are already assigned as shown in the figure.

$($a $-12$ pts$)$ Continue from the given step and apply the shortest augmenting path algorithm to find

the maximum flow. Show the BFS queue and all the labels in every step.

$($b $-3$ pts$)$ What is the minimum cut found by the algorithm?

$($c $-5$ pts$)$ For any network, describe whether the following arguments are true or false. $($Answers

without reasoning will not be graded.$)$

i$.$ If we double the capacities of all the edges included in the minimum cut, then the value

of the maximum flow doubles.

ii$.$ If we reduce by half the capacities of all the edges included in the minimum cut, then the

value of the maximum flow reduces by half.