Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:thetfordt:chapter7 [2018/04/02 15:48] – thetfordt | courses:cs211:winter2018:journals:thetfordt:chapter7 [2018/04/02 15:53] (current) – thetfordt | ||
|---|---|---|---|
| Line 53: | Line 53: | ||
| In order to design an algorithm to see if there is a feasible circulation with demands in G, we slightly alter the original G and use the Ford Fulkerson Algorithm to figure this out. We alter it by creating a super-source s* and a super-sink t*, where the super source has edges to all other sources and each of the initial sinks have an edge to the super sink. It turns out that the circulation is feasible if and only if the maximum s*-t* flow is G' has value equal to the summations of each individual node's demand. | In order to design an algorithm to see if there is a feasible circulation with demands in G, we slightly alter the original G and use the Ford Fulkerson Algorithm to figure this out. We alter it by creating a super-source s* and a super-sink t*, where the super source has edges to all other sources and each of the initial sinks have an edge to the super sink. It turns out that the circulation is feasible if and only if the maximum s*-t* flow is G' has value equal to the summations of each individual node's demand. | ||
| + | The problem is then slightly altered. Suppose that there are lower bounds on the edges in terms of the flow that passes through them. In order to do this, we just slightly modify the input. We let G' have the same nodes and edges, but the capacity of each edge is the original capacity minus that edge's lower bound. The section then walks through the proof that this modification plugged into the Ford Fulkerson Algorithm will produce the desired results. | ||
| - | + | I would rate the readability of this section at 6/10. I found 7.5 and 7.7 very difficult to grasp as we have not yet covered them in class. | |
