308-360 Tutorial #5

Question 1 - Let f be a flow. Given two subsets X,Y in V , define
f(X,Y) = sum_allxinX (sum_allyinY ( f(x,y) ) )
Question 1 - Let f be a flow. Given two subsets X,Y in V , All of these proofs use arithmetic and the properties of flows-- no induction is required!

1.1 - Prove that f(X,X) = 0

f(X,X) = sum_allxinX (sum_allyinX ( f(x,y) ) ) (by definition)
f(X,X) = [2 * sum_xinX (sum_yinX ( f(x,y) ) )] / 2
f(X,X) = [sum_xinX (sum_yinX ( f(x,y) ) ) + sum_xinX (sum_yinX (f(x,y)))]/2 (multiply out)
f(X,X) = [sum_xinX (sum_yinX ( f(x,y) ) ) + sum_yinX (sum_xinX (f(y,x)))]/2 (variable renaming, 2nd term)
f(X,X) = [sum_xinX (sum_yinX ( f(x,y) ) ) + sum_xinX (sum_yinX (f(y,x)))]/2 (switch order of summands, 2nd term)
f(X,X) = [sum_xinX (sum_yinX ( f(x,y) + f(y,x) ))]/2
f(X,X) = [sum_xinX (sum_yinX ( 0 ))]/2 (skew symmetry)
f(X,X) = 0.

* Note: this is much easier to prove using the result from 1.2
1.2 - Prove that f(X,Y) = -f(Y,X)

f(X,Y) = sum_xinX (sum_yinY ( f(x,y) ) ) (by definition)
f(X,Y) = sum_xinX (sum_yinY (- f(y,x) ) ) (skew symmetry)
f(X,Y) = - sum_xinX (sum_yinY (f(y,x) ) )
f(X,Y) = - f(Y,X). (by definition).
1.3 - Suppose Y intersect Z = 0. Prove that f(X,Y union Z) = f(X,Y) + f(X,Z)

f(X,Y union Z) = sum_xinX (sum_yinYunionZ ( f(x,y) ) )
f(X,Y union Z) = sum_xinX (sum_yinY ( f(x,y)) + sum_yinZ(f(x,y))) (since Y and Z are disjoint)
f(X,Y union Z) = sum_xinX (sum_yinY ( f(x,y))) + sum_xinX (sum_yinZ ( f(x,y)))
f(X,Y union Z) = f(X,Y) + f(X,Z).
1.4 - Prove that if X is a subset of Y, then f(X,Y) = f(X,Y-X)

Let Z = Y-X. Then:

f(X,Y) = sum_xinX(sum_yinY(f(x,y)))
f(X,Y) = sum_xinX(sum_yinZ (f(x,y)) + sum_yinX(f(x,y))) (since Z union X = Y and Z intersect X = 0)
f(X,Y) = sum_xinX(sum_yinZ (f(x,y))) + sum_xinX( sum_yinX(f(x,y)))
f(X,Y = su sum_xinX(sum_yinZ (f(x,y))) + 0 (result from 1.1)
1.5 - Prove that if X is in V-{s,t}, then f(X,V) = 0

f(X,V) = sum_xinX(sum_vinV(f(x,v)))
f(X,V) = sum_xinX( 0 ) (by flow conservation, since x is in V-{s,t} for all x)
f(X,V) = 0.
Now prove that if (S,T) is a cut such that s is in S and t is in T, then f(S,T) = |f|.
Since (S,T) is a cut, we know that S and T are disjoint, so:

f(S,T) = f(S,T union S) - f(S,S) (by 1.3)
f(S,T) = f(S,T union S) - 0 (by 1.1)
f(S,T) = f(S,T union S)
f(S,T) = f(S,V).

Let S' = S-{s}. Now we can use 1.5 to get:

f(S,T) = f(S,V)
f(S,T) = sum_xinS(sum_vinV(f(x,v)))
f(S,T) = sumvinV(f(s,v)) + sum_xinS'(sum_vinV(f(x,v))
f(S,T) = |f| + sum_xinS'(sum_vinV(f(x,v)) (by definition of |f|)
f(S,T) = |f| + 0 = |f|. (by 1.5)
Question 2 - Lef f be a flow in a network and let a be a real number. The scalar flow product af is a function from V x V to R defined by:
(af)(u,v) = a * f(u,v)
Prove that the flows in a network form a convex set by showing that if f_1 and f_2 are flows, then so is a f_1 + (1 - a) f_2 for all a in the range 0 <= a <= 1.
We will show that a f_1 +(1 - a) f_2 satisfies all the properties of a flow.

capacity constraint

The functions f_1 and f_2 are flows, so it follows that f_1(u,v) <= c(u,v) and f_2(u,v) <= c(u,v) for all u , v . The remainder of the proof is straightforward manipulation:

(a f_1 +(1 - a) f_2)(u,v) = (a f_1)(u,v) + ((1-a)f_2)(u,v)
(a f_1 +(1 - a) f_2)(u,v) = a * f_1(u,v) + (1-a) * f_2(u,v)
(a f_1 +(1 - a) f_2)(u,v) <= a * c(u,v) + (1 - a) * c(u,v)
(a f_1 +(1 - a) f_2)(u,v) <= 1 * c(u,v) = c(u,v).

The skew semmetric property and the flow conservation property can be proven in a similar way.
Question 4 -- Suppose that all capacities are either zero of one. Show that the FordFulkerson algorithm will run in O(VE) time.
The outline of the Ford Fulkerson method is given below:

  1. initialize flow f to 0
  2. for each augmenting path p, augment flow f along p
  3. return f
The augmenting step clearly takes O(|p|) steps, where |p| is the number of vertices in the path. The maximum number of vertices in the path is bounded by |V|, so the augmenting step takes O(|V|) time.

Now, consider an edge e in the flow network. It has a value of either 0 or 1. If e is a part of the ith augmenting path, then clearly this edge cannot be be part of the jth augmenting path, for j > 1. There are exactly |E| edges, in the graph, so therefore there can be at most |E| iterations of the loop. Thus the algorithm has time complexity O(VE).