Question

The weights of edges in a graph are shown in the table above. Apply the sorted edges algorithm to the graph. Give your answer as a list of vertices, starting and ending at vertex A. Example: ABCDEFA 

Answer 1

The sorted edges algorithm is as given below:

1. Arrange the weights of edges in increasing order. Mark the required number of vertices in a piece of paper, that is 6 in the given problem, A,B,C,D,E,F

2.Connect the points that has the least weight using a line. Continue this process keeping two things in mind:

i) If a new line results in one of the vertex to have 3 edges, don't draw that line

ii) If a new line results in a circuit that does not contain all the vertices, don't draw that line.

3. Repeat this until we get a circuit that contains all vertices just once. Now we have reached the result, that is , we reached a Hamiltonian circuit.

The answer is as given below:

So, the answer is ABDCEFA.