Show that no flow can have value exceeding $9$

56 Views Asked by At

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?