Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:paul:home [2012/04/04 17:00] – [Chapter 6] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 01:19] – [Chapter 7] nguyenp | ||
---|---|---|---|
Line 744: | Line 744: | ||
* Locally optimal, but not globally optimal (it's very easy to think of a counter example, counter example is on page 339 in book) | * Locally optimal, but not globally optimal (it's very easy to think of a counter example, counter example is on page 339 in book) | ||
* Awesome Solution: Residual Graphs | * Awesome Solution: Residual Graphs | ||
+ | * Edges have a capacity, but also a flow | ||
+ | * We don't have to use all of it at once | ||
+ | * Residual edge is one where you have some going one way and some going the other | ||
+ | * The Ford-Fulkerson Algorithm uses residual edges and works awesomely (optimal) | ||
+ | * page 342 - 344 | ||
+ | * Informal explanation | ||
+ | * graphs | ||
+ | * keep updating the residual edges using the following formula: | ||
+ | * If edge is the same as it was originally, set the forward rate to the bottle neck + original rate (which is the edge with the smallest flow rate) | ||
+ | * Otherwise, set the backwards residual rate to what it originally was minus the bottle neck | ||
+ | * Section 7.2 - Maximum Flows and Minimmum Cuts in a Network | ||
+ | * Cut: s-t cut is a partition (A,B) where s is in A and t is in B | ||
+ | * Problem: Find an s-t cut of minimum capacity | ||
+ | * The capacity of a cut is the sum of all the possible stuff that can go through the edge at once | ||
+ | * Flow Value Lemma: Let f be any flow, and let (A, B) be any s-t cut. Then, the value of the flow is = f_out(A) – f_in(A). | ||
+ | * Weak Duality: let f be any flow and let (A, B) be any s-t cut. Then the value of the flow is at most the cut’s capacity. | ||
+ | * Corollary: Let f be any flow, and let (A, B) be any cut. If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut | ||
+ | * |