Graph Theory37 sections · 1633 units
Open in Course

Cut Capacity

(Sum of crossing edges)

The capacity of a cut (S,T)(S, T) is the sum of capacities of all edges going from SS to TT. Edges from TT to SS do not count in a directed graph. Direction matters. For an undirected graph, you count each crossing edge once, regardless of direction.

For a directed graph, only edges leaving SS and entering TT contribute to the capacity. The capacity measures how much flow you need to block to disconnect SS from TT. If you saturate all edges crossing the cut, no more flow can pass through.