Class Note for MATH 796 at KU 4
Popular in Course
Popular in Department
This 4 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 17 views.
Reviews for Class Note for MATH 796 at KU 4
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Friday 328 Network Flows De nition A network is a directed graph N V E with the following additional data 0 A distinguished source 3 E V and sink t 6 V o A capacity function 5 z E A N We want to think of an stnetwork as modeling a situation where stuff data traf c liquid electrical current etcriis owing from s to t The capacity of an edge is the amount of stuff that can ow through it or perhaps the amount of stuff per unit time This is a very general model that can be specialized to describe cuts connectivity matchings and other things in directed and undirected graphsi A ow on N is a function f z E A N that satis es the capacity constraints 1 0 S fe S Ce V6 6 E and the conservation constraints lt2 u 1 vv 6 v at where M Z fe7 fltvgt Z fe 213 21W That is stuff cannot accumulate at any internal vertex of the network nor can it appear out of nowhere The value of a ow f is the net ow into the sink lfl f t ft f8 f 8A The second equality follows from the conservation constraintsi Typically welll assume that there are no edges into the source or out of the sink so that lfl f t f8 Problem Given a network nd a ow of maximum value Observation If we can nd a path from s to t in which no edge is being used to its full capacity then we can increase the ow along every edge on that path and thereby increase the value of the ow by the same amount 01 01 01 10 11 10 01 10 01 11 01 01 0 m1 The problem is that some ows cannot be increased in this way but are nevertheless not maximal The ow on the right above is an example In every path from s to t there is some edge 6 with fe 06 However the ow shown below evidently has a greater value namely 2 Observation Flow along an edge I can be regarded as negative ow from y to 1 Accordingly there is another way to increase owi Look for a path from s to t consisting of forward edges not being used to full capacity OR backward edges with positive owi Then increasing ow on the forward edges and decreasing ow on the backward edges will increase the value of the owi 01 11 11 10 01 11 m1 2 The FordFulkerson Algorithm lnput A network N V E with source 8 sink t and capacity function 5 z E A Ni 1 Let f be the zero flow fe 0 for all edges 6 2 Find an augmenting path ie a sequence of vertices PI 10 87 117 127 m7 171717 I such that for every 239 i 0 i i i n 7 l we have either 0 ei 111141 6 E and fei lt CEi 6 is a forward edge or o ei 114111 E E and fei gt 0 6139 is a backward edge 3 De ne f z E A N by Re fe 1 if 6 appears forward in P e fe 7 1 if 6 appears backward in P and fe fe if e g Pl Then it is easy to verify f satis es the capacity and conservation constraints and that li 4 Repeat steps 2 until no augmenting path can be found The next step is to prove that this algorithm actually works That is when it terminates it will have computed a flow of maximum possible value Cuts The dual problem to nding a maximum flow is nding a minimum cutl De nition Let N V E be an stnetworkl Let ST C V with S UT V S T 0 s E S andt 6 Ti The corresponding cut is ST 36E sEStES and the capacity of that cut is CS T 2 06 eEE For example in the network at which we have been looking we could take 5 8 a c T bdt as A A A followsi Then 5T abad Cd and C5 T 1 2 1 4i A cut can be thought of as a bottleneck through which all ow must pass ForACV de ne f A Z fefA Z fe eeAA eew l Proposition 1 Let f be aflow and let A Q V Then 3 fA f A ZUWU 7 f v veA In particular 5T is a cut then 3b f57f 5 f T7fT lfl 30 lfl S CS7T In particular the maximum value of a ow is less than or equal to the minimum capacity of a cut a principle known as weak duality Proof We just need some careful bookkeeping For 3a lt Z fe Z fegtlt Z fe Z 1 eEAA egAA eeAA eeAA lt Z M 7 lt Z M 2175 veA 21W veA Z fe 7 Z fegt Zltfltvgterltvgtl veA 81m 81W USA fA f A For 3b the conservation constraints 2 together with 3a imply that f5f 5 Zltfvf v f8f 8 lfl f tft f TfTA veS For 3c the capacity constraints 1 imply that lfl f5f 5 S f5 E Z 66 CS7T eEST Proposition 2 Suppose that f is a flow that has no augmenting path Let S v E V l there is an augmenting path from s to v T V S Then s E S t E T and C5 T In particular f is a maximum flow and 5 T is a minimum cut Proof Note that t g S precisely because f has no augmenting path By 3b we have m News Z fe Z fe Z e eES eE S eES But fe Ce for every e E 5T otherwise 5 would be bigger than what it actually is so this last quantity is just CST The nal assertion follows by weak duality D We have proven Theorem 3 For any network N the FordFulkerson Algorithm terminates in nite time and outputs a maximum flow f and a minimum cut 5T such that CS T
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'