This is urgent, need help!!! Question 6 Recall most TSP heuristics require a gra

Question

This is urgent, need help!!! Question 6

Recall most TSP heuristics require a graph that is complete and undirected with arc costs that satisfy the triangle-inequality. We learned in Lecture 10 that a graph that is connected and symmetric can be converted to a graph with these characteristics. Suppose you have the graph below as a starting point. Then, (i) what edges need to be added to it to make it complete, and (ii) what should the costs on the new edges be, in order to satisfy the triangle-inequality?

Explanation / Answer

lets consider labels of edges as 1,2,3,4 in clock-wise and middle vertex as 5

graph is not complete because every two vertices must be connected, in this graph (1,3) vertices and (2,4) vertices has no edge connecting them so these vertices are not connected.

For this graph to be complete edges need to be established between 1 and 3 vertices, 2 and 4 vertices.

costs on these edges must satisfy triangle in equality, So

edge between 1 and 3 should be less than 11 + 5.

edge between 2 and 4 should be less than 10 + 7

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.