Question $7.[5+3+7=15$ MARKS$]$ For a given flow network, the Ford$-$Fulkerson algorithm enables us to find the maximum flow over the network. We have the original flow network on the left where s is the source node, and t is the target node. On the right, we have a highlighted initial path $($s$->$u$->$v$->$t$).$

$(1)$ What$$s the maximum number of augmenting paths $($including the initial path$)$ that

need to be found until the termination of the Ford$-$Fulkerson algorithm given the

highlighted initial path $($s$->$u$->$v$->$t$).[5$ marks$]$

Breadth first search from the source to the target node can be used as a deterministic method to choose the augmenting paths in the Ford$-$Fulkerson algorithm.

$(2)$ Explain how BFS works in our example, and how many augmenting paths are found?

$[3$ marks$]$

$(3)$ Using BFS$,$ we know that the shortest paths length from source node to any other

node in the residual network monotonically $($non$-$strictly$)$ increase after each flow

update. What is the time complexity of the Ford$-$Fulkerson for a network with V nodes

and E edges if BFS is used? $[$Hint: how many times can one edge becomes the

bottleneck in the residual network?$]$