Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter7 [2014/03/31 02:54] – [Section 7.5: A First Application: The Bipartite Matching Problem] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter7 [2014/04/02 04:43] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] nollets
@@ Line 23: / Line 23: @@
 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.
+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.