Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 16:46] – [7.7 Extensions to Max Flow 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=======
 ==Summary==
-The problem of circulations with demands has the problem
+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==
@@ Line 152: / Line 152: @@
     * dv < 0: supply of –dv
     * 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 conditions
+  * 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 conditions
   * feasibility problem: whether there exists a circulation that meets the above conditions
   * in order for feasible circulation: total supply must equal the total demand