Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2011:journals:andrew:chapter7 [2011/04/05 23:26] – created bennetta | courses:cs211:winter2011:journals:andrew:chapter7 [2011/04/05 23:51] (current) – bennetta | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ===== 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ===== | ===== 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ===== | ||
| + | |||
| + | | ||
| + | | ||
| + | *Sink nodes absorb traffic | ||
| + | | ||
| + | * Capacity shows the maximum amount of flow an edge can take | ||
| + | * Flow is the amount of flow that is on the edge currently | ||
| + | * Flow is always less than or equal to capacity | ||
| + | * Flow Network - directed graph: | ||
| + | * Each edge has a capacity which is a non-negative number | ||
| + | * There is a single source node s | ||
| + | * There is a single sink node t | ||
| + | * No edge enters the source node and no edge exits the sink node | ||
| + | * There is at least one edge incident to each node | ||
| + | * All capacities are integers | ||
| + | * Maximum flow problem: | ||
| + | * Given a flow network, arrange the traffic so that use of the available capacity is as efficient as possible | ||
| + | * Closely related to finding the value of the minimum cut | ||
| + | * Use of a residual graph helps to solve this problem: | ||
| + | * On page 342 you can find the algorithm augment(f, | ||
| + | * The results of augment(f, | ||
| + | * Algorithm can be implemented in O(mC) running time | ||
| + | |||
| + | ===== 7.2: Maximum Flows and Minimum Cuts in a Network ===== | ||
| + | *This subchapter continues analysis of the Ford-Fulkerson Algorithm discussed above in subchapter 7.1 | ||
| + | *Use a cut to place upper bounds on max-flow | ||
| + | | ||
| + | *We now make a cut between these two sets where the capacity of this cut is the sum of the capacities of all the edges out of A. | ||
| + | *Max flow therefore equals min cut. | ||
| + | |||
| + | ===== 7.3: Choosing Good Augmenting Paths ===== | ||
| + | *Any way of choosing an augmenting path increases the value of the flow. | ||
| + | *With a better path choice the algorithm can be significantly improved. | ||
| + | *The Scaling Max-Flow algorithm can be found from 353-354 | ||
| + | *This algorithm can run in at most O(m^2log2C) time. | ||
| + | |||
| + | ===== Final Thoughts ===== | ||
| + | As this semester draws to a close I reflect with pride on everything I've accomplished in algorithms. This has been easily the hardest class I've taken in my time here at W&L but by increasing the amount of effort and time I spent on this class I was able to make a huge turn around from my initial average. This last reading assignment was probably the easiest for me as I've finally come around to being able to really understand the material the first time. Readability: | ||
