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 :( | ||
| + | |||
| + | |||
