Differences

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

--- courses:cs211:winter2018:journals:shermanc:chapter7 [2018/04/04 07:39] – shermanc
+++ courses:cs211:winter2018:journals:shermanc:chapter7 [2018/04/05 05:21] (current) – shermanc
@@ Line 18: / Line 18: @@
 The next part was about analyzing the max-flow equals min-cut algorithm.  The gist was that if we have "f that is an s-t-flow, where no s-t path is in our residual graph, then there is a cut (A*, B*) in the graph for which v(f) = c(A*, B*)."  This tells us that f has a max value of flow in our graph and that (A*, B*) is the minimum capacity of any cut in the graph.
+===== 7.5: A First Application: The Bipartite Matching Problem =====
+In this section, we looked back at the Bipartite Matching Problem.  In order to find the maximum matching in the graph more efficiently, we can use the Ford-Fulkerson Algorithm.  This allows us to find it in O(mn) time, which is because in the Bipartite Matching Problem, C = n, so we see this from the previous bound we had found for the Ford-Fulkerson Alg. of O(mC).
+If we have a graph with two distinct sides where the sides are equal, then this graph either has a perfect matching or there will be a subset where the adjacent set is less than the subset.  Whether it is a perfect matching or the described subset, it can be found in O(mn) time.
+This section was interesting enough, but again the examples and talking through everything was drawn out and over complicated it seemed a lot, so 5/10.
+===== 7.7: Extensions to the Maximum-Flow Problem =====
+This section focused on how the maximum-flow problem can be put to use.  The first was with circulations, where we have a set of sources and a set of sinks.  Here, each node has a fixed value (supply for source, demand for sink).  In summary, there can be a circulation with a set of demands in a graph if and only if the flow has a value of D, which is the capacity of the cut of our source nodes.
+The next problem was the same as above, but introduced lower bounds.  In this, it works the same way, but the catch is that the flow value must be at least a certain value for the flow to go through.  In this, we can only have a feasible circulation if there is a feasible circulation in an identical graph that excludes the lower bounds.
+Overall, this section was interesting, as it applied what we had learned in the previous sections.  It was also shorter and not as convoluted, as well as the last one of these, so I'd give it a 7/10.