Differences

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

--- courses:cs211:winter2014:journals:emily:entrynine [2014/04/02 06:09] – [Chapter 7.2] hardye
+++ courses:cs211:winter2014:journals:emily:entrynine [2014/04/02 06:22] (current) – [Chapter 7.2] hardye
@@ Line 55: / Line 55: @@
 This section was so confusing. I feel like I needed more diagrams or better pictures of how the algorithm works and how the forwards and backwards flows are established. I thought it was so hard to read and didn't like it. Readability: 5.
 ====== Chapter 7.2 ======
+**Maximum Flows and Minimum Cuts in a Network**
+We show that the flow returned by Ford-Fulkerson algorithm has the max possible value of any flow in G. We use a cut to place an upper bound of the max-flow value. We partition the nodes so that s is in one set and t is in a different set. All of the flow must cross from one set to the other (since the source and sink are in two different sets). The capacity of the cut, we represent as c(A,B), is the sum of the capacities of all edges out of A. This allows us the measure the flow value by watching the amount of flow f sends across a cut. So its the total amount that leaves A minus the total amount that comes back into A. value of any s-t flow is less than or equal to the capacity of any cut A,B (statement 7.8 p 347). This means the value of every flow is upper-bounded by the capacity of every cut. We can compute the s-t cut of minimum capacity in O(m) time. In every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut.
+We can further analyze this algorithm so that if all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer (p.351).
+This section again was really hard to read. A lot of proofs and really difficult to follow. Felt like it moved really fast and could use more visuals. Readability: 5
 ====== Chapter 7.5 ======
+**The Bipartite Matching Problem**
 ====== Chapter 7.7 ======