Task $4$

Ford$-$Fulkerson: Consider the flow network given in the following figure.

a$)$ Use the Ford$-$Fulkerson algorithm to find the maximum flow from s to $t$ for the

network in the figure. For each intermediate step you should show the

augmenting path and the residual network.

b$)$ Give a minimum cut for the network in the figure. State where this cut is$,$ by

giving the two sets of vertices, and not just its value.

c$)$ Suppose that you are given a minimum cut as sets A and $B$ partitioning the

set of vertices in a certain flow network $($where $sinA$ and tinB $).$ Let $k$ be the

number $($not the total capacity$)$ of the edges crossing from $A$ to $B.$ You

increase the capacity of each of these k edges by $1.$ Is it true that the

maximum flow in the network will increase by $k?$ If your answer is yes, then

give an explanation, if you answer is no$,$ then give a counterexample.a$)$ Use the Ford$-$Fulkerson algorithm to find the maximum flow from s to t for the

network in the figure. For each intermediate step you should show the

augmenting path and the residual network.

b$)$ Give a minimum cut for the network in the figure. State where this cut is$,$ by

giving the two sets of vertices, and not just its value.

c$)$ Suppose that you are given a minimum cut as sets A and B partitioning the

set of vertices in a certain flow network $($where s

in A and t

in B$).$ Let k be the

number $($not the total capacity$)$ of the edges crossing from A to B$.$ You

increase the capacity of each of these k edges by $1.$ Is it true that the

maximum flow in the network will increase by k$?$ If your answer is yes, then

give an explanation, if you answer is no$,$ then give a counterexample

Make it on paper