Lecture Ten: Network Flows

  • Lecture today follows the text fairly closely
  • A network is a loop-free directed connected graph with a unique source (a), sink (z). Arcs have capacities k(e)>=0
  • A flow phi(e) associated with each edge is a real, 0 <= phi(e) <= k(e). Flow is conserved at all nodes (except a, z)
  • Formally, a cut(P,P-bar) is a partition of the nodes. an a-z cut puts a in P, z in P-bar. Capacity of cut (P,P-bar): sum of capacities of edges flowing out of P.
  • Set Flow lemma: P a set of nodes that excludes a, z, then flow into P = flow out of P
  • Bounding lemma: (P,P-bar) any a-z cut. then |phi| -- the flow out of a -- <= k(P,P-bar)
  • |phi| = k(P,P-bar) <=> all outflows are at capacity, all backflows are 0.
  • Thm: Min-cut/Max-flow theorem. The max achievable flow = the capacity of the minimum cut. Pf (Ford-Fulkerson)
  • FF algorithm: (1) start with some feasible solution - e.g. the 0 solution; (2) starting with node a, mark any vertex b adjacent to a as (a+,r), where r is the unused capacity on the arc (a,b), for r > 0; (3) repeat: suppose b is labelled. Given edge (b,c), c unlabelled. If c has unused capacity, mark c as (b+,r), where r is the min of {b's label, unused capacity of e}; If (c,b) an edge, c unlabelled, phi(c,b) > 0, mark c as (b-,r), where r is min of phi(c,b), b's label. Finally, if there is an a-z path of lebelled nodes, auugment phi by working backwards.
  • When FF stops, we have a min cut that equals this flow (and hence the max-flow)
  • FF is computational lousy, screwy. Can be tightened!
  • network flow methods have many, many dramatic applications!

-- RobbieMoll - 10 Oct 2006

Topic revision: r1 - 2006-10-10 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort