algorithm - Finding minimal cut of a flow network -


i trying find minimum cut of following network enter image description here

i using following algorithm:

  1. run ford-fulkerson algorithm , consider final residual graph.

  2. find set of vertices reachable source in residual graph.

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

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:

enter image description here

here residual graph without backward edges , the set of vertices reachable s (which not constitute min-cut):

enter image description here

and correct residual graph min-cut:

enter image description here


Comments

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -