0
$\begingroup$

graph

I get the residual graph by Ford-Fulkerson Algorithm: 2

I get that the minimum cut can be found by the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $S$, the rest of the nodes are called $T$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $S$ to a node in $T$.

So I think $S = \{S, C, E\}$, and $T = \{T, A, B, D, F\}$. But I found that what I found was not the minimum cut and two subsets I wanted. Why? Is my residual graph wrong?

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you please show a flow that would produce that residual graph? $\endgroup$
    – JimN
    May 2 at 9:04
  • $\begingroup$ Of course, I've put it on $\endgroup$
    – waxyao
    May 6 at 9:58
  • $\begingroup$ Yes, your residual graph is wrong. The residual graph should include all your blue arcs in your diagram. For example, since there is a flow of 4 from A to E, the residual graph should include an arc from E to A of capacity 4 (representing the possibility of "pushing back" 4 units of flow there). So your partition of {S,C,E} should be including more nodes, like A as I just described. $\endgroup$
    – JimN
    May 6 at 10:04
  • $\begingroup$ Thank you! I understand that I should only delete the flow with a weight of 0, not the reverse flow, right? $\endgroup$
    – waxyao
    May 6 at 12:03
  • $\begingroup$ Correct, the non-zero reverse flow arcs are a part of the residual graph $\endgroup$
    – JimN
    May 6 at 17:27

1 Answer 1

Reset to default
0
$\begingroup$

As settled in the Question's comments:

The residual graph, as presented, is incomplete. The residual graph must include the non-zero reverse flow arcs. Then anything reachable from the source $S$ in that residual graph forms one part of the partition of the min cut.

Improve this answer
$\endgroup$

Your Answer

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

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