Are all minimum cuts on a graph equivalent?

616 Views Asked by At

In my discrete math class, our professor is insistent on using a labeling algorithm to find the max flow of a graph. This is fine, although the Ford-Fulkerson algorithm makes more sense to me. When the labeling algorithm terminates, it has the side-effect of giving us sets $P$ and $\bar{P}$ separated by a minimum cut based on which vertices have been labelled when the algorithm terminates. My understanding is that the Ford-Fulkerson algorithm won't provide a specific minimum cut, but will give you the min-cut value.

Are all minimum cuts equivalent, at least in these small introductory problems?

Extra question: I can't even begin to think of how I'd make this rigorous, but would it be reasonable to say that the final residual graph given by the Ford-Fulkerson algorithm could give us minimum cut sets $P$ and $\bar{P}$ based on where the path from $s$ to $t$ breaks down on the saturated edges?

1

There are 1 best solutions below

0
On

I'm not sure what you mean by "equivalent", but there may be many different minimum cuts. As an extreme example, if your graph consists of a source $s$, sink $t$, and $n$ other vertices each having an edge from $s$ of weight $1$ and an edge to $t$ of weight $1$, then all of the $2^n$ possible cuts are minimum cuts of value $n$. But all minimum cuts have the same value, by definition.