### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 796 at KU 4

### View Full Document

## 17

## 0

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

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

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

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.