Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Next revisionBoth sides next revision | ||
| courses:cs211:winter2012:journals:paul:home [2012/04/04 17:36] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 01:19] – [Chapter 7] nguyenp | ||
|---|---|---|---|
| Line 757: | Line 757: | ||
| * Cut: s-t cut is a partition (A,B) where s is in A and t is in B | * 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 | * Problem: Find an s-t cut of minimum capacity | ||
| + | * The capacity of a cut is the sum of all the possible stuff that can go through the edge at once | ||
| + | * Flow Value Lemma: Let f be any flow, and let (A, B) be any s-t cut. Then, the value of the flow is = f_out(A) – f_in(A). | ||
| + | * Weak Duality: let f be any flow and let (A, B) be any s-t cut. Then the value of the flow is at most the cut’s capacity. | ||
| + | * Corollary: Let f be any flow, and let (A, B) be any cut. If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut | ||
| * | * | ||
