Minimal cut/maximum flow in directed graph

Question

I have a directed graph

Firstly, I used Ford-Fulkerson's algorithm to increase the flow of the network. When I marked the vertices, I saw that flow on path: s->a->b->d->t can be increased by one so graph changed to:

I know that when searching for maximum flow, you need to add up all the capacaties of edges that connect the minimal cut and outer part of the graph. My minimal cut contains vertices: s, a, c, so When I added up all the edges I got c(G, !G) = 3 + 2 +2 + 1, however, this is a lot bigger than flow to t which is 5.

What am I doing wrong, have I messed up with FF or minimal cut?

Answer 1

You minimum cut is not s, a, c, but s, a, b, c. Its capacity is 5 which is the maximum flow that you've calculated.

You can find the minimum cut by using the definition of the residual network. Recall that the Ford-Fulkerson terminates when there are no paths between s and t in the residual network.

The minimum cut (S,T) is defined as

S = { v | there exists a path from s to v in the residual network }

In you graph, the node b is reachable from c in the residual network because of the flow b->c with weight 3.