Given a max flow on a graph, how do you determine the actual edges that belong to the minimal cut?

Question

After applying an algorithm (like Ford-Fulkerson) that gives you the max flow over a graph $G(V,E)$, how do you determine the actual edges that belong to the minimal cut (recall the Max Flow/ Min Cut theorem)?

I know that the set of edges might not be unique, but what I want is to determine one set of edges (of the possible solutions) that will give me the minimal cut.

In problems like image segmentation, determining the actual edges that form the cut is necessary to determine to which segment a certain pixel belongs to.

Finding the saturated edges isn't enough: there might be saturated edges that do not belong to the cut. (https://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on-a-graph-using-a-maximum-flow-algorithm)

Answer 1

Let $s$ and $t$ denote the source and the sink of your network.

Remove all saturated edges from the graph $G$. Then $s$ and $t$ will be disconnected (otherwise you could find an augmenting path).

Now it is easy to show that the edges leaving the connected component containing $s$ will form a min cut. The connected component can be found in linear time by using BFS.