10 Consider the graph given above Use the nearest neighbor a

(10)

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

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.

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

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.

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

Solution

a) as per nearest neighbour algorithm

route is

J-O-L-N-K-M-J

b)Total weight along hamiltonian circuit =142

c)By sorted edges algorithm

order is J-O-N-M-L-K-J

d) 105

Thank you