There are 4 possible triangles in this graph, enumerated below.

Triangle 1,2,4

d(1,2) + d(2,4) >= d(1,4) 1 + 2 >= 3, inequality holds

d(1,4) + d(4,2) >= d(1,2) 3 + 2 >= 1, inequality holds

d(1,1) + d(4,2) >= d(4,2) 1+ 2 >= 2, inequality holds

Triangle 1,2,3

d(1,2) + d(2,3) >= d(1,3) 1 + 1 >= 2, inequality holds

d(2,3) + d(1, 3) >= d(1,2) 1 + 2 >= 1, inequality holds

d(1,2) + d(1,3) >= d(3,2) 1+ 2 >= 1, inequality holds

Triangle 1,3,4

d(1,3) + d(1,4) >= d(4,3) 2 + 3 >= 1, inequality holds

d(1,3) + d(3, 4) >= d(1,4) 2 + 1 >= 3, inequality holds

d(1,4) + d(3,4) >= d(1,3) 3+ 1 >= 2, inequality holds

Triangle 2,3,4

d(2,3) + d(3,4) >= d(2,4) 1 + 1 >= 2, inequality holds

d(2,4) + d(3, 4) >= d(2,3) 2 + 1 >= 1, inequality holds

d(2,3) + d(2,4) >= d(3,4) 1+ 2 >= 1, inequality holds

Thus, all the edges in the graph obey the triangle inequality.

APPROX-TSP-TOUR:

Pick vertex 1 to be the root.

Q - 1, 0, 0 2, inf, NILL 3, inf, NILL 4, inf, NILL

Q!=0 Loop 1 U = 1,0,0 V = 2 , 0+1 < inf, true V = 3 , 0+2 < inf, true V = 4 , 0+3 < inf, true

Q -

2, 1, 1 3, 2, 1 4, 3, 1

Q!=0 Loop 2 U = 2,1,1 V = 3 , 1+1 < 2, true V = 4 , 1+2 < 3, false

Q -

3, 2, 1 4, 3, 1

Q!=0 Loop 3 U = 3,1,1 V = 4 , 1+2 < 3, false

Q -

4, 3, 1

Q!=0 Loop 4 U = 4,3,1 V = empty set

MST-PRIM returns {1,2,3,4}

Traversal would be 1,2,3,4 if we’re ordering by the size. Cost of tree traversal for this route is 1 + 1 + 1 + 3 = 6 (the last 3 is to go back to the root)

G = (V, E), V = {1, 2, 3, 4}, E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}, w = {1, 2, 3, 1, 2, 1} The triangle inequality states that the sum of any two sides of a triangle is greater than or equal to the third side. We can verify that the graph obeys the triangle inequality as follows: (1, 2), (1, 3), (2, 3): 1 + 2 >= 1, 1 + 1 >= 2, 2 + 1 >= 1 (1, 2), (1, 4), (2, 4): 1 + 3 >= 2, 1 + 2 >= 3, 3 + 2 >= 1 (1, 3), (1, 4), (3, 4): 2 + 3 >= 1, 2 + 1 >= 3, 3 + 1 >= 2 (2, 3), (2, 4), (3, 4): 1 + 2 >= 1, 1 + 1 >= 2, 2 + 1 >= 1 Thus, the graph obeys the triangle inequality. APPROX-TSP-TOUR (abbreviated as ATT) would compute a tour on this graph as follows: ATT1: Select vertex to be root (arbitrarily choose r = 1) ATT2: Compute MST-PRIM(G, w, r) (abbreviated as MT) MT1-MT3: key = {infty, infty, infty, infty}, pi = {NIL, NIL, NIL, NIL} MT4-MT5: key = {0, infty, infty, infty}, pi = {0, NIL, NIL, NIL} MT6: Q = MAKE-QUEUE(G.V) = {1, 2, 3, 4} Loop 1 MT7-MT9: Q != 0, u = EXTRACT-MIN(Q) = 1, G.adj[u] = {2, 3, 4} v = 2 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 0 + 1 < infty -> true MT11-MT12: v.pi = 1, v.key = u.key + w(u, v) = 0 + 1 = 1 v = 3 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 0 + 2 < infty -> true MT11-MT12: v.pi = 1, v.key = u.key + w(u, v) = 0 + 2 = 2 v = 4 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 0 + 3 < infty -> true MT11-MT12: v.pi = 1, v.key = u.key + w(u, v) = 0 + 3 = 3 Loop 2 MT7-MT9: Q != 0, u = EXTRACT-MIN(Q) = 2, G.adj[u] = {1, 3, 4} v = 1 MT10: v not in Q -> false v = 3 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 1 + 1 < 2 -> false v = 4 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 1 + 2 < 3 -> false Loop 3 MT7-MT9: Q != 0, u = EXTRACT-MIN(Q) = 3, G.adj[u] = {1, 2, 4} v = 1 MT10: v not in Q -> false v = 2 MT10: v not in Q -> false v = 4 MT10: v in Q -> true, u.key + w(u, v) < v.key -> 2 + 1 < 3 -> false Loop 4 MT7-MT9: Q != 0, u = EXTRACT-MIN(Q) = 4, G.adj[u] = {1, 2, 3} v = 1 MT10: v not in Q -> false v = 2 MT10: v not in Q -> false v = 3 MT10: v not in Q -> false ATT2: return MST = {1, 2, 3, 4} ATT3: L = {1, 2, 3, 4} ATT4: H = {1, 2, 3, 4}