Recall this flow network and flow
s->v1[11/16]
v1->v3[12/12]
Copyright By PowCoder代写 加微信 powcoder
v3->t[15/20]
s->v2[8/13]
v2->v4[11/14]
v4->t[4/4]
v2->v1[1/4]
v3->v2[4/9]
v4->v3[7/7]
Remember from last week that we can’t find augmenting paths in such a network and hope to get the max flow every time. Instead, we write out the residual network and then find augmenting paths in there instead.
The residual network for this network is as follows.
v3->v1[12]
v4->v2[11]
Now, find an augmenting path in here. Here is one:
s->v2->v3->t
The minimum capacity of this path is 4. Let’s take the original flow network and add 4 to forward edges and subtract 4 from backward edges.
s->v1[11/16]
v1->v3[12/12]
v3->t[19/20]
s->v2[12/13]
v2->v4[11/14]
v4->t[4/4]
v2->v1[1/4]
v3->v2[0/9]
v4->v3[7/7]
Now our flow value is 23 (better than 19!). Construct the new residual network and try to find another augmenting path in there: you won’t find one. This means that the flow value is maximum.
Note: every time the flow changes, you have to compute a new residual network. A residual network changes whenever the flow changes.
This path allowed us to increase our flow from 19 to 23.
Why are these paths guaranteed to increase our flow?
Because these paths always start like this: s->…->……
So more flow leaves s after the augmentation than before.
-make residual network
-find an augmenting path in residual network from s to t
-augment in the original network along that path
-Repeat: form new residual network, find next augmenting path in there, use it in original network… … …
-Stop when there are no more augmenting paths in residual network
———-
We want to prove that Ford-Fulkerson is correct.
This involves two parts of an if-and-only-if proof.
1. If f is a maximum flow, then the residual network has no augmenting paths.
2. If the residual network has no augmenting paths, then f is a maximum flow.
We can do part 1 now:
1. If f is a maximum flow, then the residual network has no augmenting paths.
The proof is by contradiction: suppose that f is a maximum flow but that the residual network _does_ have some augmenting path. Well, then you can use that augmenting path to get a flow that is better than the maximum. This is the contradiction.
For part 2, we introduce cuts and use cuts to prove part 2.
———-
Recall this flow with value 19.
s->v1[11/16]
v1->v3[12/12]
v3->t[15/20]
s->v2[8/13]
v2->v4[11/14]
v4->t[4/4]
v2->v1[1/4]
v3->v2[4/9]
v4->v3[7/7]
Now consider cut ({s, v1, v2}, {v3, v4, t})
Flow across cut: 12+11-4 = 19
Capacity of cut: 12+14 = 26
Two interesting findings:
-The flow across this cut equals the value of the flow
-The capacity of the cut is >= the value of the flow
We can prove that in fact these are not coincidences. They will always be true.
———-
Prove that for any flow f and cut (S, T), we have |f| <= c(S, T).
There are some similarities with this proof and the big-oh proofs from CSC236. In both cases, you are upper-bounding a value.
|f| = f(S, T) (I didn't prove this; check the book for the proof)
= \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T} f(v, u) (definition of flow across cut)
<= \sum_{u \in S} \sum_{v \in T} f(u, v) (removing a bunch of negative terms, since all flow values are >= 0 by the capacity constraint)
<= \sum_{u \in S} \sum_{v \in T} c(u, v) (capacity constraint; flow is less than capacity)
= c(S, T) (definition of the capacity of a cut)
----------
OK. Now back to proving that Ford-Fulkerson is correct. Specifically, we were left with this:
2. If the residual network has no augmenting paths, then f is a maximum flow.
This can be proved as follows, in two steps:
A. Prove that if the residual network has no augmenting paths then |f| = c(S, T) for some cut (S, T)
For this part, you must exhibit a cut whose capacity equals the value of the flow. You can use the fact that the residual network has no augmenting paths.
B. Prove that if |f| = c(S, T) for some cut (S, T), then f is a maximum flow
We proved both of these using slides!
----------
What is the max flow in this flow network? 2000000
s->u[0/1000000]
u->t[0/1000000]
s->v[0/1000000]
v->t[0/1000000]
Form residual network
s->u[1000000]
u->t[1000000]
s->v[1000000]
v->t[1000000]
Find me a terrible path in this residual network: s->u->v->t. Minimum capacity on this path is 1
New flow network (flow value is now 1)
s->u[1/1000000]
u->t[0/1000000]
s->v[0/1000000]
v->t[1/1000000]
New residual network
s->u[999999]
u->t[1000000]
s->v[1000000]
v->t[999999]
Find me another terrible path please: s->v->u->t
New flow network is now (flow value is 2)
s->u[1/1000000]
u->t[1/1000000]
s->v[1/1000000]
v->t[1/1000000]
I can keep going and get flow 3, 4, 5, 6…
Our method is correct, but we need to do something about the runtime.