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'?

enter image description here

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$.

  • $\begingroup$ Why did you use $\leftarrow$ instead of $\le$? $\endgroup$ – MJD Apr 12 '14 at 12:56
  • $\begingroup$ @fgrieu :Sir,thanks for the details response. In addition, could you advise me on how to find a number $\alpha$, a feasible flow such from $1$ to $7$ with value $\alpha$ and a $1−7$ cut with capacity $\alpha,$ based on the feasible flow you have previously constructed? And why is this feasible flow maximal and cut minimal? $\endgroup$ – Alexy Vincenzo Apr 12 '14 at 13:35
  • $\begingroup$ @MJD: We have $(5,7)\le9$, because that's a given. I used $(5,7)←8$ to mean than $(5,7)$ is assigned the value $8$ in the flow, and that matches $8\le9$. $\endgroup$ – fgrieu Apr 12 '14 at 13:39
  • $\begingroup$ @fgrieu: So there is a feasible flow from $1$ to $7$ with value of $8 \ ?$ $\endgroup$ – Alexy Vincenzo Apr 12 '14 at 14:17
  • $\begingroup$ @AlexyVincenzo: No with that constraint that $(2,5),(4,5),(6,5),(6,7)$ are saturated. Yes without that constraint (we can reduce everything in proportion $8/14$). $\endgroup$ – fgrieu Apr 12 '14 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.