Flow Network

Definition

• capacity function: $c(u,v)\ge 0$
• source $s$ and sink $t$, so that $\exists s⇝v⇝t$ $\forall v\in V$.
• flow: $f:V\times V\to \mathbb{R}$
  • $0\le f(u,v)\le c(u,v)$
  • $\sum _{v\in V}f(v,u)=\sum _{v\in V}f(u,v)\forall u\in V-\{s,t\}$
  • $f(u,v)=0\forall (u,v)\notin E$
• supersource and supersink