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

$\endgroup$
5
  • $\begingroup$ Can you please show a flow that would produce that residual graph? $\endgroup$
    – JimN
    May 2, 2023 at 9:04
  • $\begingroup$ Of course, I've put it on $\endgroup$
    – waxyao
    May 6, 2023 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, 2023 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, 2023 at 12:03
  • $\begingroup$ Correct, the non-zero reverse flow arcs are a part of the residual graph $\endgroup$
    – JimN
    May 6, 2023 at 17:27

1 Answer 1

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.

$\endgroup$

Your Answer

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

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