Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:camille:chapter7 [2011/04/05 04:24] – [Section 3: Choosing Good Augmenting Paths] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter7 [2011/04/05 04:39] (current) – [Section 2: Max Flows and Min Cuts in a Network] cobbc
@@ Line 13: / Line 13: @@
     * **Summary:**
+This section is an analysis of the Ford-Fulkerson algorithm. They show that the flow is the max possible value for any flow in the graph. If you divide the nodes into two sets A and B such that s is in A and t is in B, then the capacity of the cut is the sum of the capacities of the edges out of A. Cuts provide upper bounds on the values of flows. v(f) = fout(A)-fin(A). They go on to show that the max flow is upper bounded by the capacity of every cut, so there can't be a cut with value less than the flow. In order to show that the flow is the maximum psosible value of any flow in G, we use this fact. We show that there's some cut where the flow is equal to the value of the cut. That means that the flow is max and that that particular cut is min. They prove that this is the case and that this is all that's necessary to show that F-F is optimal. The residual graph from F-F will also give us the min cut pretty directly. It's all of the nodes reachable from s. There's a flow and a cut in every flow network such that their values are equal (pretty cool!), and the max value of an s-t flow is equal to the capacity of an s-t cut in every flow network. Integers vs. real numbers: for rational numbers, you can multiply by some constant to turn the whole thing into integers. No biggie. But irrational numbers create a little bit more of a problem (ok ... a big problem): the F-F might not terminate! But the max-cut-min-flow thing still works. In real problems, there wouldn't be irrational numbers, but the F-F can take a long time to complete if we don't make good choices of augmenting paths. That's improved upon in the next section.
     * **Questions and Insights:**
@@ Line 19: / Line 19: @@
     * **Readability:**
-Great :)
+Great :) Except I felt like they kept giving the same facts over and over and over in this section ... they're all so closely related and follow pretty directly from each other.
 ===== Section 3:  Choosing Good Augmenting Paths =====