0
$\begingroup$

I have a network flow (with min and max capacities) where the only transport units flowing are within a cycle (of flow value 2). The source of the network does not send out any transport units into any direction and the transport units getting into the sink are all getting sent away directly, so 0 transport units "stay" there. Now my question is, is such a flow allowed as long as minimium neccesarry flow (given by min capacities) exists and the amount of incoming transport units is equal to the amount of outgoing transport units? Or is a flow network where the source doesn´t send out any transport units not permitted?

I look forward for any help.

$\endgroup$
4
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$
    – Kaveh
    Mar 2, 2013 at 7:12
  • $\begingroup$ I am sorry, I did not know this. Thanks for clarification. I will consider reposting this question in the Computer Science section. $\endgroup$
    – Philipp
    Mar 2, 2013 at 12:20
  • $\begingroup$ If you want I can migrate the question to Computer Science for you. $\endgroup$
    – Kaveh
    Mar 2, 2013 at 21:13
  • $\begingroup$ Thank you Kaveh, since this question and the question related to it (see cstheory.stackexchange.com/questions/16664/…) have already been answered it is not necessary to migrate it. However, since it might help other people struggling with similar problems, it might be a good idea to migrate both questions to the CS section. $\endgroup$
    – Philipp
    Mar 3, 2013 at 9:37

1 Answer 1

1
$\begingroup$

You can make it valid depending on your definition of a valid network flow. Let s and t be the source and sink, respectively. Depending on your problem you may no further restrictions of the network flow conservation of t and s. In most definitions there are even no further restrictions on that, as this would just complicate the definition (without helping much).

If you want to restrict such "superficial" network flows in your example, you may however further state that for each edge (u,v) with a flow (i.e. flow function f(u,v)>0) there must be a path from s to u where each edge on the path has a positive flow (i.e. f(e)>0).

You may further restrict the flow on s not to be negative and the flow on t not beeing positive, i.e. for sum for all u on f(s,u) must be positive and sum for all u on f(u,t) must be positive or 0.

This should then remodel a "more intuitive" network flow comparable with water flows :).

(Note that the restriction: the source must not send out any transport units does not help much to prevent such superficial flows as suggested in the question.)

However, typically one assumes that f(t,u)<=0 for all vertices u, i.e. the sink consumes everything which it retrieves.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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