Lecture 21 - Notes

March 31, 2016

Max Flow & Mincut

Mincut

definition: Given an edge weighted digraph with source $s$ and sink $t$, we define,

• $st$-cut is a partition of two disjoint sets, with $s$ in one set $A$ and $t$ in the other set $B$.
• Capacity is the sum of the capacities of the edges from $A$ to $B$.

The problem is to find a cut of minimum capacity.

Max Flow

definition: Given an edge weighted digraph with source $s$ and sink $t$, an $st$-flow is an assignment of values to the edge such that,

• Capacity, $0 \le \text{edge's flow} \le \text{edge's capacity}$
• Equilibrium, The inflow equals the outflow at every vertex except $s$ and $t$.

The value of a flow is the total inflow at $t$. The problem is to find the maximum value.