Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
| courses:cs211:winter2012:journals:paul:home [2012/04/04 17:26] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/04 17:36] – [Chapter 7] nguyenp | ||
|---|---|---|---|
| Line 749: | Line 749: | ||
| * The Ford-Fulkerson Algorithm uses residual edges and works awesomely (optimal) | * The Ford-Fulkerson Algorithm uses residual edges and works awesomely (optimal) | ||
| * page 342 - 344 | * page 342 - 344 | ||
| - | | + | * Informal explanation |
| + | * graphs | ||
| + | * keep updating the residual edges using the following formula: | ||
| + | * If edge is the same as it was originally, set the forward rate to the bottle neck + original rate (which is the edge with the smallest flow rate) | ||
| + | * Otherwise, set the backwards residual rate to what it originally was minus the bottle neck | ||
| + | * Section 7.2 - Maximum Flows and Minimmum Cuts in a Network | ||
| + | * Cut: s-t cut is a partition (A,B) where s is in A and t is in B | ||
| + | * Problem: Find an s-t cut of minimum capacity | ||
| + | | ||
