Graph Theory37 sections · 1633 units
Open in Course

s-t Cut

(Source and sink separation)

An ss-tt cut is a cut where sSs \in S and tTt \in T. It separates the source from the sink. The source and sink are forced to opposite sides of the partition. Every flow from ss to tt must cross this cut. If you remove all edges crossing the cut, no flow can reach tt from ss.

The cut acts as a barrier. The value of the cut is the total capacity of edges leaving SS. This represents the maximum flow that can cross the cut from the source side to the sink side.