Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 15:55] – [7.5 Bipartite Matching Problem] nasona | courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 16:57] (current) – [7.7 Extensions to Max Flow Problem] nasona | ||
|---|---|---|---|
| Line 140: | Line 140: | ||
| =======7.7 Extensions to Max Flow Problem======= | =======7.7 Extensions to Max Flow Problem======= | ||
| ==Summary== | ==Summary== | ||
| + | The problem of circulations with demands has the problem of is it feasible for the circulation capacity and demand conditions to exist. Total supply must equal the total demand for a circulation to be feasible. There is a feasible circulation with demands {dv} in G if and only if the max s*-t* flow in G’ has value D (the capacity). We can add lower bounds to ensure flow to certain edges. In order to do this, we need to reduce this to the problem of finding a circulation with demands but no lower bounds. | ||
| ==The Problem: Circulations with Demands== | ==The Problem: Circulations with Demands== | ||
| Line 151: | Line 152: | ||
| * dv < 0: supply of –dv | * dv < 0: supply of –dv | ||
| * dv=0; neither a source nor a sink | * dv=0; neither a source nor a sink | ||
| - | * circulation with demands {dv} is a function that assigns a nonnegative real number to each edge and satisfies the following two conditions: capacity conditions and command | + | * circulation with demands {dv} is a function that assigns a nonnegative real number to each edge and satisfies the following two conditions: capacity conditions and demand |
| * feasibility problem: whether there exists a circulation that meets the above conditions | * feasibility problem: whether there exists a circulation that meets the above conditions | ||
| * in order for feasible circulation: | * in order for feasible circulation: | ||
