algorithm - Finding minimal cut of a flow network -
i trying find minimum cut of following network
i using following algorithm:
run ford-fulkerson algorithm , consider final residual graph.
find set of vertices reachable source in residual graph.
all edges reachable vertex non-reachable vertex minimum cut edges. print such edges.
in first step, 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 maximum flow (and therefore minimum cut) equal 2.5.
however, when later try eliminate aforementioned paths network end this:
the reachable vertices s, c , h, form cut equal 3.5.
what missing? why can't traverse graph minimum cut?
every time increase capacity of edge in residual graph, need increase capacity of opposite edge same amount.
example graph:
here residual graph without backward edges , the set of vertices reachable s
(which not constitute min-cut):
and correct residual graph min-cut:
Comments
Post a Comment