CSC373H Lecture 7
Dan Zingaro
November 2, 2015
Flow Networks: Example
Flow Networks: Definition
A flow network is a directed graph G = (V,E) with
A single source vertex s
A single sink vertex t
Nonnegativecapacityc(u,v)foreachedge(u,v)
No antiparallel edges; e.g. network cannot contain both edges (u, v) and (v, u)
Flow in a Network
Let f(u,v) be a value for each edge (u,v) f is a valid flow if it satisfies two properties
It doesn’t violate any of the capacity constraints Forallverticesuandv,0≤f(u,v)≤c(u,v)
Flow in equals flow out
ForeachvertexuinV−{s,t},v:V f(v,u)=v:V f(u,v)
Maximum Flow Problem
The value of a flow is given by the flow out of the source minus the flow into the source
|f|=v:V f(s,v)−v:V f(v,s)
If there is no flow into the source (often true in flow networks),
then the second sum is 0
The maximum flow problem is to find a flow of maximum value
Sample Flow
Edges are labeled with f /c (flow / capacity)
Existing Techniques
Not clear how to productively apply our existing techniques
Brute-force: way too many possible flows to try (product of all edge capacities)
Greedy: not obvious how to add edges and preserve flow conservation
Dynamic programming: what are the subproblems?
Incremental Improvement
Here’s a new idea
Start with any valid flow (e.g. start with 0 flow for each edge) Try to make an incremental improvement
Stop when there is no possible improvement
If we do this properly, we get the Ford-Fulkerson method
Augmenting Paths, Take 1
An augmenting path is a path that increases the value of a flow
Oneideaistofindasimplepathfroms tot intheflow network where f (v) < c(v) for each vertex v on the path
Define the residual (i.e. leftover) capacity for an edge to be r(u, v) = c(u, v) − f (u, v)
Let the residual capacity of a path be the minimum r(u,v) of any edge (u,v) on the path
The idea is to keep finding an augmenting path, adding the residual capacity of each path to corresponding edges in G
Unfortunately, this isn’t guaranteed to yield a maximum flow
Augmenting Paths: Failing Example
Try using the path s,u,w,v,t on this network.