1
$\begingroup$

I have a network:

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

$\endgroup$
  • $\begingroup$ Do you know how to distinguish if the flow labeled on a graph is a valid flow, given the capacities? $\endgroup$ – DanielV Feb 18 '16 at 22:02
  • $\begingroup$ i'm assuming as long as all undefined branches are less than the output. so in this case if f1+f2+f3 <= 90? $\endgroup$ – supremus_01 Feb 18 '16 at 22:06
  • 1
    $\begingroup$ 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) $\endgroup$ – agastalver Feb 18 '16 at 22:06
  • $\begingroup$ One thing that needs to be clarified, does the blue text represent flow, or does it represent capacities (with unlabeled capacities being infinite)? $\endgroup$ – DanielV Feb 18 '16 at 22:08
  • $\begingroup$ they're representative of flow @DanielV $\endgroup$ – supremus_01 Feb 18 '16 at 22:11
1
$\begingroup$

Flow must meet the following criteria:

  • Flow into a vertex must equal flow out
  • Flow must be non-negative
  • Flow must be less than or equal to capacity for each edge

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.

$\endgroup$

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.