algorithmgraphmax-flowford-fulkersonminimum-cut

Finding minimal cut of a flow network


I am trying to find a minimum cut of the following network enter image description here

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: enter image description here

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?


Solution

  • 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:

    enter image description here

    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):

    enter image description here

    And the correct residual graph with the min-cut:

    enter image description here