Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear programming problems and find a feasible solution? In particular, what is meant by the 'edge is saturated'?
p.s. my background in linear/network programming is at most rudimentary, so I apologize if my question seems trivial.
Thank you.
A feasible flow is an assignment of non-negative values to each edge, at most equal to the maximum value given for the edge in the statement, so that the sum of what enters any node equals what exits (with an additional implicit return edge from $7$ to $1$ with arbitrarily large value). An edge is saturated if it is assigned the value given. As an analogy, think moving an incompressible fluid from node $1$ to node $7$ (and back through an implicit large pipe with a pump in it) without exceeding the indicated maximum capacity of each pipe, and the added condition of using some pipes at full capacity.
It is required that $(2,5)\gets3, (4,5)\gets4, (6,5)\gets1$, thus $(5,7)\gets3+4+1=8$ so as to match the condition for node $5$, and that's less than the given maximum $9$. We want $(6,7)\gets6$, thus $(7,1)\gets14$ so as to match the condition for node $7$. We can choose $(1,3)\gets4$, $(3,6)\gets4$, $(4,3)\gets0$, $(4,6)\gets3$, $(1,4)\gets7$, $(1,2)\gets3$, $(2,4)\gets0$ (variants are possible).
Addition: the return $(7,1)$ is maximal. One possible proof is separating the graph in two halves with nodes $1$ $2$ $3$ $4$ $6$ on one side, and $5$ $7$ on the other. Edges going through the separation are $(2,5), (4,5), (6,5), (6,7)$ in one direction, and the single return $(7,1)$ in the other. The return $(7,1)$ is bound to be equal to the total $(2,5)+(4,5)+(6,5)+(6,7)$, which has all its edges saturated, thus $(7,1)$ can't be increased over the existing $(7,1)\gets 14$.