308-360 Tutorial #9

For the Friday tutorial, we will look at the questions during the last tutorial.

1. and 2. Write your own. Email me your answer if you think you want it verified. For 1., answer 'what' and 'how'. i.e. a possible point could be: "A lower bound is a ***** on a ***** such that ************". You fill in the blanks.

3. Prove len(t) >= weight(T*) + D[x1,y], for all tours t, where T* is a minimum spanning tree for full vertex set X and y is a nearest neighbour of x1 (ie. D[x1,y] <= D[x1,xi], for all xi neighbours of x1).

Let t be any valid tour visiting all cities, t = x1,x2,...,xn,x1. Recall that a tour is simply a spanning tree for all the cities when you remove one of the edges from the tour.

So let spanning tree T = (x2,x3),...,(xn-1,xn),(xn,x1) by not including the edge (x1,x2). Note that the spanning tree is a path. So our tour t = (x1,x2) + T and weight(T) = sum of weights of edges of T.

So, len(t) = len((x1,x2) + T) = D[x1,x2] + weight(T).

len(t) >= weight(T*) + D[x1,y]
D[x1,x2] + weight(T) >= weight(T*) + D[x1,y]

Suppose this isn't true. We know that weight(T) >= weight(T*), because T and T* are spanning trees of X and T* is a minimum weight spanning tree. So, if the statement isn't true, then D[x1,x2] must be less than D[x1,y]. But this is a contradiction because y is defined as a nearest neighbour of x1.

4. Let L1 be the 1-tree bound for D and let L be the bound defined in question 3. Prove that L <= L1.

Recall that a 1-tree lower bound is equal to the weight of a minimal spanning tree for all but one city x plus the weights of two edges adjacent to x.

Let x1 be the vertex(city) we leave out. So let T' be the MST for X-{x1}.

1-tree lower bound L1 = weight(T') + D[x1,u] + D[x1,v], where u and v are two vertices adjacent to x1 (u<>v).

Since L = weight(T*) + D[x1,y], where T* is an MST for X and y is a nearest neighbour of x1, we can rewrite the statement we are trying to prove.
L <= L1
weight(T*) + D[x1,y] <= weight(T') + D[x1,u] + D[x1,v]

T = T' + (x1,u) is a spanning tree for X, because T' is a spanning tree for X-{x1} and (x1,u) attaches x1 to T' to make a spanning tree for all X.
weight(T*) + D[x1,y] <= weight(T) + D[x1,v]

This is just like the proof for question 3. Suppose that this does not hold. We know that weight(T*) <= weight(T), because T* is an MST for X, and T is a (possibly mimimal, but not necessarily) spanning tree for X. Given that fact, for the statement not to hold, D[x1,v] must be less than D[x1,y]. This is a contradiction because y is defined as a nearest neighbour of x1, so the D[x1,v] cannot be smaller than the distance between x1 and its nearest neighbour y.