Skip to content

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

Flow Networks

  • 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

img

Antiparallel edges

  • antiparallel edges violate constraint \((u, v) \in E \rightarrow (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

img

Multiple sources and sinks

  • 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\)

img