We consider the network flow problem with dynamically$-$evolving capacities in

the network. We start with a fixed network $N=(G=(V,E),c,s,t),$ where all

capacities are integers, and compute a maximum flow $f$ for $N.$ However at any

time in the future we may receive notification that the capacity of a particular

edge in the network is being increased by $1($or decreased by $1).$

$($a$)$ Suppose that the capacity of a single edge $(u,v)inE$ is increased by $1.$ Give

a $O(|V|+|E|)-$time algorithm which updates the flow $f$ to obtain a max

flow $f^{\text{'}}$ for the updated network.

$($b$)$ Suppose that the capacity of a single edge $(u,v)inE$ is decreased by $1.$ Give

a $O(|V|+|E|)-$time algorithm which updates the flow $f$ to obtain a max

flow $f^{\text{'}}$ for the updated network.