308-360 Tutorial #5

Question 1 - Let

Question 1 - Letf(X,Y) = sum_allxinX (sum_allyinY ( f(x,y) ) )

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

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).

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).

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)

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.

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

Prove that the flows in a network form a convex set by showing that if(af)(u,v) = a * f(u,v)

We will show thata f_1 +(1 - a) f_2satisfies all the properties of a flow.

capacity constraint

The functionsf_1andf_2are flows, so it follows thatf_1(u,v) <= c(u,v)andf_2(u,v) <= c(u,v)for allu , 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:

The augmenting step clearly takes

- initialize flow
fto0- for each augmenting path
p, augment flowfalongp- return f
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 takesO(|V|)time.

Now, consider an edgeein the flow network. It has a value of either 0 or 1. Ifeis a part of theith augmenting path, then clearly this edge cannot be be part of thejth augmenting path, forj > 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 complexityO(VE).