Please post your solutions to the May 4 In-Class Exercise to this thread.

Best,

Chris

Resource Description for Screen Shot 2022-05-04 at 5.47.08 PM.jpg

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}

<u>v = 2</u>

'''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

<u>v = 3</u>

'''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

<u>v = 4</u>

'''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}

<u>v = 1</u>

'''MT10:''' v not in Q -> false

<u>v = 3</u>

'''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 1 + 1 < 2 -> false

<u>v = 4</u>

'''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}

<u>v = 1</u>

'''MT10:''' v not in Q -> false

<u>v = 2</u>

'''MT10:''' v not in Q -> false

<u>v = 4</u>

'''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}

<u>v = 1</u>

'''MT10:''' v not in Q -> false

<u>v = 2</u>

'''MT10:''' v not in Q -> false

<u>v = 3</u>

'''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}

<nowiki> 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 were 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)

</nowiki>

<pre> ATT 1 root 1 ATT 2 -----> MST(G,w,1) u.key= {inf, inf, inf, inf} ; u.pi = {NIL, NIL, NIL, NIL} r.key = 0 r.pi = 0 Q = {1,2,3,4} while Q!=0 u = ExtractMin(Q) = 1 Q = {2,3,4} for each v in G.adj[u] {2,3,4} {2} 2 is in Q and inf+1 < inf 2.pi = 1 {0, 1, inf, inf} 2.key = 0 + 1 = 1 {0, 1, NIL, NIL} {3} 3 is in Q and 0+2 < inf 3.pi = 1 {0, 1, 1, inf} 3.key = 0 + 2 = 2 {0, 1, 2, NIL} {4} 4 is in Q and 0+3 < inf 4.pi = 1 {0, 1, 1, inf} 4.key = 0 + 3 = 3 {0, 1, 2, 3}

        u = ExtractMin(Q) = 2 Q = {3,4}
        for each v in G.adj[u] {1,4,3}
            {1} 1 is not in Q so no if execution
            {4} 4 is in Q and 1+2 !< 3 so no if execution
            {3} 3 is in Q and 1+1 !< 2 so no if execution

        u = ExtractMin(Q) = 3 Q = {4}
        for each v in G.adj[u] {1,2,4}
            {1} 1 is not in Q so no if execution
            {2} 2 is in Q  so no if execution
            {4} 4 is in Q and 2+1 !< 3 so no if execution      

        u = ExtractMin(Q) = 4 Q = {}
        for each v in G.adj[u] {1,2,3}
            {1} 1 is not in Q so no if execution
            {2} 2 is in Q  so no if execution
            {3} 3 is in Q so no if execution

returns {1,2,3,4} L = {1,2,3,4} H= {1,2,3,4}

Cost = 1+1+1+3 = 6 units </pre>