Differences

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

--- courses:cs211:winter2018:journals:martineza:home [2018/04/01 20:01] – [Section 7.1:] martineza
+++ courses:cs211:winter2018:journals:martineza:home [2018/04/03 01:08] (current) – [Section 7.7: Extensions to Maximum Flow] martineza
@@ Line 97: / Line 97: @@
-====Section 3.3: Implementing Graph Traversals====
+====Section 3.3: Implementing Graph Traversals ====
 **SUMMARY:**
 The book seeks to implement BFS and DFS in O(m+n) running time, where m represents edges and n represents nodes. A graph with n nodes and m edges can be represented by an nXn adjacency matrix, which allows us to check if there is an edge between 2 nodes in the graph. Adjacency lists are another way to represent represent a graph and are preferable to a matrix when edges are sparse; a list also only uses O(m+n) space, which is preferable to O(n<sup>2</sup>). Two data structures that support the implementation of DFS and BFS are queues (first in first out) and stacks (last in first out).
@@ Line 368: / Line 368: @@
 ===== Chapter 7 =====
-====Section 7.1: ====
+====Section 7.1: Maximum Flow ====
+**SUMMARY:**
+All transportation networks have three things in common: they have a source (where stuff originates), a sink (where everything eventually ends up), and each edge has a capacity (how much it can transport at one time). Two conditions that apply to the flow are 1) capacity condition, which states that the flow through an edge cannot exceed it's capacity and 2) conservation condition, which states that the total flow coming into an internal node must be the total flow going out. A common problem in a flow network is finding the maximum flow that can be pushed at once -- in order to do this we need to use residual graphs, which are a new data structure.
+**''
+Max-Flow\\
+- - - - Initially f(e)=0 for all e in G\\
+- - - - While there is an s-t path in the residual graph G<sub>f</sub>\\
+- - - - - - - - Let P be a simple s-t path in G<sub>f</sub> \\
+- - - - - - - - f’ = augment(f, P)\\
+- - - - - - - - Update f to be f’\\
+- - - - - - - - Update the residual graph G<sub>f</sub> to be G<sub>f'</sub>\\
+- - - - Endwhile\\
+Return f
+''**
-====Section 7.2: ====
+The algorithm above is known as the Ford-Fulkerson Algorithm and it terminates in at most C iterations of the while loop, where C is the sum of capacities of all edges coming out of the source. The overall running time of the algorithm is O(m*C).
-====Section 7.5: ====
+**REFLECTION:**
+I give this section a 9/10. The concept of a residual graph just blew me away -- what other applications are these graphs good for? It's really interesting how the type of data structure you have makes a world of difference in the running time of your algorithm. The class lecture was good for introducing the material and then the chapter in the book went into a LOT of detail. I still don't really understand how it can be O(m*C) running time because doesn't finding a path take O(n+m) just on its own?
-====Section 7.7: ====
+====Section 7.2: Minimum Cuts ====
+**SUMMARY:**
+We can prove that the Ford-Fulkerson Algorithm gives us the optimal solution by looking at cuts. A cut is when you divide the graph into 2 sets A and B so that the source is in A and the sink is in B -- the capacity of a cut is just the total of all capacities of edges that go from A to B. The total value of the flow from any cut in the s-t path is equal to the flow out of A minus the flow into A. For each graph, there exists a minimum cut that limits the overall maximum flow. The logic behind the correctness of the Ford-Fulkerson Algorithm depends heavily on the capacities of edges being integers -- if they are not integers, the running time of the algorithm might be much longer than O(m*C). However, the Max-Flow Min-Cut theorem holds even if the capacities were real numbers.
+**REFLECTION:**
+I'm giving this section a 5/10 for readability because it seems like they took some very common sense things and turned them into really complicated math proofs. It just makes sense that at some point in the graph you're going to have a bottleneck that limits the overall input. It could be at the very beginning if all the edges coming out of the source have the smallest total capacity of any cut in the graph or at the very end if all the edges going into the sink have that. Or it could be at any point in between. I would like more clarification of why real numbers could make it potentially a bad algorithm, since it seems highly likely that we would not only be working with integers in a real world implementation of this algorithm.
+====Section 7.5: Bipartite Matching====
+**SUMMARY:**
+In the Bipartite Matching Problem, we are trying to find the largest possible matching in graph G such that every edge in the set of edges has one end in set X and one end in set Y. We can compute this by turning the undirected graph into a directed graph where all edges have a capacity of 1. Then, we find the maximum flow over this new graph and this results in the largest matching in G. The overall running time of this (converting to directed graph and running the Ford-Fulkerson Algorithm) is O(n*m), which is the same as running BFS or DFS. Hall's Theorem states that if the maximum flow over the graph is less than n, there is no bipartite matching possible.
+**REFLECTION:**
+I found this section very difficult to read 4/10, because they used symbols that I have never before, such as the upside down L. I really wish I knew math terminology because I feel like that would make reading this textbook much easier at times. One question I have is: when is Bipartite Matching useful? What real world applications does it relate to? We haven't talked about this problem in class yet, hopefully that will make it clearer.
+====Section 7.7: Extensions to Maximum Flow====
+**SUMMARY:**
+Many problems can be solved in polynomial time because they can be reduced to problems of maximum flow. One such extension is meeting the demand of multiple sinks using the flow produced by multiple sources (eg. multiple factories shipping products to multiple stores). By manipulating the graph and adding a "super" source and "super" sink, we can reduce the problem to essentially a maximum flow problem. If the maximum flow of this new graph has value D, that means there is a feasible circulation -- otherwise, there is none. Another extension is that of forcing the solution to include certain edges by placing lower bounds on edges. We want to know if there is a circulation that satisfies the new conditions created by this limitation. We do this by creating a graph G' that is the same as G but without lower bounds. If G' contains a feasible circulation, that means that G does as well.
+**REFLECTION:**
+I give this section a 7/10. It wasn't super-interesting but it also wasn't terribly complicated like the last couple of sections I've read. I'm interested to see these ideas explained in class -- I feel like some of these concepts would be more clear with step-by-step illustrations. The algorithms we looked at here are for seeing if there exists a way to solve the problem at hand, but can they actually say what the most efficient way is? Do companies actually use algorithms like this to ensure top efficiency in product delivery?