Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 02:45] – [7.ONE - The Max-Flow Problem and the Ford-Fulkerson alg] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 03:16] (current) – [7.7 - Extensions to the Max-Flow Problem] tobind
@@ Line 230: / Line 230: @@
 ======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.