Use the following diagram and situation to answer questions 9 10 A delivery truc

Question

Use the following diagram and situation to answer questions 9 10 A delivery truck must deliver packages to five different store locations (A, B, C, D, and E)The trip must start and end at A. The graph below shows the distances (in miles) between locations. We want to minimize the total distance traveled. 30 10 Eo 15 25 12 9) How many different Hamilton circuits would we have to check if we used the brute-force algorithm? Explain how you determined your answer The repetitive nearest-neighbor algorithm applied to the graph yields the following solution edges (including weights) you use in the order you use them from EACH AND EVERY vertex (hence the name REPETITIVE nearest neighbor) Credit will not be awarded for providing only an answer. 10) Show your work by indicating the FROM A FROM B FROM C FROM D FROM E

Explanation / Answer

9. Total 24 number of Hamilton circuit can be drawn because it has 5 vertices and 10 edges so here degree of the vertices is (5-1)=4 degree. And total number of hamilton circuit are 4!=24.

10. FROM A the edges are A-C-D-B-E-A so the minimum cost is 8+3+7+15+30=63(in miles)

FROM B the  edges are B-C-D-A-E-B so the minimum cost is 5+3+15+30+15=68(in miles).

  FROM C the  edges are C-D-B-A-E-C so the minimum cost is 3+7+10+30+12=62(in miles).

  FROM D the  edges are D-C-B-A-E-D so the minimum cost is 3+5+10+30+25=73(in miles).

  FROM E the  edges are E-C-D-B-A-E so the minimum cost is 12+3+7+10+30=62(in miles).

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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