In a network flow graph, using the Ford–Fulkerson algorithm, we can find a residual graph G_f
which no augmenting paths. This gives us a way of finding one minimum cut (a cut (S, T)
with minimum capacity) where S
is the set of vertices reachable from the source vertex s
in G_f
(and it is clear that this set of vertices are not in T
, the cut that is on the side of the sink vertex t
).
Analogously, we can repeat the Ford–Fulkerson algorithm to find a residual graph G'_f
that is anchored at the sink t
, such that we can find another minimum cut (S', T')
where T'
is the set of vertices reachable from the sink vertex t
in G'_f
. It is possible that (S, T)
and (S', T')
are different (see my made-up network flow below with 2 different minimum cuts):
The question there is, is there are more comprehensive way of finding other minimum cuts in the the flow network? Or are there only ever a maximum of 2 minimum cuts in a flow network?