Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2014:journals:gabi:home [2014/04/01 21:59] – [Chapter 7.5] tremog | courses:cs211:winter2014:journals:gabi:home [2014/04/02 01:21] (current) – [Chapter 7.7] tremog | ||
---|---|---|---|
Line 1830: | Line 1830: | ||
==== Chapter 7.2 ==== | ==== Chapter 7.2 ==== | ||
- | //**0.0: **// | + | //**7.2: Maximum Flows and Minimum Cuts in a Network**// |
+ | **Summary: | ||
+ | Our goal is to go ahead and show that the flow that is returned by the F-F algorithm has the maximum flow possible of any other flow in G. How do we check this??? We want to look at the way in which the structure of the flow network places upper bounds on the max value of s-t flow. | ||
- | **Summary:** | + | We already have one bound: the value of v(f) of any s-t flow. That, at most, is C = SUM (e out of s Ce) |
+ | (7.6) Let f be any s-t flow and (A,B) any s-t cut. Then v(f) = f(out(A)) - F(in(A)) | ||
+ | (7.8) Let f be any s-t flow, and (A,b) any s-t cut. Then v(f) < = c(A,B) | ||
- | **Algorithms: | + | In a sense, (7.8) looks weaker than (7.6) does since it is only an inequality rather can than equality. However, this becomes extremely useful for us, since the right-hand side is independent of any particular flow f. |
+ | Basically, what (7.8) is saying is that //the value of every flow is upper-bounded by the capacity of every cut// | ||
+ | (7.13) In Every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut. | ||
- | **Questions:** | + | **Algorithms:** |
+ | none | ||
+ | **Questions: | ||
+ | |||
+ | What did I just read? That seems like a weird question but I'm slightly confused because I feel like I just read myself in circles. | ||
**What made sense?:** | **What made sense?:** | ||
+ | Very very little. | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | In a sense, (7.8) looks weaker than (7.6) does since it is only an inequality rather can than equality. However, this becomes extremely useful for us, since the right-hand side is independent of any particular flow f. | ||
+ | |||
+ | Readability (scale: 1-10): | ||
+ | |||
+ | 5-6. I don't know. This section was very circuitous for me. It could be just that the entire chapter seemed to make very similar points the entire way around it or it could be that I have a hard time reading sums? I don't know. I just got lost and am still very confused as to what I just read. | ||
==== Chapter 7.5 ==== | ==== Chapter 7.5 ==== | ||
- | //**0.0: **// | + | //**7.5: A First Application: |
+ | **Summary: | ||
+ | |||
+ | One of our original goals in developing the Max-Flow problem was to be able to solve the Bipartite Matching problem. | ||
+ | |||
+ | The graph defining a matching problem is undirected, while flow networks are direction. However this is not difficult to implement to find a max matching solution. | ||
+ | |||
+ | We start by computing a max s-t flow in the network G'. We discover that the value of this maximum is equal to the size of the maximum matching in G. Also, our analysis shows that we can actually use the flow itself to recover the matching. | ||
+ | |||
+ | We do this by looking at three facts about M', which is the set of edges of the form (x,y) on which the flow value is one. | ||
+ | |||
+ | 1) M' contains k edges | ||
+ | 2) Each node in X is the nail of at most one edge in M' | ||
+ | 3) Each node in Y is the head of at most one edge in M' | ||
+ | |||
+ | Combining these facts we can see that if we view M' as a set of edges in the original bipartite graph G, we get a matching of size k. In short: | ||
+ | |||
+ | (7.37) The size of the maximum matching in G is equal to the value of the max flow in G' and the edges in such matching in G are the edges that carry flow from X to Y in G' | ||
+ | |||
+ | |||
+ | Moreover, we can do all of this in O(Mc) time since we are using the F-F algorithm!!! | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | the Ford-Fulkerson algorithm, which is actually discussed in section 1. | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | Why couldn' | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The runtime!! (It's the same as section one ;) ) | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | The graph defining a matching problem is undirected, while flow networks are direction. However this is not difficult to implement to find a max matching solution. | ||
+ | |||
+ | **Readability (1-10):** | ||
+ | |||
+ | 7. Would have been an 8 if there was some psudeo-code to go along with it. The psudeo-code always helps me sort through the text (since the texbook can be a little bit dense sometimes. The code is a nice outline) | ||
+ | ==== Chapter 7.7 ==== | ||
+ | //**7.7: Extensions to the Max-Flow Problem**// | ||
**Summary: | **Summary: | ||
+ | Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew? It also helps with problems that have nontrivial combinatorial search components. It is very useful because it can be solved in poly-time with O(Mc) time because of the F-F algorithm. | ||
+ | |||
+ | One of these problems is the : | ||
+ | |||
+ | (7:51) The Graph G has a feasible circulation with demands (dv) if and only if for all cuts (A,B) | ||
+ | |||
+ | |||
+ | If all of the capacities and demands in G are integers and there is a feasible circulation, | ||
**Algorithms: | **Algorithms: | ||
+ | Once again, the F-F algorithm from section one. | ||
**Questions: | **Questions: | ||
+ | Where is the psudo-code? :( | ||
**What made sense?:** | **What made sense?:** | ||
- | ==== Chapter | + | The real world application. I don't know why but I can visualize this problem well. Maybe not real world, but this is much less of an abstraction than the ones in 7.5 and 7.2 |
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew? | ||
+ | |||
+ | **Readability (1-10):** | ||
+ | |||
+ | 7. No psudeo-code :( | ||
+ | |||
+ |