Flows, connectivity and matching

Definition 3..1 (Flow)  

A flow in a digraph $D$ with source $s$ and sink $t$ is a function $f: E(D) \mapsto \mathbb{R}_{\ge 0}$ such that $f_+(x) = f_-(x)$ $\forall x \in V(D) \setminus \{ s,t \}$ where $f_+(x) = \sum_{y: xy \in E(D)} f(xy)$ (the flow out of $x$) and $f_-(x) = \sum_{y: yx \in E(D)} f(yx)$ (the flow into $x$). Convenient to set $f(xy)=0$ if $xy \notin E(G)$.

Definition 3..2 (Directed edge)  

$xy$ is the directed edge from $x$ to $y$. Loops and multiple edges are forbidden, so certainly $f(xy)=0$ or $f(yx) = 0$.

Observation 3..3  

We imagine $f$ as representing a flow of water or electricity in a network, being pumped in at $s$, and being pumped out at $t$. The condition $f_+(x) = f_-(x)$ expresses that flow is conserved at each vertex.

Definition 3..4 (Value of the flow)  

$v(f)=f_+(s)-f_-(s)=f_-(t)-f_+(t)$ is called the value of the flow where $s$ is the source and $t$ is the sink.

Definition 3..5 (Net flow)  

Let $S \subseteq V(D)$ with $s \in S$ and $t \notin S$. Let $\bar{S} = V(D) \setminus S$. The net flow from $S$ to $\bar{S}$ is $f(S,\bar{S}) = \sum_{x \in S,y \in \bar{S}}(f(xy) - f(yx))$.

Since $\sum_{x,y \in S}(f(xy) - f(yx)) = 0$ we get $f(S,\bar{S}) = \sum_{x \in S,y \in V}(f(xy) - f(yx)) = \sum_{x \in S}(f_+(x) - f_-(x)) = f_+(s) - f_-(s) = v(f)$.

Definition 3..6 (Capacity function)  

Given a capacity function $c: E(D) \mapsto \mathbb{R}_{\ge 0}$ we require that $0 \le f(xy) \le c(xy)$ for all $xy \in E(D)$.

Definition 3..7 (Cut)  

Let $S \subseteq V(D)$ with $s \in S$ and $t \notin S$. Let $\bar{S} = V(D) \setminus S$. The set of edges $E(S,\bar{S}) = \{ xy \in E(D) : x \in S, y \in \bar{S} \}$ is called a cut with capacity $c(S,\bar{S}) = \sum_{x\in S,y \in \bar{S}} c(xy)$.

For any cut we have $v(f) = f(S,\bar{S}) \le c(S,\bar{S})$.

Theorem 3..8 (Max-flow min-cut (MFMC))  

The maximum value of a flow (source $s$ and sink $t$) in a network is equal to the minimum cut capacity.

Proof. The maximum flow in a network is less than or equal to the minimum cut capacity. Let $f$ be a flow. We construct $S \subseteq V(D)$. Initially let $S = \{ s \}$. Then put $y \in S$ if either $\exists x \in S: f(xy) < c(xy)$ or $\exists x \in S$ with $f(yx) > 0$. Repeat.

If $t \in S$ then there is a sequence of vertices starting with $s = y_0, y_1,\cdots, y_k = t$ where for each $1 \le i \le k$ either $c(y_{i-1},y_i) - f(y_{i-1},y_i) = \delta_i > 0$ or $f(y_i,y_{i-1}) = \delta_i > 0$. Let $\delta = min_{1 \le i \le k} \delta_i$. We construct a new flow $f: E(D) \mapsto \mathbb{R}_{\ge 0}$ equal to $f$ except on the $s-t$ path but with $f'(y_{i-1},y_i) = f(y_{i-1},y_i) + \delta$ or $f'(y_i,y_{i-1}) = f(y_i,y_{i-1}) - \delta$ as appropriate. $f'$ is a flow. $v(f') = v(f) + \delta$ so $f$ was not maximal, contradiction.

Algorithm increases. Take a subsequence monotonic on each edge. Take the limit. This flow has value of limit so it is maximal.

If $t \notin S$. Let $\bar{S} = V(D) \setminus S$. $E(S,\bar{S})$ is a cut. For every $xy$ with $x \in S$ and $y \in \bar{S}$ we have $f(xy) = c(xy)$. For every edge $yx$, $x \in S$ $y \in \bar{S}$ we have $f(yx) = 0$. $v(f) = f(S,\bar{S}) = \sum_{x \in S, y \in \bar{S}}(f(xy)-f(yx)) = \sum_{x \in S, y \in \bar{S}} c(xy)$. That is, the value of the flow is the cut capacity of some cut.

$\qedsymbol$

Corollary 3..9 (Integrability theorem)  

In a network with integer valued edge capacities there is a maximal flow whose value is equal to the minimum cut capacity, which has integer values at each edge.

Proof. Follow MFMC starting with the zero flow. Then $\delta$ is always integer.

$\qedsymbol$

Observation 3..10  

Note that there may be a maximal flow which is not integer valued on each edge.

Definition 3..11 (Multiple sinks and sources)  

Consider multiple sources $s_1,\cdots,s_k$ and multiple sinks $t_1,\cdots,t_k$. The value of the flow is $v(f) = \sum_{i=1}^{k}(f_+(s_i)-f_-(s_i)) = \sum_{j=1}^{l}(f_-(t_j)-f_+(t_j))$ and a cut is $E(S,\bar{S})$ where $s_1,\cdots,s_k \in S$ and $t_1,\cdots,t_k \in \bar{S}$.

Corollary 3..12 (MFMC for multiple sources and sinks)  

In a multiple source network the maximum value of a flow is equal to the minimum cut capacity.

Proof. We construct a new network by joining a supersource $s$ to $s_1,\cdots,s_k$ and a supersink $t$ to $t_1,\cdots,t_l$ using edges of infinite capacity.

Apply MFMC. Note that any cut of finite capacity cannot touch edges $s s_i$ or $t_j t$ so cut can be applied to original graph.

$\qedsymbol$

Definition 3..13 (Vertex capacities)  

We can consider vertex capacities instead of edge capacities. The capacity function is now $C : V(D) \setminus \{ s,t \} \mapsto \mathbb{R}_{\ge 0}$ and we want $0 \le f_+(v)=f_-(v) \le c(v)$ $\forall v \in V(D) \setminus \{ s,t \}$. A cut is now a set of vertices $S$ such that $D-S$ has no $s-t$ path. It has capacity $\sum_{v \in S} c(v)$.

Corollary 3..14 (Vertex capacity version of MFMC)  

The maximum value of a flow in a network with vertex capacities is equal to the minimum cut capacity.

Proof. Construct from $D$ a new network $D'$ with edge capacities. Replace each vertex $v$ by two vertices $v_-$ and $v_+$ and an edge $v_-v_+$. For each edge $xy \in E(D)$ add an edge $x_+y_-$ to $D'$. We give $v_-v_+$ capacity $c(v)$ give $x_+y_-$ infinite capacity. Apply MFMC.

$\qedsymbol$