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/06 01:19] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 01:20] – [Chapter 7] nguyenp | ||
---|---|---|---|
Line 761: | Line 761: | ||
* 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. | * 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 | * 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 | ||
+ | * Augmenting path theorem: Flow f is a max flow iff there are no augmenting paths | ||
+ | * Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. | ||
* | * |