# 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)∈V$ has a nonnegative capacity $c(u,v)$.

A flow network satisfies the following constraints:

- Capacity Constraint: For all $u,v∈V$, $f(u,v)≤c(u,v)$
- Flow Conservation: For all $u∈V−{s,t}$, $∑_{v∈V}f(u,v)=0$
- Skew Symmetry: For all $u,v∈V$, $f(u,v)=−f(v,u)$

### Max-Flow, Min-Cut Theorem

The following are equivalent:

- $∣f∣=c(S,T)$ for some cut $(S,T)$
- $f$ is a maximum flow
- $f$ admits no augmenting paths

### Related

Applications

- Baseball Elimination
- Bipartite Matching