Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter7 [2014/03/31 01:36] – [Section 7.2: Maximum Flows and Minimum Cuts in a Network] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter7 [2014/04/02 04:43] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] nollets
@@ Line 18: / Line 18: @@
 This section was very proof heavy and therefore a little confusing. I would give it a 6/10.
 =====Section 7.5: A First Application: The Bipartite Matching Problem=====
+The Bipartite Matching Problem is a problem we discussed earlier in the semester, where we want to split a graph into two colors of nodes. We can create a flow network from a bipartite graph that will have a maximum matching that is equal to the maximum flow of the graph. We try and find the best matching for the graph (a matching is the two sets in which one can entirely be colored blue and the other red and there are edges between them).
+We then bound the run time of this algorithm O(mn) where m is the number of edges in the graph. There is discussion of further refining this run time but it is not necessary.
+We also want to be able to determine whether a graph has a perfect matching and output this information to the user.
+This section was super confusing to me. I'm not really sure what the motivation is behind this problem is. Since I was confused I would give this section a 5/10. It was confusing and I hope we discuss this problem in class.
 =====Section 7.7: Extensions to the Maximum-Flow Problem=====
+The Maximum-Flow problem is able to do a lot more than determine how much traffic can flow across a graph. Some of the other problems that exist in tandem with the Maximum-Flow are circulations with demands and circulation with bounds. The circulation with demands is when we have multiple sources and multiples sinks and a fixed supply and demand that we must ship across the graph. We want to know that there is a circulation that delivers the necessary demand without exceeding the capacity of the graph. In order to determine what this circulation is, we can find a maximum s-t flow is a graph that is made by attaching a super source and a super sink to each end of the graph. The process by which we are able to glean a maximum graph using this is on page 381 of the text. Then we know that there is a feasible circulation if the maximum flow of the graph is D.
+Another problem is the circulations with demands and lower bounds. This problem enables us to force the flow to pass through certain edges by placing lower bounds on some edges. The strategy behind the algorithm is to reduce this to finding a circulation with demands but no lower bounds. (Discussed on 383 of the text).
+I would give this section a 6/10. It was little confusing and I'm not entirely sure how these problems would be applied in real life. I am sure that we will go over this in class and it will help me see things a little more clearly.