# March 4. Maximum flow and minimum cut I

Flow

Let $D = (V, A)$ be a directed graph where every edge $(i, j)$ has a capacity $c_{ij} \in \mathbb{Z}_+$. We are given two special vertices $s,t$ where $s$ is the source vertex and $t$ is the sink vertex.  A flow in $D$ is defined as function $f: A \rightarrow \mathbb{Z}_+$ where $0 \le f_{ij} \le c_{ij}$. Further for every node $v \notin \{s, t\}$ we have the following conservation property: $\sum_{j: (j, i) \in A} f_{ji} = \sum_{j: (i, j) \in A} f_{ij}$. In other words for every vertex that is not the source or the sink, the net incoming flow is the same as the net outgoing flow.

The value of the flow is given by $val(f)=\sum_{j: (s, j) \in A} f_{sj} - \sum_{j: (j, s) \in A} f_{js}$. We claim that $val(f) = \sum_{j: (j, t) \in A} f_{jt} - \sum_{j:(t, j) \in A} f_{tj}$. To see this consider a matrix where the rows are indexed by vertices and the columns are indexed by the edges. For any vertex $v$ and edge $(x, y)$ the entry $(v, (x, y))$ is equal to either $f_{vy}$ if $x=v$ and is equal to $- f_{xv}$ if $v=y$. Otherwise the entries are 0. Note that the sum of the entries in a particular row gives us the net flow out of that vertex. Clearly the columns sum up to $0$. Since the net flow for every vertex not equal to $s,t$ is $0$ the claim follows.

s-t Cut

An $s-t$ cut is a subset $S$ of edges such that $A\setminus S$ has no directed path from $s$ to $t$ in $D$. We claim that the maximum number of $s, t$ edge disjoint paths in $D$ is the same as the size of the minimum $s, t$ cut. Clearly the maximum is always less than the minimum. Menger’s theorem says that equality is attained, i.e. the maximum number of edge disjoint $s, t$ path is equal to the size of the minimum $s, t$ cut.

Thus our cut only consists of edges of the form $(s, v)$ and $(v, t)$. Define a flow $f(i) = \min\{d_{in}(i), d_{out}(i)\}$.

Claim: The maximum $s,t$ flow in any graph $D$ is less than or equal to the capacity of the $s,t$ minimum cut.  The capacity of a cut $(S, \bar{S})$ is defined as $c(S, \bar{S}) = \sum{i\in S, j\in \bar{S}} c_{ij}$.

Proof: Note that $f(s, V) - f(V, s) = val(f)$. For every $x\neq s,t$ we have $f(x, V) - f(V, x) = 0$. Let us add up all the vertices in $S$. We get $f(S, V) - f(V, S) = val(f)$. However $f(S, V) = f(S, S) + f(S, \bar{S})$. Thus $f(S, \bar{S}) - f(\bar{S}, S) = val(f)$. This proves the claim.