Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:paul:home [2012/04/06 01:54] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 02:17] (current) – [Chapter 7] nguyenp | ||
|---|---|---|---|
| Line 776: | Line 776: | ||
| * Assume that the bipartite graph G=(V,E) has two sides X and Y such that |X| and |Y|. Then the graph G either has a perfect matching or these is a subset A such that |\G(A)|< | * Assume that the bipartite graph G=(V,E) has two sides X and Y such that |X| and |Y|. Then the graph G either has a perfect matching or these is a subset A such that |\G(A)|< | ||
| * Section 7.7 - Extensions to Max-Flow Problem | * Section 7.7 - Extensions to Max-Flow Problem | ||
| - | * | + | * Circulations with Demands |
| + | * We have a directed graph | ||
| + | * edges have capacities | ||
| + | * nodes have supply and demands | ||
| + | * A circulation is a function that satisfies the following | ||
| + | * the flows for a particular edge are always less than the capacity (makes sense and is very intuitive) | ||
| + | * the demand for a node is equal to the stuff coming in minnus the stuff going out (the the demand that his node has? I guess that makes enough sense...) | ||
| + | * To keep the world form exploding, the sum of supplies == sum of demands | ||
| + | * Algorithm: more details on pg 381 and 382 | ||
| + | * Add a new source s and sink t | ||
| + | * For each v with d(v) < 0, add edge (s, v) with capacity -d(v) | ||
| + | * For each v with d(v) > 0, add edge (v, t) with capacity d(v) | ||
| + | * MAGIC: G has circulation iff G' has max flow of value D | ||
| + | * MORE MAGIC : Given (V, E, c, d), there does not exist a circulation iff there exists a node partition (A, B) such that the sum of all the demands is greater than cap(A,B) | ||
| + | * These two pretty much solve the problem for us. more details are on page 382 if you get confused rereading this sometime in the future | ||
| + | * Circulation with Demands and Lower Bounds | ||
| + | * Same givens as last problem | ||
| + | * except!!!! we have lower bounds on each edge | ||
| + | * algorithm on page 384 | ||
| + | * Here's how we do | ||
| + | * we set teh flow along an edge to be the lower bound and then we update the demand on both nodes attached to it. | ||
| + | * the rest is self explanatory | ||
