Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:haley:chapter7 [2014/04/02 04:50] – archermcclellanh | courses:cs211:winter2014:journals:haley:chapter7 [2014/04/02 05:20] (current) – archermcclellanh | ||
|---|---|---|---|
| Line 33: | Line 33: | ||
| * 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 | * 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 | * And it can be implemented in O(mC) time | ||
| + | * Wordy but interesting, | ||
| ===== 7.2: Network Flows & Minimum Cuts ===== | ===== 7.2: Network Flows & Minimum Cuts ===== | ||
| Line 41: | Line 42: | ||
| * 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. | * 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 | * the Ford-Fulkerson flow is a maximum flow | ||
| + | * Reminded me of real analysis, straightforward, | ||
| ===== 7.5: Bipartite Matching ===== | ===== 7.5: Bipartite Matching ===== | ||
| - | * We wish to | + | * 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 | ||
