Compute the max flow for the following diagram, using the Ford-Fulkerson algorithm.

enter image description here

I computed the max flow, using the Ford-Fulkerson algorithm, and I got 14. However, the capacity of the min cut I found is 16, which does not verify the max-flow/min-cut theorem. Otherwise, if I did something wrong in finding the min-cut and/or max flow, let me know. It took me so much hours to work out this problem.

  • $\begingroup$ Can you show us your work? Perhaps we can spot an error in your work. $\endgroup$ – ml0105 May 5 '14 at 4:19

Max flow is 14. The cut partition is $\{B, C, D, G\}$ indicated in Green to $\{A, E, F, H\}$ indicated in Purple. Cut edges are indicated in red. By Max-Flow Min-Cut Theorem, the simultaneous existence of a cut of capacity 14 and a flow of capacity 14 proves this optimum.

Labeled graph

You can verify by looking at the validity of the flow by comparing the ingress and egress flow of each vertex.


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.