# Network Flow

Flow network.

• Abstraction for material flowing through the edges.
• G = (V, E) = directed graph, no parallel edges. 【简单图】
• Two distinguished nodes: s = source, t = sink.
• c(e) = capacity of edge e.

Def：

An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B

The capacity of a cut (A, B) is: $cap(A, B) = \sum_\text{e out of A} c(e)$

## Minimum Cut Problem

Min s-t cut problem. Find an s-t cut of minimum capacity.

Def：

An s-t flow is a function that satisfies:

• For each e ∈ E: $0 \leq f(e) \leq c(e)$ [capacity]
• For each v ∈ V – {s, t}: $\sum_\text{e in to v} f(e) = \sum_\text{e out of v} f(e)$ [conservation]

The value of a flow f is: $v(f) = \sum_\text{e out of s} f(e)$

## Maximum Flow Problem

Max flow problem. Find s-t flow of maximum value

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut.Then, the net flow sent across the cut is equal to the amount leaving s.$$\sum_\text{e out of A} f(e) - \sum_\text{e in to A}f(e) = v(f)$$**Weak duality.** Let f be any flow, and let (A, B) be any s-t cut. Then thevalue of the flow is at most the capacity of the cut.

Corollary:

Let f be any flow, and let (A, B) be any cut.

If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.

## Residual Graph

Original edge: e = (u, v) ∈ E.

• Flow f(e), capacity c(e)

Residual edge:

"Undo" flow sent.

e = (u, v) and $e^R$ = (v, u)

Residual capacity:$$\begin{equation}c_f(e)=\left{\begin{array}{lr}\text{c(e) - c(f),}&\quad\text{if e ∈ E,}\f(e) &\quad if e^R ∈ E.\end{array}\right.\end{equation}$$

Residual graph: $G_f = (V, E_f)$

• Residual edges with positive residual capacity.
• $E_f = {e : f(e) < c(e)} \cup {e^R : f(e) > 0}$.

Def:

• An augmenting path is a simple s->t path in the residual graph $G_f$

• The bottleneck capacity of an augmenting path P is the minimum residual capacity of any edge in P.

Key property. Let f be a flow and let P be an augmenting path in $G_f$,then after calling $f' \leftarrow Augment(f,c,P)$, the resulting f’ is flow and$$v(f’) = v(f) + bottleneck(G_f,P)$$

## Max-Flow Min-Cut Theorem

• Augmenting path theorem: Flow f is a max flow iff there are no augmenting paths.
• Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut