Finding minimal cut of a flow network

Question

I am trying to find a minimum cut of the following network

I am using the following algorithm:

1. Run Ford-Fulkerson algorithm and consider the final residual graph.

2. Find the set of vertices that are reachable from source in the residual graph.

3. All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges.

In the first step, my algorithm finds 3 paths:

 - s->b->h->t  **value: 1** 
 - s->d->e->t  **value: 1**
 - s->c->h->i->m->d->g->t  **value: 0.5**

So the maximum flow (and therefore minimum cut) is equal to 2.5.

However, when I later try to eliminate the aforementioned paths from the network I end up with something like this:

The reachable vertices are s, c and h, which form a cut equal to 3.5.

What am I missing? Why can't I traverse the graph like I would normally to get the minimum cut?

Answer 1

Every time you increase the capacity of an edge in the residual graph, you need to increase the capacity of the opposite edge by the same amount.

Example graph:

Here is the residual graph without backward edges and the the set of the vertices reachable from S (which do not constitute a min-cut):

And the correct residual graph with the min-cut:

Answer 2

I assume, that your definition of residual graph is that you put edge A->B in residual graph if:

a) There is some different between flow and capacity in direction A->B (aka forward edge) b) There is some flow in direction B->A (aka backward edge)

In this definition your step 2 is wrong.

To find minimum cut, you only walk through forward edges from start. Now you can denote vertices reachable from start as set R and rest as set R'. Now the cut is made by edges between R and R'. And the size of the cut is flow between R and R'.