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:24] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/04 17:35] – [Chapter 7] nguyenp | ||
---|---|---|---|
Line 747: | Line 747: | ||
* We don't have to use all of it at once | * We don't have to use all of it at once | ||
* Residual edge is one where you have some going one way and some going the other | * Residual edge is one where you have some going one way and some going the other | ||
- | * | + | |
+ | * 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 | ||
+ | |