Consider the graph given above Use the sorted edges algorith

Consider the graph given above. Use the sorted edges algorithm to find a Hamiltonian circuit.

a. List the weights of the edges separated by commas in the Hamiltonian circuit in the order they are chosen as specified by the algorithm.

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

Consider the graph given above. Use the sorted edges algorithm to find a Hamiltonian circuit.

a. List the weights of the edges separated by commas in the Hamiltonian circuit in the order they are chosen as specified by the algorithm.

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

Solution

Note:A circuit which starts at a vertex of a graph, which is the starting vertex,passes through every vertex exactly once, and returns to the starting vertex is called a HAMILTON CIRCUIT.

1)case 1

b)The sum of weight in a hamiltonian circuit is the sum of all the edges =

12+7+10+8+11+13+14+5+6+9=95

1)case 2

b)The sum of weight in a hamiltonian circuit is the sum of all the edges =

16+15+14+12+11+9+10+13+17+18=135