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/02 01:12] – [Chapter 7.5] tremog | courses:cs211:winter2014:journals:gabi:home [2014/04/02 01:21] (current) – [Chapter 7.7] tremog | ||
---|---|---|---|
Line 1847: | Line 1847: | ||
(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. | (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. | ||
+ | |||
**Algorithms: | **Algorithms: | ||
Line 1858: | Line 1859: | ||
Very very little. | 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): | Readability (scale: 1-10): | ||
Line 1908: | Line 1913: | ||
==== Chapter 7.7 ==== | ==== Chapter 7.7 ==== | ||
- | //**0.0: **// | + | //**7.7: Extensions to the Max-Flow Problem**// |
+ | **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. | ||
- | **Summary:** | + | One of these problems is the :Circulations with demands: algorithm. For example, what if you had multiple sources and multiple sinks. In this problem, instead of maxing the flow value, we have to consider a problem in which the sources have fixed supply values and the sinks have fixed demands values and our job is to meet these demands. |
+ | (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?:** | ||
+ | |||
+ | 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 :( | ||
+ | |||
+ | |||