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:

Personal tools