# The Maximum Flow Problem

From IFORS Education Resources

**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