The Maximum Flow Problem
By: Erik Demaine and David Karger
In this section we define a flow network and setup the problem we are trying to solve in this lecture: the maximum flow problem.
A network is a directed graph G = (V,E) with a source vertex s ∈ V and a sink vertex t ∈ V . Each edge e = (v,w) from v to w has a defined capacity, denoted by u(e) or u(v,w).
It is useful to also define capacity for any pair of vertices (v,w) 6∈ E with u(v,w) = 0.
Link to material: http://courses.csail.mit.edu/6.854/06/scribe/s9-maxflow.pdf