Differences

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

--- courses:cs211:winter2014:journals:sam:home [2014/04/01 20:40] – [7.1] odells
+++ courses:cs211:winter2014:journals:sam:home [2014/04/02 02:18] (current) – [Readability] odells
@@ Line 336: / Line 336: @@
 ====7.2====
+We will continue to analyze the Ford-Fulkerson algorithm and verify that it does indeed have the maximum possible value for any graph G.
+The Ford-Fulkerson algorithm terminates when the flow f has no s-t path in the residual graph of Gf. This turns out to be the only property needed for proving its maximality. (7.9, pg 348)
+Remember when we pointed out that capacities in our graph must be integers for the F-F algorithm? Well, if that's NOT the case, then it is entirely possible for the algorithm to run forever, if real numbers are incorporated.
 ====7.5====
+The Bipartite Matching Problem
+A matching in a graph G is a subset of the edges M in E such that each node appears in at most one edge in M. The Bipartite Matching problem is that of finding a matching in G of largest possible size.
+The Ford-Fulkerson algorithms can be used to find a maximum matching in a bipartite graph in O(mn) time.
 ====7.7====
+Much of the power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph.
+Before, we had just one sink and one source. Now, we will have multiple! Now, instead of maximizing flow value, we will have sources that have a fixed supply and sinks that have a fixed demand, and our goal is to ship flow from nodes with available supply to those with given demands.
 ====Readability====
+/10. This section is incredibly dense and hard to make sense of. I don't think the book does a great job of explaining overly technical aspects.