8 Consider the graph given above Use the sorted edges algori

(8)

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?

Using sorted edges algorithm

From the starting edges choose the vertex with the small values

so write the path values in increasing order

MJ - 14 , MO- 15 , OJ -16 , MK - 17 , JK - 18 , OK - 19 , MN - 20 , NJ - 21

NO - 22 , NK - 23 , ML - 24 , MK - 25 , OL - 26 , KL - 27 , LN - 28

which we have arranged in an order

from here least value is 14 it exists draw a line

next MO - 15 for OJ there exist a closed path so leave it.

next MK which makes M to 3 paths so leave it. so as per rules there should not be closed path until the graph

joins all the edges and an edge doesn\'t have 3 paths until the completion of graph.

On making these attempts we get graph as shown in the image below

starting from j----18----K-----27------L------28------N------22-------O-----15-----M------14-------J

Thus this forms the graph

JK --- 18

KL----27

LN ----28

NO----22

OM-----15

MJ------14

b. Total weight along the hamiltonian circuit is 27+18+28+14+15+22 which is 124