07-11-2012, 02:52 PM
Maximum flow
Maximum flow.ppt (Size: 264 KB / Downloads: 82)
Variant
Multiple sources, multiple sinks
Possible maximum flow out of certain sources or into some sinks
Models logistic questions
Finding admissible flow 1
First, we transform the question to: find an admissible circulation
Finding admissible circulation is transformed to: finding maximum flow in network with new source and new sink
Translated back
Circulations
Given: digraph G, lower bounds l, upper capacity bounds c
A circulation fulfills:
For all v: flow into v equals flow out of v
For all (u,v): l(u,v) £ f(u,v) £ c(u,v)
Existence of circulation: first step for finding admissible flow
Finding admissible flow
Find admissible circulation in network with arc (t,s)
Construction: see previous sheet
Remove the arc (t,s) and we have an admissible flow
Matrix rounding problem
p * q matrix of real numbers D = {dij}, with row sums ai and column sums bj.
Consistent rounding: round every dij up or down to integer, such that every row sum and column sum equals rounded sum of original matrix
Can be modeled as flow problem with lower and upper bounds on flow through edges