How to find min cut in this flow network?

918 Views Asked by At

I have created a flow network and wondering what the min cut is.

I can't embed yet

Clearly its a max flow since the edges out of $s$ are fully saturated.

The algorithm to find min cut is to draw the residual and then see which nodes are reachable from $s$. This is the $S$ in the min cut.

In the residual, $d$ is the only node reachable from $s$. So $s,d$ are the $S$ part of the min-cut.

However this doesn't agree with the min-cut-max-flow thereom, which states that the value of the flow graph ($6$), must equal the capacity of edges leaving the cut, which is $3$ (s->a), $3$ (s->c), $5$ (d->t), which is not 6 (its actually 11). What is wrong with this cut?

1

There are 1 best solutions below

2
On

The edges out of $s$ are not fully saturated, since $(s,d)$ has a capacity of 2 and no flow.

By contrast, the edges out of $\{s,a,c,d\}$ are $\{(a,b),(d,t)\}$, which are fully saturated. Those edges are the minimum cut of $6$ that matches the maximum flow of the network.