Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:shermanc:chapter7 [2018/04/04 21:37] – shermanc | courses:cs211:winter2018:journals:shermanc:chapter7 [2018/04/05 05:21] (current) – shermanc |
|---|
| ===== 7.7: Extensions to the Maximum-Flow Problem ===== | ===== 7.7: Extensions to the Maximum-Flow Problem ===== |
| |
| This section focused on how the maximum-flow problem can be put to use. | This section focused on how the maximum-flow problem can be put to use. The first was with circulations, where we have a set of sources and a set of sinks. Here, each node has a fixed value (supply for source, demand for sink). In summary, there can be a circulation with a set of demands in a graph if and only if the flow has a value of D, which is the capacity of the cut of our source nodes. |
| | |
| | The next problem was the same as above, but introduced lower bounds. In this, it works the same way, but the catch is that the flow value must be at least a certain value for the flow to go through. In this, we can only have a feasible circulation if there is a feasible circulation in an identical graph that excludes the lower bounds. |
| | |
| | Overall, this section was interesting, as it applied what we had learned in the previous sections. It was also shorter and not as convoluted, as well as the last one of these, so I'd give it a 7/10. |
| |
