Graph Theory37 sections · 1633 units
Open in Course

Cuts and Capacity

(Partitioning the graph)

A cut divides the nodes into two sets SS and TT, where the source is in SS and the sink is in TT. The capacity of the cut is the sum of capacities of edges going from SS to TT. Edges from TT to SS do not count toward cut capacity.

Only forward edges (from SS to TT) matter. Every flow from source to sink must cross the cut. So the flow value is at most the cut capacity. This is true for every cut.