23. Consider this graph showing distances between locations: 80 40 30 20 25 a. D

Question

23. Consider this graph showing distances between locations: 80 40 30 20 25 a. Describe the nearest neighbor tour starting at vertex B and give the total distance. b. In creating a cheapest-link tour: (i) Which is the first edge you would include? (ii) Which is the second edge you would include? (iii) Which is the third edge you would include? (iv) Which is the last edge you would include? (iv) Draw the resulting graph, list the vertices of the cheapest-link tour starting with vertex A, and give the total distance.

Explanation / Answer

a)nearest neighbor tour starting from B.

B-D Distance is :20

D-A Distance is :40

A-C Distance is ;80

Total distance is : 20+40+80=140 if we started from B

b)in creating cheapest-link tour A-B-C-D IS cheapest tour:

30+25+60=115

i)A

ii)B

iii)C

iv)D

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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