2
$\begingroup$

For the following problem I am trying to find maximum flow and minimum cut:

enter image description here

I found the maximum flow as 6 like this:

$1-3-7-8:2 flows$

$1-2-5-8: 2 flows$

$1-3-4-5-8:1 flow$

$1-3-4-6-5-8:1 flow$

But I am having trouble to match the min cut, I thought it would be 8(by cutting the following arcs $(7,8)$ and $(5,8))$. How do I match the min cut? Or do you think I made a mistake finding max flow?

$\endgroup$
3
$\begingroup$

The maximum flow is $6$. To find a corresponding minimum cut, note that $S=\{1,3,4,7\}$ is the set of nodes reachable from the source node $1$ in the residual network. Now consider the arcs from $S$ to $N\setminus S$.

$\endgroup$
2
  • $\begingroup$ We took the following arcs, right? I am asking to make sure. (1-2),(4-5),(4-6),(7-8). $\endgroup$
    – diabolik
    Jan 22 at 21:43
  • $\begingroup$ Yes, those are correct, with sum of capacities equal to $2+1+1+2=6$, matching the flow value. $\endgroup$
    – RobPratt
    Jan 22 at 21:49

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.