## 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

 Home Moll575 Web View Edit Account
Copyright © 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