Consider the following graph, which describes a flow network.

So Si

v$3$

v$1$

v$2$

v$4$

v$5$

v$6$

v$7$

$5(5)$

$4(3)$

$3(3)$

$2(2)$

$4(2)5(4)$

$1(1)$

$3(3)$

$6(6)$

$3(2)$

$1(0)$

$5(2)$

$2(2)$

Here, the vertex labeled So is the source, and the vertex labeled Si is the sink. The

edge weightings indicate flow capacity, and the figures in brackets indicate the current

flow through the network.

$($i$)$ Identify the current total flow. $[2$ marks$]$

$($ii$)$ a$)$ Consider the following set of edges:

C $=\{($v$1,$ v$4),($v$2,$ v$5),($v$3,$ v$5)\}.$

Carefully explain why this set of edges forms a cut for the network. What is

the capacity of this cut? $[5$ marks$]$

b$)$ What does the $$max$-$flow$/$min$-$cut$$ theorem together with your answer to

$3($ii$)($a$)$ tell you about the maximum possible flow through the network?

$[3$ marks$]$

$($iii$)$ Apply the Ford$-$Fulkerson procedure once to the above network, and draw a diagram to illustrate the new flow. Give full details of your considerations. Decide,

with justification, whether or not the new flow is maximal. $[14$ marks$]$

$($iv$)$ Does there exist a cut for the network with a lower capacity than C$?$ If so$,$ find

such a cut. If not, explain why a lower capacity cut cannot exist