Lecture23_NetworkFlows2
Friday, October 23, 2020
1:44 PM
Recap:
• Flowvalue:|f|=f(s,V).
• Cut: Any partition (S, T) of V such that s ∈ S and t ∈ T.
• Lemma. | f | = f (S, T) for any cut (S, T).
• Corollary. | f | <= c(S, T) for any cut (S, T).
• Residual graph: The graph Gf = (V, Ef ) with strictly positive residual capacities cf (u, v)
= c(u, v) – f (u, v) > 0.
• Augmenting path: Any path from s to t in Gf.
Max-flow, min-cut theorem
Theorem. The following are equivalent: 1. | f | = c(S, T) for some cut (S, T). 2. f is a maximum flow.
3. f admits no augmenting paths.
• These three statements are equivalent.
Proof.
(1) -> (2): Since | f | <= c(S, T) for any cut (S, T) (by the corollary from Lecture 22), the assumption that | f | = c(S, T) implies that f is a maximum flow.
• The flow value could never exceed the capacity of any cut. It is the upper bound!
(2) -> (3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f.
• The contra positive statement: if there wasn’t an augmenting path, it wouldn’t be a maximum flow – > definition of augmenting path
• If the augmenting path is 1, we can improve the flow.
(3) -> (1): Suppose that f admits no augmenting paths. Define S = {v ∈ V : there exists a path in Gf from s to v}, and let T = V – S. Observe that s ∈ S and t ∈ T, and thus (S, T) is a cut. Consider any vertices u ∈ S and v ∈ T.
We must have cf (u, v) = 0, since if cf (u, v) > 0, then v ∈ S, not v ∈ T as assumed. Thus, f (u, v) = c(u, v), since cf (u, v) = c(u, v) – f (u, v). Summing over all u ∈ S and v ∈ T yields f (S, T) = c(S, T), and since | f | = f (S, T), the theorem follows.
• The path is the bottom neck
Ford-Fulkerson max-flow algorithm
➢Non-existing of augmenting path implies that we had the best solution • How many augmentation should we expect?
Each time we doing an augmentation, and the augmentation depends on the critical assignment, the critical edge of the augmenting path.
-> it could be very slow!!
○Based on edge values not the number of vertices ○Based on capacity values
➢We do not prefer the running time depends on those values
Edmonds-Karp algorithm
breadth-first augmenting path: a shortest path in Gf from s to t where each edge has weight 1. These implementations would always run relatively fast.
Since a breadth-first augmenting path can be found in O(E) time, their analysis, which provided the first polynomial-time bound on maximum flow, focuses on bounding the number of flow augmentations.
Analysis of Algorithms Page 1
number of flow augmentations.
• How do we pick the augmenting path
Monotonicity lemma
• Notice: residual network is constantly changing. Every time we have new flow assignment, we have a modification of residual network.
• Consider a flow before an augmentation and after an augmentation.
Case1
Case2:
• What we are trying to show here is that we are making progress: by the monotonicity we established, we are improve by 2.
• Imaging that we have a graph with shortest paths defined, veery time we perform an augmentation, many of the vertices’ value are going up, they can go up at most n – 1. (upper bound)
If they reaches the upper bound, we can say we can’t improve more
Counting flow augmentations
• Every time we do augmentation there must be at least one critical edge, and that edge would cause at least one vertex go up by 2. Hence, this particular edge can repeatedly appear and disappear at most n – 1 times.
• Shortest value start 0 potentially, and it went up all the way to n – 1 until that vertex become unreachable and not a part of the augmentation.
➢Every edge can be a critical edge for at most O(n) augmentations. Since we have O(E) Analysis of Algorithms Page 2
➢Every edge can be a critical edge for at most O(n) augmentations. Since we have O(E) number of edges, O(VE) = all possible augmentations.
Running time of Edmonds-Karp
Distances start out nonnegative, never decrease, and are at most |V| – 1 until the vertex becomes unreachable. Thus, (u, v) occurs as a critical edge O(V) times, because δ(v)
increases by at least 2 between occurrences. Since the residual graph contains O(E) edges, the number of flow augmentations is O(V E).
Best to Date
Analysis of Algorithms Page 3