Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 14:04] – [7.2 Maximum Flows and Minimum cuts in a Network] patelk
+++ courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 17:53] (current) – [7.7 Extensions to the Maximum-Flow Problem] patelk
@@ Line 115: / Line 115: @@
     * A* denotes the set of all nodes v in G for which there is an s-v path in Gf
     * B* denotes the set of all other nodes: B* = V - A*
+{{:courses:cs211:winter2018:journals:patelk:7.9maxflowequalsmincut.png?nolink&400|}}
+    * All edges out of A* are saturated with flow
+    * All edges into A* are completely unused, so:
+{{:courses:cs211:winter2018:journals:patelk:7.9maxflowequalsmincutequation.png?nolink&400|}}
+  * The flow f+ returned by the Ford-Fulkerson Algorithm is a maximum flow
+  * Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time
+    * construct the residual graph Gf, perform breadth-first search/depth-first search, define B* = V - A*, return the cut (A*,B*)
+  * In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut
+__Further Analysis: Integer-Valued Flows__
+  * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer
+    * Not every maximum flow is integer-valued, only some maximum flow has this property
+  * //Real Numbers as Capacities?//
+    * allowing capacities to be rational numbers does not make the situation any more general, since we can determine the least common multiple of all capacities, and multiple them all by this value to obtain an equivalent problem with integer capacities.
+    * If real numbers are capacities: concern is that the value of our flow keeps increasing, but in increments that become arbitrarily smaller and smaller; no guarantee that the number of iterations of the loop is finite
+    * Capacities in any practical application of network flow would be integers or rational numbers
+      * The problem of pathological choices for the augmenting paths can manifest itself even with integer capacities.
+==== Personal Thoughts ====
+This section makes a lot of sense, again, because we began our discussion on this chapter in class on Friday. I think most of the ideas are logical, but some take a little longer to understand than others. The idea of having real numbers as capacities is a little confusing for me, especially because of the way that the section leaves off. The section ends by saying that there can be problems with integer capacities, not just with rational number capacities. I'd like to know more about why that is and what the solution to it is.
+Readability: 6.5
+Interesting: 6.5
+----
+===== 7.5 A First Application: The Bipartite Matching Problem =====
+__Analyzing the Algorithm: Flows and Cuts__
+**The Problem**
+  * Bipartite Graph G = (V,E) is an undirected graph whose node set can be partitioned as V = X union Y, with the property that every edge e in E has one end in X and the other in Y
+  * Matching M in G is a subset on the edge M in E such that each node appears in at most one edge in M
+**Designing the Algorithm**
+  * We construct a flow network G'
+  * Direct all edges in G from X to Y
+  * Add a node s, and an edge (s,x) from s to each node in X
+  * add a node t, and an edge (y,t) from each node in Y to t
+  * Give each edge in G' a capacity of 1
+  * Compute a maximum s-t flow in the network G'
+**Analyzing the Algorithm**
+  * Suppose there is a matching in G consisting of k edges
+  * Then consider the flow f that sends one unit along each path, that is f(e) = 1 for each ege on one of these paths
+  * Suppose there is a flow f' in G' of value k
+  * By the integrality theorem for maximum flows, we know there is an integer-valued flow f of value k
+  * Since all capacities are 1, f(e) is equal to either 0 or 1 for each edge e
+  * Consider the set M' of edges in the form (x,y) on which the flow value is 1
+    * M' contains k edges
+    * Each node in X is the tail of at most one edge in M'
+    * Each node in Y is the head of at most one edge in M'
+  * If we view M' as a set of edges in the original bipartite graph G, we get a matching of size k:
+    * The size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G'
+  * //Bounding the Running Time//
+    * The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time
+      * Consider the matching M consisting of edges in the bipartite graph
+        * Let f be the corresponding flow in G'
+        * Matching in not maximum, so f is not a maximum s-t flow, and hence there is an augmenting path in the residual graph G'f.
+        * All augmenting paths must alternate between edged used backward and forward, as all edges of the graph G' go from X to Y
+          * also known as alternating paths in the context of finding a maximum matching
+        * Effect of this augmentation is to take the edges used backward out of the matching and replace them with the edges going forward.
+          * Because the path goes from s to t, there is one more forward edge than backward edge (size of the matching increases by one)
+__Extensions: The Structure of Bipartite Graphs with No Perfect Matching__
+  * What if there is not a perfect matching?
+  * We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has at least n
+    * By the Max-Flow Min-Cut Theorem, there will be an s-t cut of capacity less than n if the maximum-flow value in G' has value less than n
+      * a cut with capacity less than n provides a "certificate" of no matching
+  * If a bipartite graph G = (V,E) with two sides X and Y has a perfect matching, then for all A in X, we must have |Gamma(A)| >= |A|
+    * Hall's Theorem
+  * Assume that the bipartite graph G = (V,E) has two sides X and Y such that |X| = |Y|. Then the graph G either has a perfect matching or there is a subset A in X such that |Gamma(A)| < |A|.
+    * A perfect matching or an appropriate subset A can be found in O(mn) time
+{{:courses:cs211:winter2018:journals:patelk:mincutmovingnodes.png?nolink&400|}}
+==== Personal Thoughts ====
+This section was more dense, so it was not quite as easy to read. I think this section spent a lot of time trying to prove theorems, and as a result, I had to spend more time processing and learning this section. However, on the whole, I think everything this section says made sense to me. I know I'll need some application practice in order to fully comprehend this section.
+Readability: 6.0
+Interesting: 6.0
+----
+===== 7.7 Extensions to the Maximum-Flow Problem =====
+  * Many problems have a nontrivial combinatorial search component that can be solved in polynomial time
+**The Problem: Circulations with Demands**
+  * set S of sources generating flow and set T of sinks that can absorb flow
+  * Consider a problem where sources have fixed supply values and sinks have fixed deman values
+  * goal: ship flow from nodes with available supply to those with given demands
+  * Associated with each node v in V is a demand dv
+    * If dv > 0, the node v has a demand of dv for flow
+    * Node is a sink and it wishes to receive dv units more flow than it sends out
+    * If dv < 0, the node v has a supply of -dv; the node is a source and it wishes to send out -dv units more flow than it receives
+    * If dv = 0: node v is neither a source nor a sink
+      * Assume all capacities and demands are integers
+  * S: set of all nodes with negative demand
+  * T: set of all nodes with positive demand
+  * Circulation with demands {dv} is a function f that assigns a nonnegative real number to each edge and satisfies the following two conditions:
+    * Capacity: for each e in E, we have 0 <= f(e) <= ce
+    * Demand: for each v in V, we have v, fin(v)-fout(v) = dv
+  * Feasibility Problem: does there exist a circulation that meets the two conditions above?
+  * If there exists a feasible circulation with demands {dv}, then sum of the demands = 0
+**Designing and Analyzing an Algorithm for Circulations**
+  * We can reduce the problem of finding a feasible circulation with demands {dv} to the problem of finding a maximum s-t flow in a different network
+  * We attach a "super-source" s* to each node in S and a "super-sink" t* to each node in T
+    * create a graph G' from G by adding new nodes s* and t* to G
+    * for each node v in T, we add an edge (v,t*) with capacity dv
+    * for each node u in S, we add an edge (s*, u) with capacity du
+    * carry the remaining structure of G over to G' unchanged
+  * Can think of this reduction as introducing a node s* that "supplies" all the sources with their extra flow, and a node t* that "siphons" the extra flow out of the sinks.
+  * There cannot be an s*-t* flow in G' of value greater than D, since the cut (A,B) with A ={s*} only has capacity D
+    * Further, if there is a flow of value D in G', there there is such a flow that takes integer values
+  * There is a feasible circulation with demands {dv} in G if and only if the maximum s*-t* flow in G' has value D. If all capacities and demands in G are integers, and there is a feasible circulation, there there is a feasible circulation that is integer-valued
+  * The graph G has a feasible circulation with demands {dv} if and only if for all cuts (A,B), the sum of for all v in B of dv <= c(A,B).
+**The Problem: Circulations with Demands and Lower Bounds**
+  * To force the flow to make use of certain edges, we can enforce lower bounds on edges
+  * G=(V,E) with a capacity of ce and a lower bound le on each edge e
+  * -<= le <= ce for each e
+  * each node v also has a demand dv (positive or negative)
+  * all are integers
+  * circulation in flow network must satisfy two conditions:
+    * Capacity: for each e in E, we have le<=f(e)<=ce
+    * Demand: for every v in V, we have fin(v)-fout(v) = dv
+**Designing and Analyzing an Algorithm with Lower Bounds**
+  * Reduce this to the problem of finding a circulation with demands but no lower bounds
+  * On each edge e, we need to sent at least le units of flow
+  * Initial circulation: f0(e) = le
+    * f0 satisfies all the capacity conditions (both lower and upper bounds)
+  * If Lv = dv, where Lv is quantity, then we have satisfied the demand condition at v
+  * If not, then we need to superimpose a circulation f1 on top of f0 that will clear the remaining "imbalance" at v
+    * f1in(v)-f1out(v) = sum of all e into v of le = the sum of a v of le
+  * There is a feasible circulation in G if and only if there is a feasible circulation in G'
+    * If all demands, capacities, and lower bounds in G are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
+==== Personal Thoughts ====
+This section took the concept of network flows to the next level by bringing in other variations/extensions of the original problem. While the overarching problems made sense, I got bogged down in a lot of the terminology and new factors that were added in. I think I need to reread this section one more time after we go over it in class to fully grasp the concepts presented in this section.
+Readability: 5.5
+Interesting: 5.5
+----