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/03/28 01:57] – [Chapter 6] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 01:54] – [Chapter 7] nguyenp | ||
---|---|---|---|
Line 731: | Line 731: | ||
* Weird stuff. Never thought algorithms like this existed. | * Weird stuff. Never thought algorithms like this existed. | ||
* | * | ||
+ | |||
+ | ====== Chapter 7 ====== | ||
+ | * Section 7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm | ||
+ | * Problem | ||
+ | * You have a directed graph | ||
+ | * Each edge has a capacity | ||
+ | * Have a start node s and end node t | ||
+ | * Greedy | ||
+ | * Find an s-t path with highest capacity | ||
+ | * do it! | ||
+ | * keep doing this until you cant do it any more | ||
+ | * 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 | ||
+ | * 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 | ||
+ | * Augmenting path theorem: Flow f is a max flow iff there are no augmenting paths | ||
+ | * Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. | ||
+ | * More explanation on page 350 | ||
+ | * Boom and we are done. Just use the same stuff as in the past section and we have all we need. | ||
+ | * Section 7.5 - A First Application: | ||
+ | * Given an undirected bipartite graph | ||
+ | * We must match so each node appears at most once on each edge | ||
+ | * How do we find one with the max number of nodes? This is our problem. | ||
+ | * Here's how we do it. We got a bunch of red and blue nodes. Add nodes s and t, which will be the start and end nodes. Have the start node s have a unit edge (edge of size 1) connect it to all the red nodes. Have all the blue nodes have a unit edge connect them to the end node t. Still have same edges in the middle. | ||
+ | * Now, use same algorithm as in the first section. BOOOM!!! Right? Yep. It's pretty intuitive, these later sections are more like practical uses rather than actual algorithms. I guess this is kind of good since pretty much all computer science problems go back to graph theory. | ||
+ | * Extensions: The structore of bipartite graphs with no perfect matching | ||
+ | * Dicusses how to tell if it is impossible to find a perfect matching in a bipartite graph. | ||
+ | * Can easily find an algorithm based on the following theorem: | ||
+ | * Assume that the bipartite graph G=(V,E) has two sides X and Y such that |X| and |Y|. Then the graph G either has a perfect matching or these is a subset A such that |\G(A)|< | ||
+ | * Section 7.7 - Extensions to Max-Flow Problem | ||
* | * |