I am trying to find a minimum cut of the following network
I am using the following algorithm:
Run Ford-Fulkerson algorithm and consider the final residual graph.
Find the set of vertices that are reachable from source in the residual graph.
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?
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: