Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 18:12] – zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 20:59] (current) – [7.3 Choosing Good Augmenting Paths] zhongc
@@ Line 1: / Line 1: @@
-======  7.1-7.2 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
+======  7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
 The Problem Motivation:
@@ Line 60: / Line 60: @@
 f has the maximum value of any flow in G, and (A*, B*) has the minimum
 capacity of any s-t cut in G.
+useful lemma,
+Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) =fin(B) -f°Ut(B).
+Pf on P374.
+If f is an s-t-flow such that there is no s-t path in the residual graph
+then there is an s-t cut (A*,B*) in G for which v(f) = c(A*, B*). Consequently,
+f has the maximum value of any flow in G, and (A*, B*) has the minimum
+capacity of any s-t cut in G. .....
+Proof. The statement claims the existence of a cut satisfying a certain desirable
+property; thus we must now identify such a cut. To this end, let A* denote the
+set of all nodes v in G for which there is an s-v path in @. Let B* denote.~e
+set of all other nodes: B* = V - A*.
+Runtime analysis:
+O(Cm)
+Intereting/readable: 6/6
+====== 7.3 Choosing Good Augmenting Paths ======
+Big idea: Good choice of augmentation path can improve bounds significantly.
+augmentation increases the value of the maximum
+flow by the bottleneck capacity of the selected path; so if we choose paths
+with large bottleneck capacity, we will be making a lot of progress.
+maintain a so-called scaling parameter to avoid looking at exactly the largest bottleneck
+P379
+The algorithms on  p380
+analysis of the running time:
+The number of iterations o[ the outer While loop is at most 1 +[log2 C].
+we are using paths that augment the flow by a great amount, and so there should be relatively few augmentations.
+Let f be the [low at the end of the A-scaling phase. There is an s-t
+cut (A, B) in G for which c(A, B) < v(f) + mA, where m is the number of edges
+in the graph G. Consequently, the maximum [low in the network has value at
+most v(f) + m A.
+Proof on P380.
+Interesting/readable: 5/6