Suppose a network $N = (G,c,s,t)$ where $c$ is real.
How do you find all min-cuts? (or how do you find the cut with the least number of vertices)
I've tried messing with the capacity, but since it might be real I can't get it to work.
EDIT: I'll try to rephrase the question more clearly : Amongst all the $(S,T)$ cuts in $G$ that have minimum capacity, find the one which has the least number of vertices.
(Or, similiarly, how do you find all min$(S,T)$ cuts in $G$ ? )
The number of partitions A,B which induce a minimum cut is at most $n^2$, and these can be enumerated in time $O(n^2 \log^3 n)$ using the Recursive Contraction Algorithm of Karger and Stein. So it is a simple matter to determine any property you would like of minimum cuts.