Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 01:53] – [6.4 - Subset Sums and Knapsacks: Adding a Variable] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 03:16] (current) – [7.7 - Extensions to the Max-Flow Problem] tobind
@@ Line 170: / Line 170: @@
   * the node set of //Gf// is the same as that of //G//
   * for each edge //e = (u,v)// of //G// on which //f(e) < ce//, the are //ce - f(e)// "leftover" units of capacity on which we could try pushing flow forward so we include the edge //e = (u,v)// in //Gf// with a capaicty of //ce - f(3)//. ->> forward edges
-  * for each edge //e// on which //f(e) > 0, there are //f(e)// units of flow we can "undo" by pushing backwards. So we include the edge //e' = (v,u)// in //Gf// with a capacity of //f(e)//. ->>> backwards edges
+  * for each edge //e// on which //f(e) > 0//, there are //f(e)// units of flow we can "undo" by pushing backwards. So we include the edge //e' = (v,u)// in //Gf// with a capacity of //f(e)//. ->>> backwards edges
 //Gf// has at most 2x the edges as //G//.
-To augment paths in a residual graph
+To augment paths in a residual graph:
+Let //P// be a simple //s-t// path in //Gf//. We define bottleneck(//P,f//) to be the min residual capaicty of any edge on //P//, with respect to the flow //f//. Now,
+   augment(f,P)
+     Let b = bottleneck(P,f)
+     For each edge (u,v) ∈ P
+        If e = (u, v) is a forward edge then
+           increase f(e) in G by b
+        Else ((u,v) is a backward edge and let e = (v,u))
+           decrease f(e) in G by b
+        Endif
+      Endfor
+      Return(f)
+The result of augment(//f,P//) is a new flow //f'// in //G//, obtained by increasing and decreasing the flow values on edges of //P//.
+Now, the alg to compute a //s-t// flow:
+   Max-flow
+     Initially f(e) =0 for all e in G
+     While there is an s-t path in the residual graph Gf
+        Let P be a simple s-t path in Gf
+        f' = augment(f,P)
+        Update f to be f'
+        Update the residual graph Gf to be Gf'
+     Endwhile
+     Return f
+This is the Ford-Fulkerson algorithm.
+**analyzing the algorithm: termination and running time**
+  * at every intermediate stage of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in //Gf// are integers.
+  * Let //f// be a flow in //G// and let //P// be a simple //s-t// path in //Gf//. Then //v(f') = v(f) + bottleneck(P,f)// and since //bottleneck(P,f) > 0//, we have //v(f') > v(f)//.
+  * The FF alg terminates in at most //C// iterations of the while loop. C = total possible sum
+  * The FF alg can run in //O(mC)// time.
+This section was a nine out of ten.
+======7.2- Maximum Flows and Minimum Cuts in a network. ======
+**analyzing the algorithm: Flows and Cuts**
+Now we want to show that the flow found by FF has the max possible value of any flow in G.
+Consider dividing the nodes of the graph into two sets, //a// and //B//, so that //s ∈ a// and //t ∈ B//. The capacity fo a cut (//a,B//), which we will denote //c(a,B)// is simply the sum of the capacities of all edges out of //a//.
+Note that if (//a,B//) is a cut, then the edges into //B// are precisely the edges out of //a//. So, we have fout(//a//) = fin(//B//) and fin(//a//) = fout(//B//). So, let //f// be any //s-t// flow and (//a,B//) any //s-t// cut. Then //v(f)// = fin(//B//) - fout(//B//).
+  (7.8) Let f be any s-t flow, and (a,B) any s-t cut. Then v(f) ≤ c(a,B).
+**analyzing the algorithm: Max-Flow equals Min-Cut**
+Let //f//* denote the flow returned by FF. To show that //f//* has the max possible vale of any flow in //G//, we exhibit an //s-t// cut (//a*, B*//) for which //v(f*) = c(a*, B*)//. So f* has the max value and (//a*, B*//) has the min capacity of any //s-t// cut.
+If //f// is an //s-t// flow s.t. there is no //s-t// path in the residual graph //Gf//, then there is an //s-t// cute (//a*, B*//) in //G// for which //v(f) = c(a*, B*)//. Consequently, //f// has the max value of any flow in //G// and (//a*, B*//) has the min capacity of any //s-t// cut in //G//.
+   (7.) Given a flow f of max value, we can compute an s-t cut of min capaity in O(m) time.
+   In every flow network, the max value of an s-t flow is equal to the min capacity of an s-t cut.
+For interesting, I found this section a 7.
+======7.5 - Bipartite Matching Problem ======
+**The Problem**
+We want to find a matching in //G// of largest possible size.
+**Designing the alg**
+The graph defining a matching problem is undirected, but we can make it work.
+Beginning with a graph //G//, we construct a flow network //G'//. First we direct all edges in //G// from //X// to //Y//. We then add a node //s// and an edge (//s,x//) from //s// to each node in //X//. We add a node //t// and an edge (//y,t//) from each node in //Y// to //t//. Finally, we give each edge in //G'// a capacity of one. Then we compute a max //s-t// flow in this network //G'//.
+**analyzing the alg**
+Here are three simple facts about the set //M'//.
+  * //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'//.
+  The size of the maximum matching in G is equal to teh value of the max flow in G';
+  and the edges in such a matching in G are the edges that carry flow from X to Y in G'.
+The FF alg can be used to find a max matching in a bipartite graph in //O(mn)// time.
+I give this section an 8.
+======7.7 - Extensions to the Max-Flow Problem ======
+**Circulations with Demands**
+Suppose there is now a set //S// of sources generating flow and a set //t// of sinks. Instead of maximizing the flow values, we will consdier a problem where sources have fixed supply values and sinks have fixed demand values. given a flow network with capacities on the edges, each node //v// has a demand //dv//. If //dv// > 0, the node is a sink. If //dv// < 0, it is a source. //S// denotes the nodes with negative; //T// is the set of nodes with positive demands.
+In this setting we say that a circulation with demands {//dv//} is a function //f// satisfies the capacity and demand conditions.
+So now we just have a feasibility problem.
+  (7.49) If there exists a feasible circulation with demands {dv}, then Σdv = 0.
+See p 382 for proof of:
+There is a feasible circulation with demands {//dv//} in //G// iff the max //s*-t*// flow in //G'// has value //D//. If all capacities and demands in //G// are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
+**Circulations with Demands and Lower Bounds**
+Consider a flow network with a capacity //ce// and a lwoer bound //le// on each edge //e//.
+We simply reduce this problem to the one above. See p383 for proof that
+There is a feasible circulation in //G// iff 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.
+This section wasn't very interesting for me, so only a 6.