1
$\begingroup$

Let $N$ be the network with source $u$ and sink $v$, where each are is label with its capacity.

enter image description here

a) Show that no flow can have value exceeding 9

b) Give an example of a flow $f$ on $N$ such that $val(f)=9$

My professor went through this very fast, so I don't think I can understand very well about flow. The number on the graph are the capacity of the arc, I know that the flow can't be bigger than the capacity, so for a), is it because the max capacity is from $x$ to $y$ and the biggest is $5+4=9$ so the flow of the whole network can't be bigger than 9? Why can't we have the max capacity be $5+3+2=10?$

For b) I know that $val(f)= f^+ -f^-= flowout - flow in$, but they only give me capacity, should I assume that the flow and capacity are the same?

$\endgroup$
  • $\begingroup$ The two edges going into $v$ have a total capacity of $5+4=9$, so no more than $9$ can flow into $v$. For part (b), label each edge with a flow that is less than or equal to its capacity, so that every vertex but the source and sink has flowout=flowin. $\endgroup$ – vadim123 Nov 14 '14 at 18:28
  • $\begingroup$ so the max flow is just the sum of in degree of the sink? $\endgroup$ – Diane Vanderwaif Nov 14 '14 at 18:30
  • $\begingroup$ @Diane : Not always. It depends on the network. See : en.wikipedia.org/wiki/Max-flow_min-cut_theorem $\endgroup$ – Manuel Lafond Nov 14 '14 at 18:31
  • $\begingroup$ @vadim123: Don’t you mean the minimum capacity of a set of edges that disconnects the graph? $\endgroup$ – Brian M. Scott Nov 14 '14 at 18:40
  • 2
    $\begingroup$ @Diane: Looks good to me. $\endgroup$ – Brian M. Scott Nov 14 '14 at 19:18

Your Answer

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

Browse other questions tagged or ask your own question.