Differences

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

--- courses:cs211:winter2018:journals:martineza:home [2018/04/03 00:17] – [Section 7.5:] martineza
+++ courses:cs211:winter2018:journals:martineza:home [2018/04/03 01:08] (current) – [Section 7.7: Extensions to Maximum Flow] martineza
@@ Line 402: / Line 402: @@
 **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====
-====Section 7.7: ====
+**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?