Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

Question

I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network.

For example, in the baseball elimination problem, if we wanted to find out if team z is eliminated, the min cut represents the team(s) that will beat team z out of the 1st place if the edges aren't full saturated. If the edges are fully saturated, then min-cut is everything except t, and team z still has a chance.

For the project selection, the min cut contains the projects you should do to maximize your return.

How do people figure out that min-cut can be applied to these problems? What is it about min-cut that gives it such power?

Thank you!

Answer 1

Given a weighted directed graph and two nodes $s,t$, an $s$-$t$ cut is a set of edges, upon whose removal $t$ is not reachable from $s$. The weight of the cut is the total weight of edges removed. A minimum $s$-$t$ cut is one of minimum weight.

A similar definition works for undirected graphs and in the special case in which the graph is unweighted, in which all edges have unit weight.

If we think of a weighted digraph as a flow network with source $s$ and sink $t$, then any $s$-$t$ cut gives a restriction on the weight of any flow in the network, which must be at most the weight of the cut. The min cut max flow theorems states that the weight of a minimum $s$-$t$ cut coincides with the weight of the maximum flow. However, a cut and a flow are two very different things.

There's a related definition of cut which works just for undirected graphs. A cut in an undirected graph is a set of edges whose removal disconnects the graph. (Any $s$-$t$ cut is a cut.) A minimum cut is one of minimum total weight (or, in the unweighted case, of minimum cardinality).

One reason that cuts are so powerful is that they can be found efficiently.