Problem 9: Question # C Consider the graph given above. Use the nearest neighbor

Question

Problem 9: Question # C

Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex T.

a. List the vertices in this Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends.

Answer - TSQRT

b. What is the total weight along this Hamiltonian circuit?

Answer - 62

Now use the sorted edges algorithm to find a Hamiltonian circuit.

c. List the weights in this Hamiltonian circuit in the order they are chosen by the algorithm.

Answer: ________________________

Explanation / Answer

Sorting the edges
SQ(13), ST(14), TQ(15), SR(16), RQ(17), TR(18)
Choosing edges for hamiltonian path
SQ, ST, RQ, TR
Weights chosen
13,14,17,18

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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