Flows and Cuts

We are interested in two problems:

• Finding a maximum flow: What is the maximum amount of flow we can send from a node to another node?
• Finding a minimum cut: What is a minimum-weight set of edges that separates two nodes of the graph?

Flow Network

A flow network is a directed graph $G=(V,E)$ with two distinguished vertices: source $s$ and sink $t$. Each edge $(u,v)\in V$ has a nonnegative capacity $c(u,v)$.

A flow network satisfies the following constraints:

• Capacity Constraint: For all $u,v\in V$, $f(u,v)\le c(u,v)$
• Flow Conservation: For all $u\in V-\{s,t\}$, ${\sum }_{v\in V}f(u,v)=0$
• Skew Symmetry: For all $u,v\in V$, $f(u,v)=-f(v,u)$

Max-Flow, Min-Cut Theorem

The following are equivalent:

1. $|f|=c(S,T)$ for some cut $(S,T)$
2. $f$ is a maximum flow
3. $f$ admits no augmenting paths

Related

• Ford-Fulkerson Method

Applications

• Baseball Elimination
• Bipartite Matching