# Max/Min flow of a network

I have a network:

How do I figure out the maximum and minimum possible flow through each undefined branch?

• Do you know how to distinguish if the flow labeled on a graph is a valid flow, given the capacities? – DanielV Feb 18 '16 at 22:02
• i'm assuming as long as all undefined branches are less than the output. so in this case if f1+f2+f3 <= 90? – supremus_01 Feb 18 '16 at 22:06
• Define: A = [1 1 0; 0 -1 1; 1 0 1] x = [f1; f2; f3] b = [80; 10; 90] A*x = b f1, f2, f3 >= 0 (i guess) Subject to these equations, LP solve: - minimums: min(f1), min(f2), min(f3) - maximums: max(f1), max(f2), max(f3) – agastalver Feb 18 '16 at 22:06
• One thing that needs to be clarified, does the blue text represent flow, or does it represent capacities (with unlabeled capacities being infinite)? – DanielV Feb 18 '16 at 22:08
• they're representative of flow @DanielV – supremus_01 Feb 18 '16 at 22:11

For this, we'll have to assume the capacities are "$\infty$".
Vertex $A$ limits the flow of $f_1$ to 80, vertex $C$ limits it to 90. So we check if there is a flow through $f_1$ of 80: $f_1 = 80, f_2 = 0, f_3 = 10$ is a valid flow. We can also check if $0$ is a valid minimum: $f_1 = 0, f_2 = 80, f_3 = 90$.
Proceed similarly for $f_2$ and $f_3$. Just check "is there a valid flow with $f_n = x$?", you should be able to guess $x$ from the picture.