9 Consider the graph given above Use the nearest neighbor al

9)

Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex W. 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

Nearest Neighbor Algorithm:applied to the vertex W

start from W
repeat:
        visit the nearest neighbor that hasn\'t been visited yet
return to home when no other choice is available

(a) The Hamiltonian circuit obtained applying the nearest neighbour algorithm is

W->U->V->T->W

(b) Total length = 18+20+23+21= 82

Sorted-Edges Algorithm

(c) In this graph, the sorted edges in the increasing order are

WU,WV,UV,WT,TU and TV with weights 18,19,20,21,22 and 23 respectively.

Applying the algorithm,

WU (18), WV (19) are selected.

UV (20) is rejected as it would form a circuit (omitting the vertex T)

The next edge WT (21) is rejected as it would cause W to bave degree 3

So we choose the edges TU (22) and TV (23) in succession

(c) the weights chosen are 18,19,22,23

(d) total weight =82