Flow Networks

Summarized notes on Introduction to Algorithms, Chapter 26

consider some source that produces material and some sink that consumes it
- flow represents the the rate at which material moves through a system
- each edge in system is a conduit for the material
- each conduit has maximum capacity
- vertices are conduit junctions and does not collect in these junctions
- rate of entry = rate of exit → flow conservation
Maximum flow problem: compute the greatest rate at which material can be shipped from source without violating capacity constraints

directed graph $G = (V, E)$ where
- each edge has nonnegative capacity $c (u, v) \geq 0$
- if $E$ contains edge $(u, v)$ there is no edge $(v, u)$ in reverse direction
- if $(u, v) \notin E$ then $c (u, v) = 0$
- edges are labelled as flow/capacity → flow $\leq$ capacity
- self-loops are not allowed
two special vertices: source $s$ and sink $t$
all vertices connected, $E \geq V - 1$
flow in $G$ is a real-valued function that satisfies
1. capacity constraint: for all $(u, v) \in V$ , $0 \leq f (u, v) \leq c (u, v)$
2. flow conservation: for all $u \in V - {s, t}$ :
  $\sum_{v \in V} f (v, u) = \sum_{v \in V} f (u, v)$
value of flow is defined as $ $| f | = \sum_{v \in V} f (v, u) - \sum_{v \in V} f (u, v)$ $
maximum flow problem: given $G$ and $s$ and $t$ , find flow $f$ with maximum value

Antiparallel edges

antiparallel edges violate constraint $(u, v) \in E \to (v, u) \notin E$
if antiparallel exist, transform network into an equivalent without antiparallel edges
- choose one edge and add new vertex $v^{'}$
- replace $(v_{1}, v_{2})$ with $(v_{1}, v^{'})$ and $(v^{'}, v_{2})$
- set same capacity as original edge

if multiple sources and sinks → convert to network with one source and sink
add supersource $s$ :
- add directed edge $(s, s_{i})$ with capacity $c (s, s_{i}) = \infty$ for each $i = 1, 2, . . ., m$
add supersink $t$ :
- add directed edge $(t_{i}, t)$ with capacity $c (t_{i},) = \infty$ for each $i = 1, 2, . . ., n$