程序代写代做代考 CSC373H Lecture 7

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.