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?

Solution

From the figure we get the weights of edges as :

DE = 17, EF= 16, FG = 19, GH = 27, HI = 25 , ID = 18

EG = 22, EH = 26, EI = 18

DF = 13, DG = 20 , DH = 24

FI = 14, FH = 23

GI = 21

A) By sorted edges algorithm method to hamiltonian circuit is :

The first algorithm we will consider is called the nearest-neighbor algorithm. it’s based on a common sense idea: at each vertex, choose the closest vertex that you haven’t visited yet

so first consider starting vertex E : the shoetest vertex is F , from F the shortest distance is vertex D. and so on the process continues as the until all the vetices are covered and no vertex is repeated.

EF = 16, FD = 13, DI = 15, IG = 21, GH = 27 ,

The algorithm goes as the weights given above.

B) Total weight along the Hamiltonian circuit is : 294