### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Special Topics MAT 180

UCD

GPA 3.88

### View Full Document

## 28

## 0

## Popular in Course

## Popular in Mathematics (M)

This 17 page Class Notes was uploaded by Otilia Murray I on Tuesday September 8, 2015. The Class Notes belongs to MAT 180 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 28 views. For similar materials see /class/187391/mat-180-university-of-california-davis in Mathematics (M) at University of California - Davis.

## Reviews for Special Topics

### 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: 09/08/15

Mathematics for Decision Making An Introduction Lecture 13 Matthias KOppe UC Davis Mathematics February 17 2009 Reminder Flows in networks General structure Flows in networks 0 In general consider adigraph directed graph VA where a V is a set ofvertices o A is a set of directed arcs which are ordered pairs ab 6 V X V with a b no loops We call two designated vertices r s e V the source and the sink An r s flow x is a vector of real values X4 for every arc a b e A such that in every vertex except for source r and sink 5 flow conservation constraints are satisfied fxb Z Xabe Z bec o for b e v b y rs a6 V c ab6A bc6A We call fxb the excess of the flow x at vertex b The excess fxs at the sink is called the value of the flow x note fxs ifxr Often capacities uayb are given ie upper bounds on the flow values qab We call a flow x feasible if it is nonnegative and respects the upper bounds if given 34 inder Flows in networks ll Maximum ow problem Given a digraph VA source r sink s arc capacities ugh Find a feasible flow x of maximum value fxs Minimumcost rs ow problem Given adigraph VA source r sink s arc capacities ugh perunit costs cab and aflow value 1 Find afeasible flow x of value fxs q that has minimum total flow costs cabxau Note that it is essential to use the excess function fx at the sink s if we want to measure or prescribe the flow value If we just determine the amount of incoming flow the flow model is not correct Disconnected solutions are possible We now turn to study the maximum flow problem We will discuss an optimality criterion strong duality theory maxflow mincut and combinatorial algorithms to compute the maximum flow z I Demolition We have interpreted an integer rs flow of value 1 as a path from r to s plus circulations when we modeled the shortestpath problem as a minimumcost flow Lemma Integer oWs a s39 path packing39s39 There exists a family P1Pk of directed paths from r to s in V A with li ab 6 Pl g uab forallab EA if and only if there exists a feasible integral rs flowx of value K Proof When we add up unit path flows along the P we clearly get afeasible integral rs flow of value K It remains to show the converse o If there is any directed circuit C with Xab gt O for all arcs a b E C then construct a new feasible flow x by reducing the arc flows along this cycle by 1 or by minXab a b e C Continue until no such directed circuit exists 0 If K gt 0 follow a path starting from r through arcs a b with Xayb gt 0 We never get stuck due to flow conservation and finally reach s Call this simple path Pk Subtract the path flowfrom x and continue Q Flows Decomposition into Paths and Cycles II For general flows we have Every rs flow of nonnegative value is the sum of at most m lAl flows each of which is a path flow or a circuit flow These decomposition results give us a natural idea how to construct a maximum flow 0 Start with the zero flow x 0 0 Send flow along a path from source to sink 0 Repeat until there is no path with positive bottleneck capacity Unfortunately this fails While we can decompose flows into paths by using arbitrary paths one at a time we cannot construct a maximum flow by packing arbitrary paths We either need to look ahead or use a different idea that allows us to continue it we get stuck a An important idea is to consider also paths P from r to s that include arcs in the wrong direction so these paths P are not directed paths 0 We call these arcs reverse arcs as opposed to forward arcs o For a given flow x we shall call a path xincrementing if a for every fonNard arc a b E P we have Xayb lt uayb and 0 for every reverse arc ab 6 P we have 0 lt X41 An xincrementing path from r to s is called xaugmenting 0 Why are these paths useful We can 0 increase flow by some 2 gt 0 on all fonNard arcs and a decrease flow by this s on backward arcs The resulting augmented flow a respects the flow conservation constraints a tors small enough is afeasible flow capacities and nonnegativity hold 0 Has a larger flow value We now claim A feasible flow x is maximum if and only if there is no xaugmenting path Optimality Criteria A theorem like this is easiest to prove if we have an optimality criterion that is based on a certificate of optimality o In the case of shortest paths feasible potentials served as optimality certificates 0 Any feasible potential y provided a lower bound for the length of any path from rto v e For an optimal solution of this minimization problem minimumcost paths PV from r to v we could construct a feasible potential namely setting yV to be the cost of PV for which this lower bound was attained So the lower bound matching the value of the feasible solution provided the optimality certificate 0 In the case of maximum flow we should be looking for useful upper bounds with similarly strong properties 0 Let R Q V be a set of vertices Then we call the are set 5F1 ab EA 516 Rb R the cut induced by B Any are set that can be obtained this way is called a cut a An rs cut is a cut induced by a set R with r e R and s R For any rs cu15F1 and any rs flow x mm 7xsv R fxs For any rs cu15F1 and any feasible rs flow x fx5 S quot59 The MaxFlow MinCut Theorem So any rs cut provides an upper bound But we have something much stronger Theorem MaxFlow MinCut Ford Fulkerson 1956 Kotzig 1956 If there is a maximum rs flow fhen maxfxs x is a feasible rs flow minu5R 5R is an rs cut So for an optimal solution of the maximization problem there always exists an rs cut for which the provided upper bound is attained Proof of the MaxFlow MinCut Theorem and the theorem on slide 6 o Bythe Corollary g holds Only need to find one pairx5F1 forwhich holds Let x be a maximum rs flow or aflow without xaugmenting path We define R v e V there is an xincrementing path from r to v Then r e R trivial and s R otherwise xaugmenting path so x not maximum For a b e 5F1 we have Xab ugh for a b e 5 V R we have Xab 0 Otherwise there would be an xincrementing path to b o Bythe Lemma fxs x5R 7x5V FD u5F1 D 0000 Consequences f MaxFlow MinCut If u is integral and there exists a maximum flow there also exists a maximum flow that Is integral Thus integer flow problems are as easy to solve as continuous flow problems This is in contrast to the general situation of linear programs vs integer programs the latter are much harder to solve This integrality property of network flows is one reason why network flow formulations are useful as a modeling tool 0 Among all integral flows pick one of maximum value call it x o If there existed an xaugmenting path then since u is also integral we could increase the flow by an integer amount 0 So x is already a maximum flow D mm Consequences from MaxFlow MinCut Corollary Complementary slackness Letx be a feasible rs flow and 5F1 be an rs out Then x is a maximum rs flowif and only if Xab Uab fora b e 5F1 Xayb 0 fora b e 5VF1 13m Auxiliary directed graphs 0 An algorithm for constructing maximum flows thus repeatedly needs to find xaugmenting paths 5 We already know algorithms for constructing shortest paths so we might want to use them 0 However reverse arcs complicate the picure 0 So let us construct an auxiliary digraph Gx such that finding a directed path from rto s is the same as finding an xaugmenting path in G Constructing the auxiliary digraph Gx from G V A a For any arc a b e Awith Xab lt uab introduce an arc a b in Gx o For any arc b a e A with bea gt O introduce an arc a b in Gx We allow to introduce parallel arcs i342 The Ford Fulkerson Algorithm Ford Fulkerson Maximum Flow Algorithm Input A digraph G VA with arc capacities u vertices r and s Output A maximum flowx and aset R g V inducing a minimum cut 5F1 a Setx0 0 While we find a directed rs path P in the auxiliary graph Gx Determine the xwidth of P s 2 min min uaybixayb a b forward in P minXab a b reverse in P Augment x along P by s 0 Set R to the set of vertices that can be reached by paths from r in Gx i343 Ml 2 T nation E Theorem Termination of the Algorithm If u is integral and there is a maximum flow of value K then the Ford Fulkerson Maximum FIowAlgorithm terminates after at most K augmentations Each of the augmentations increases the flow value by an integer amount D a This also establishes that the Ford Fulkerson Algorithm is a pseudopolynomial algorithm for inputs with integer datathat have a maximum flow By the MaxFlow MinCut Theorem the flow value is the same as some cut capacity so it is at most Zuab a quantity that is polynomial in the given data 0 Examples that really take K augmentations with a specific choice of a sequence of augmenting paths can be easily constructed Moreover if there is no maximum flow the procedure might fail to terminate So we are not completely happy with this basic algorithm A scaling approach with data u2k fork decreasing to 0 leads to a polynomial algorithm we omit the details Even better it turns out that a specific choice of xaugmenting paths which is currently unspecified will lead to a strongly polynomial algorithm 3 000 0 A Strongly Polynomial Time Variant Theorem Dinits 1970 Edmonds Karp 1972 If each augmentation is along a shortest ie minimum number of arcs augmenting path then the algorithm terminates after at most nm l Vl lAl augmentations a To prepare the proof consider an augmentation along a shortest augmenting path P v0 vk of length K leading from flow x to flow x o Denote by dxv w the least number of arcs in a directed path from vto w in the auxiliary digraph Gx we set dxv w 00 it no such directed path exists 9 Since subpaths of shortest paths are shortest we have dxr v iand dxvs K7 i was A Strongly Polynomial Time Variant ll Shortestaugmentingpath augmentations never decrease the length of shortest directed paths in the auxiliary digraph from the source r to any node v and from any node v to the sink s dxrs V 2 dxrs V and dXVv 5 2 dXV7 5 In particular they never decrease the length of a shortest augmenting path dxr s 2 dxr s This lemma implies that shortestaugmentingpath augmentations proceed in stages during which augmenting paths of constant length are used c Augmentations along paths of length 1 possibly none 0 Augmentations along paths of length 2 possibly none 0 Augmentations along paths of length n71 possibly none It now suffices to bound the number of augmentations of each stage in a strongly polynomial way 3 A Strongly Polynomial Time Variant I Let Ztx be the set of arcs a b E A that appear in a shortest xaugmenting path If a shortestaugmentingpath augmentation does not increase the length of a shortest augmenting path ie dxr s dxr s then Ax is a proper subset of Ax Proof of the theorem From the second lemma in each stage there are at most m iAi augmentations per stage From the first lemma there are at most n7 1 stages So in total at most nm augmentations El 347

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

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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