Differences

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

--- courses:cs211:winter2014:journals:johanna:home [2014/03/26 01:17] – goergenj
+++ courses:cs211:winter2014:journals:johanna:home [2014/04/02 21:34] (current) – goergenj
@@ Line 176: / Line 176: @@
   * In order to solve for Opt(n), we will need to find out the value for Opt(n-1) and the Opt() of all subsets of the first n-1 items. Thus, we will use a 2D array to store the values for the optimal value in the bag per weight per num items added for each subset. This is a version of the memoization we used in previous algorithms to allow us not to have to recalculate and help us easily make comparisons throughout the algorithm.
+====== Chapter 7.1 Summary ======
+  * This section deals with flow networks. These are networks that model traffic through "switches" passing from edge to edge. These are modeled by graphs with a few components: capacities on the edges, source nodes in the graph that generate traffic, sink nodes in the graph that absorb traffic, and the traffic itself which is transmitted across the edges. The graphs of this form are directed graphs represented by G = (V, E) as any other graph. However, this graph also has a single source node //s// and a single sink node //t//. The other nodes will be called internal nodes. An //s-t// flow is a function mapping each edge //e// in E to a nonnegative real number. The value f(//e//) represents the amount of flow carried by edge //e//. A value f(//e//) must satisfy the two values: 0≤f(//e//)≤c<sub>e</sub> and the sum of flow into //e// is equal to the sum of the flow out of //e//. The problem we will try to solve with this network flow model will be to find the arrangement of traffic that makes the most efficient use possible of a given set of capacities and flows.
+  * The residual graph is a tool we will use to implement an algorithm to solve the maximum-flow problem. The residual graph contains the same nodes as our original graph but its edges are different. Each forward edge (u,v) has a capacity of c<sub>e</sub> - f(//e//) and then a backwards edge (v,u) is added so that we can "undo" this forward flow. The capacity of this backwards edge is f(//e//).
+  * The augment function defined on page 342 traverses a path P turning it into a simple residual graph by decreasing the remaining capacity of each edge by bottleneck(P, f) and increasing the residual capacity by b. Proof 7.1 proves that the result of this augment function is a flow in G.
+  * Then the Ford-Fulkerson Algorithm uses this augment function and creates an entire residual graph and then uses it to calculate the maximum flow. It does so by running the augment function on every s-t path in the residual graph.
+====== Chapter 7.2 Summary ======
+  * We will now use the fact that cuts provide very natural upper bounds on the values of flows. This is since the capacity of a cut (A,B) is the sum of capacities on all edges out of A. Then we will prove that v(f)= f<sup>out</sup>(A) - f<sup>in</sup>(A). The intuition is that f<sup>in</sup>(s) = 0 so v(f) = <sup>out</sup>(s) - <sup>in</sup>(s). Then either edge //e// has both ends in A, //e// has one end in and one end out of A, or //e// has neither ends in A. So f(//e//) either appears once in the sum with a + and once with a -, just once in the sum with a +, or just in the sum with a -. Thus, the sum of flow for edges in A is f<sup>out</sup>(A) - f<sup>in</sup>(A).
+  * This helps us come to the conclusion that the maximum flow in the maximum-flow problem is equal to the minimum cut.