DO NOT USE AI $.$Let $N$ be a network where each arc$(i,j)$ has both a capacity constraint $c(i,j)$ and a

lower bound constraints $l(i,j).$ We are interested in finding a feasible flow.

$($a$)$ Explain why an arc $(i,j)$ with flow $f(i,j)$ such that $l(i,j)f(i,j)c(i,j)$ can be

represented equivalently by a sink with demand $l(i,j)$ at vertex i and a source with

supply $l(i,j)$ at vertex $j$ and a flow $f^{\text{'}}(i,j)$ such that $0f^{\text{'}}(i,j)c(i,j)-l(i,j).$

$($b$)$ Show that finding a feasible flow from $s$ to $t$ in $N=(V,U,l,c)$ is equivalent to finding

the maximum flow $f^{\text{'}}$ in the network after

modifying the bounds on $f(i,j)$ to $0f^{\text{'}}(i,j)c(i,j)-l(i,j),$

lumping all the resulting sources into one supersource $s^{\text{'}}$ with outgoing arc capacities

${\displaystyle \underset{\text{k}\text{i}\text{n}\text{P}(j)}{\overset{?}{}}}l(k,j)$ for arcs $(s^{\text{'}},j),$ where $P(j)$ is the set of all predecessors of $j.$

lumping all the resulting sinks into one supersink $t^{\text{'}}$ with incoming arc capacities

${\displaystyle \underset{\text{k}\text{i}\text{n}\text{S}(i)}{\overset{?}{}}}l(i,k)$ for arcs $(i,t^{\text{'}}),$ where $S(i)$ is the set of all successors of $j.$

connecting the sink $t$ to the source $s$ in $N$ by a return infinite capacity arc.

Give a sufficient and necessary condition on the new network for the existence of a feasible

flow in $N.$

$($c$)$ Apply the above method to the following network with source $1$ and sink $4$ to find a

feasible flow.

$($d$)$ Assume an initial feasible flow is given. Use this flow together with the Ford$-$Fulkerson

Algorithm to describe a method for determining i$)$ a maximum feasible flow, ii$)$ a minimum

feasible flow in $N.$

$($e$)$ Find a maximum and a minimum feasible flow in the example network $($with source $1$

and sink $4)$ of c$)$ with the feasible flow obtained in c$)$ and the method described in d$).$

DO NOT USE AI