Differences

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

--- courses:cs211:winter2014:journals:sam:home [2014/03/31 12:13] – odells
+++ courses:cs211:winter2014:journals:sam:home [2014/04/02 02:18] (current) – [Readability] odells
@@ Line 327: / Line 327: @@
 ====7.1====
+Graphs are often used to model transportation networks, where edges carry some sort of traffic and nodes act as "switches" passing traffic between different edges. Network models like this have capacities on the edges and source nodes in the graph (that generate traffic) and sink nodes in the graph that are destinations that absorb traffic as it arrives. The traffics across these kinds of graphs is often referred to as "flow."
+A typical goal with this type of graph is to arrange the traffic so as to make as efficient use as possible of the available capacity. At the moment, there is no known algorithm for the Maximum-Flow Problem that could be considered a "dynamic programming" solution, so we'll return to greedy solutions.
+The Ford-Fulkerson Algorithm solves this problem. (page 344)
+It can be implemented in O(mC) time, so long as all the capacities in the flow network are integers.
 ====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.