0
$\begingroup$

I was trying to solve problems in max flow algorithms. And I came across this MIT Lecture Quiz.

http://people.csail.mit.edu/moitra/docs/6854hw4.pdf

solution : http://people.csail.mit.edu/moitra/docs/6854hw4solns.pdf

Questions :

(a) In any maximum flow, and for all vertices v and w, either the amount of flow from v to w (f(v, w)) or the amount of flow from w to v (f(w, v)) is 0.

(b) Consider a directed graph G = (V, E). There always exists a maximum flow of G such that, for all vertices v and w, either the amount flow on vw or the amount of flow on wv is 0.

These two problems look one and the same. And both are based on the trick of 'Flow conservation on any vertex'. The main properties of both problems are the same. except that

first problem ---> any flow (all flow)

second problem --> a flow (at least one flow)

So this made the difference

problem 1 -> False (because any flow on subtraction and add to incoming and out going we can make it non zero. So the statement 'ALL FLOWS' makes this statement false)

problem 2 -> True (because any flow on subtraction and add to incoming and out going we can make it non zero, so whatever be the flow, we can make manipulations such that one is zero and other is non zero. so there is 'A FLOW' with this property. this 'A FLOW' makes this statement true.

Am I right in my understanding of the key difference in both the questions, thought both look almost the same ?

$\endgroup$
1
$\begingroup$

A helpful way to build intuition: Try working through an example! Can you find an example of a graph and a flow where property (a) is true? Then, ask yourself: is property (b) true in that one? What made the difference?

Spoiler (but it's best to try the above first; it will help you learn more from this exercise):

The crucial difference is between "for every maximum flow" vs "there exists a maximum flow". That's the difference between $\forall$ vs $\exists$. As you probably know, $\forall x . P(x)$ can be false even if $\exists x . P(x)$ is true.

$\endgroup$
  • $\begingroup$ Thanks. So my line of thinking was it right ? I think you too meant the same but in more math sense. Am i right ? $\endgroup$ – learner Apr 19 '17 at 23:31

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.