2
$\begingroup$

The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob

|cite|improve this question
$\endgroup$
-1
$\begingroup$

It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow. Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird. Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow). Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You maybe right but the first part of the question says "Show how to find a maximum flow". It does not say find augmenting paths. Also, if I understand what you are telling me then to solve this question, I need to find multiple augmenting paths. Do I have that right? $\endgroup$ – Bob Mar 5 '18 at 2:46
  • $\begingroup$ @Bob, yup, that's right. Yes, I noticed that part of the question, but I believe I have the correct interpretation. I do realize it seems a bit weird. $\endgroup$ – D.W.♦ Mar 5 '18 at 3:06

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.