The Maximum Flow Problem

From IFORS Education Resources
Jump to: navigation, search

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.

Definition 1

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


Personal tools