-- May 4 In-Class Exercise Thread
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}
(
Edited: 2022-05-04)
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}