I can not find the max flow, min cut in this graph where all edges have capacity 1.
The graph:
1
The max flow in this graph from s to t is 2?
But it is impossible to separate s and t without cutting atleast 3 edges?
Max flow min cut in matching reduced to max flow
algorithmsbipartite-graphsgraph theorynetwork-flow
Related Solutions
These notes contain a proof. The digraph used in this proof is a little more complicated than the one that you have in mind: each point of the partial order corresponds to two vertices of the digraph.
Let $\langle P,\preceq\rangle$ be the partially ordered set; I’ll write $p\prec q$ to indicate that $p\preceq q$ and $p\ne q$. For each $p\in P$ the digraph $D$ will have two vertices, $p^-$ and $p^+$; in addition, it will have a source vertex $s$ and a sink vertex $t$. For each $p\in P$, $D$ has edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$; in addition, for each$p,q\in P$ with $p\prec q$ it has $\langle p^-,q^+\rangle$. Each edge has capacity $1$.
Let $f$ be a maximal flow in $D$, and let $\langle S,T\rangle$ be a minimal cut constructed by the Ford-Fulkerson algorithm. Note that every path from $s$ to $t$ has the form $s\to p^-\to q^+\to t$ for some $p,q\in P$ with $p\prec q$; thus $|f|$ is the number of $p\in P$ such that $f(s,p^-)=1$ there is a $q\in P$ such that $f(p^-,q^+)=1$. Let $C=\{p\in P:f(s,p^-)=0\}$; for future reference note that $|C|=|P|-|f|$.
If $p\in P\setminus C$, then $f(s,p^-)=1$, and there must therefore be a unique ‘successor’ $\sigma(p)\in P$ such that $f(p^-,\sigma(p)^+)=1$, and hence $p\prec\sigma(p)$. Thus, for each $p\in P$ there is a well-defined chain $$p=p_0\prec p_1\prec\ldots\prec p_n\in C$$ in $P$ such that $p_{k+1}=\sigma(p_k)$ for $k=0,\dots,n-1$. ($P$ is finite, so each chain must terminate, and the elements of $C$ are the only elements without successors.) For $p\in P\setminus C$ let $\xi(p)$ be the unique element of $C$ at which the chain from $p$ terminates, and let $\xi(p)=p$ for $p\in C$; then $$\Big\{\{p\in P:\xi(p)=q\}:q\in C\Big\}$$ partitions $P$ into $|C|$ chains. To complete the proof we must show that $P$ also has an antichain of cardinality $|C|$.
The desired antichain is $A=\{p\in P:p^-\in S\text{ and }p^+\in T\}$. Proving that it’s an antichain isn’t too hard. Suppose that $p,q\in A$ with $p\ne q$. Then $p^-\in S$ and $q^+\in T$, so $f(p^-,q^+)\ne0$: either $\langle p^-,q^+\rangle$ isn’t an edge of $D$ at all, or $f(p^-,q^+)=1$, and I leave it to you to show that the latter is impossible: it would unbalance the flow at $p^-$. (The argument here uses the hypothesis that the minimal cut was constructed using the F-F algorithm.) It follows that $p\not\preceq q$, and by symmetry (or a similar argument) $q\not\preceq p$. Thus, $A$ is an antichain.
The last step is to show that the edges contributing capacity towards $c(S,T)$ are preciesly the edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$ such that $p\notin A$; this also uses the hypothesis that the minimal cut was constructed using the F-F algorithm, to show that there are no edges of the form $\langle p^-,q^+\rangle$ with $p^-\in S$ and $q^+\in T$.
Once you’ve worked out these details, you’ll have shown that $c(S,T)=|P|-|A|$ and hence that $|A|=|P|-c(S,T)=|P|-|f|=|C|$, as desired.
Suppose $e$ is the edge whose capacity is reduced by $\delta$. The capacity of all cuts such that $e$ is one of their cross edges is decreased by $\delta$. The capacity of all other cuts is unchanged. If $e$ is a cross edge of a source-sink minimum cut, the capacity of the minimum cut decreases by $\delta$.
Best Answer
If you apply the usual flow-augmenting algorithm, you may arrive at flows of 1 in each of the arcs sa, sb, ab', ba', a't, and b't, flows of zero in the other arcs, so there's your flow of value 2. Now when you run the flow-augmenting algorithm again, you can label the source, s, and you can label c from s, and you can label b' from c, and (the tricky part) you can label a from b' (since b' is labeled, a is unlabeled, and there is a flow from a to b). So the cut is $A=\{\,s,c,b',a\,\},B=\{\,b,a',c',t\,\}$, and the arcs from $A$ to $B$ are sb and b't, and cutting those two arcs indeed separates s from t.