Lecture 17: Proof of Ford-Fulkerson
An s-t cut is a partition (A, B) of the vertex set such that s in A, t in B. The capacity of a cut (A, B) c(A,B) = sum(ce) for e from A to B.
Theorem 1: Let f be an s-t flow and (A,B) be an s-t cut. Then value(f) <= c(A,B).
Proof: value(f) = fout(A) - fin(A) <= fout(A) = sum(f(e)) of e out of A = sum(ce) of e out of A = c(A,B)
Theorem 2: Let f be an s-t flow and (A,B) be an s-t cut. Then value(f) <= c(any cut).
Proof: Let f be the flow by the Ford Fulkerson algorithm. Goal: find a cut q = (A*,B*) such that value(f) = c(q)
Theorem 3: If f is an flow such that there is no s-t path in the residual graph Gf, then f is a max flow.
Proof: Let A* be a set of all vertices such that there exists an s-v path in Gf. A* = {v | there exists s-v path in Gf}. B* = the remaining vertices. B = Gfvertices - A*. We know t is in B*. There is an edge e(u, v) in G* from A* to B*. f(e) = ce, otherwise v could be in A*. Consider e’(u’, v’) in G* from B* to A*. f(e) = 0 because otherwise there would be a backedge that force u’ into A*. All edges out of A are saturate with flow. All edges going into A* have no flow. Thus, value(f) = fout(A*) - fin = sum(f(e)) e of out of A* - sum(f(e)) e into A* = sum(f(e)) e of out of A* = sum(ce) e out of A* = c(A*, B*) = value of f, since all others flows f’ have value(f’) <= c(A*, B*). Thus, f is a max flow.
Conclusions: The max s-t flow has a value equal to the capacity of the min-cut. If all capacities are integers, then there is an optimal flow f such that f(e) is an integer for each edge e.