Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:shannon:chapter7 [2014/04/02 04:32] – [Section 7.5: A First Application: The Bipartite Matching Problem] nollets | courses:cs211:winter2014:journals:shannon:chapter7 [2014/04/02 04:43] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] nollets | ||
|---|---|---|---|
| Line 28: | Line 28: | ||
| The Maximum-Flow problem is able to do a lot more than determine how much traffic can flow across a graph. Some of the other problems that exist in tandem with the Maximum-Flow are circulations with demands and circulation with bounds. The circulation with demands is when we have multiple sources and multiples sinks and a fixed supply and demand that we must ship across the graph. We want to know that there is a circulation that delivers the necessary demand without exceeding the capacity of the graph. In order to determine what this circulation is, we can find a maximum s-t flow is a graph that is made by attaching a super source and a super sink to each end of the graph. The process by which we are able to glean a maximum graph using this is on page 381 of the text. Then we know that there is a feasible circulation if the maximum flow of the graph is D. | The Maximum-Flow problem is able to do a lot more than determine how much traffic can flow across a graph. Some of the other problems that exist in tandem with the Maximum-Flow are circulations with demands and circulation with bounds. The circulation with demands is when we have multiple sources and multiples sinks and a fixed supply and demand that we must ship across the graph. We want to know that there is a circulation that delivers the necessary demand without exceeding the capacity of the graph. In order to determine what this circulation is, we can find a maximum s-t flow is a graph that is made by attaching a super source and a super sink to each end of the graph. The process by which we are able to glean a maximum graph using this is on page 381 of the text. Then we know that there is a feasible circulation if the maximum flow of the graph is D. | ||
| - | Another problem is the circulations with demands and lower bounds. | + | Another problem is the circulations with demands and lower bounds. This problem enables us to force the flow to pass through certain edges by placing lower bounds on some edges. The strategy behind the algorithm is to reduce this to finding a circulation with demands but no lower bounds. (Discussed on 383 of the text). |
| - | I would give this section a 8/10. It was little confusing and I'm not entirely sure how these problems would be applied in real life. I am sure that we will go over this in class and it will help me see things a little more clearly. | + | I would give this section a 6/10. It was little confusing and I'm not entirely sure how these problems would be applied in real life. I am sure that we will go over this in class and it will help me see things a little more clearly. |
