Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2014:journals:haley:chapter7 [2014/04/02 04:04] – created archermcclellanh | courses:cs211:winter2014:journals:haley:chapter7 [2014/04/02 05:20] (current) – archermcclellanh | ||
|---|---|---|---|
| Line 21: | Line 21: | ||
| * For each edge e, f(e) is 0 initially | * For each edge e, f(e) is 0 initially | ||
| * While an s-t path remains in the residual graph | * While an s-t path remains in the residual graph | ||
| - | | + | |
| + | * f' = augment(f, | ||
| + | * f = f' | ||
| + | * the residual graph is the residual graph of f' | ||
| + | * We use augment(f, | ||
| + | * b = bottleneck(P, | ||
| + | * for each (u,v)-edge e in P, | ||
| + | * if e is a forward edge, increase f(e)+ = b | ||
| + | * else e = v,u and f(e) - = b | ||
| + | * return f | ||
| + | * If all capacities, this algorithm (the Ford-Fulkerson algorithm) terminates in C ( = sum(c_e) for all out edges of s) iterations of the while-loop | ||
| + | * And it can be implemented in O(mC) time | ||
| + | * Wordy but interesting, | ||
| - | ===== 7.2: Maximum Flow & Ford-Fulkerson | + | ===== 7.2: Network Flows & Minimum Cuts ===== |
| + | * Consider an s-t cut: a partition (A,B) of V such that s∈A and t∈B. The capacity of an (A,B) cut, or c(A,B) is the sum of all c_e for each out edge e of A. | ||
| + | * For an s-t flow and an s-t cut (A,B), v(f) = the out flow of A - the in-flow of A | ||
| + | * For any s-t flow and any s-t cut (A,B), v(f) < = c(A,B). | ||
| + | * If f is an s-t flow so that the residual graph has no s-t path, there is an s-t cut (_A,_B) in G so that f(v) = c(_A,_B). Then, v(f) is the maximum of all flows in G and (_A,_B) has the minimum capacity of any s-t cut. | ||
| + | * the Ford-Fulkerson flow is a maximum flow | ||
| + | * Reminded me of real analysis, straightforward, | ||
| - | ===== 7.5: Maximum Flow & Ford-Fulkerson | + | ===== 7.5: Bipartite Matching |
| + | * We wish to match edges to a subset such that each node appears in max one edge of the edge subset, such that the matching has the largest possible size. | ||
| + | * We solve this as follows: | ||
| + | * Look at G, constructing a flow network by directing all edges in G from X to Y, then adding a node s and an (s,x) edge from s to each node in X. We add a node t and an edge (y,t) from every edge in Y to t. We give every edge in the flow network a capacity of 1. Then we compute the maximum s-t flow. | ||
| + | * The size of the maximum matching in G equals the max flow in the flow network G' and edges carrying flow from X to Y in G' are in the matching in G. | ||
| + | * We can do this in O(mn) time. | ||
| + | * What if the graph has no perfect matching? | ||
| + | * If this // | ||
| + | * Either we can find a perfect matching or an appropriate subset _G in O(mn) time. | ||
| + | * 4/10 | ||
| - | ===== 7.7: Maximum Flow & Ford-Fulkerson | + | ===== 7.7: Maximum Flow Extensions |
| + | * What if we have a set of sources and a set of sinks? | ||
| + | * Consider the case where sources have fixed supply and sinks have fixed demand, like rainway lines shipping from factories to retail outlets. | ||
| + | * Now the circulation fulfills | ||
| + | * for each edge e, 0< | ||
| + | * for each vertex v, the in minus out flows equal the demand of v. | ||
| + | * We can also do this with circulations that have lower bounds for demand. | ||
| + | * Boring and wordy, 2/10 | ||
