Flow Network

Definition

• A directed graph $G=(V,E)$
• Each edge $(u,v)\in E$ has capacity $c(u,v)\ge0$
• Source: $s$; Sink: $t$
• Flow $f(u,v):V\times V\to R$
• Total flow: $|f|=\sum_{v\in V} f(s,v) - \sum_{v\in V} f(v,s)$

Analogy

• A massive pipe network
• Capacity of each pipe
• $s$ = inlet; $t$ = outlet
• Flow through that pipe
• Net flow out of source

Constraints

• Capacity Contraint（容量限制）: $f(u,v)\le c(u,v)$
• Skew Symmetry Constraint（反对称性）: $f(u,v) = -f(v,u)$
• Flow Conservation（流守恒性）: $\sum_{v\in V}f(u,v)=0, \forall u\in V-\{s,t\}$
  • For all nodes except sink and source, incoming flow = outgoing flow

Remodeling

• Antiparallel Edges

  • $\because$ skew symmetry constraint
  • $\therefore$ can’t have $(v_1,v_2)$ and $(v_2,v_1)$ at the same time
  • $\therefore$ Remodel $(v_1, v_2)\to(v_1,v'),(v',v_2)$

  

• Flow Cancellation

  • $\because$ skew symmetry constraint
  • $\therefore$ 2 flows $(u,v)(v,u)$ can be combined into $f(u,v) = f(u,v)-f(v,u)$
  • $\therefore$ Add flow $(u,v)$$f(u,v)+d \to f(v,u)-d$

• Multiple Sources / Sinks

  • Add supersource $s$; $c(s, s_i) = \infin, s_i\in\{s_1, s_2, ... ,s_n\}$
  • Add supersink $t$; $c(t_i, t) = \infin, t_i\in\{t_1, t_2, ..., t_n\}$

  

Ford-Fulkerson Algorithm

Residual Network

Definition

• Residual Network $G_f$

• Residual Capacity $c_f(u,v)=c(u,v)-f(u,v)$

  $$ c_f(u, v) = \begin{cases} c(u, v) - f(u, v) & \text{if } (u, v) \in E, \\f(v, u) & \text{if } (v, u) \in E, \\0 & \text{otherwise}.\end{cases} $$

Explanation

为方便写最大流算法而存在

$c_f(u,v)$即$u\to v$之间 可压入的额外流量

对于反向边, 其$c_f$可以理解为把正方向上的流量给抵消掉。所以正方向上的流量$c_f(v,u)$即是反方向的$c_f$

Augmenting Path

Definition

• Augmenting Path $p$
• A simple path from $s\to t$ in the residual network $G_f$