Step 2

:- It denotes the step where the second starter vertex ( ie:- the right starter vertex ) of the starter edge is taken. For eg:- in step 2 for se[b,c], sv{c} is taken, ie:- vertex c is taken as the second starter vertex. Taking the right starter vertex as the second starter vertex for ‘step 2’ is for the purpose of convention.

End of Notations

Description of Starter edge method

1S)Find the edge with the least minimum weight from all the edges of the graph.

2S)Process the graph by taking the edge with the least weight and using the edge as a starter edge.

3S)Process the starter edge for obtaining a hamilton circuit by first taking the left starter vertex of the starter edge. Then from the left starter vertex, apply the nearest neighbour method . If a hamilton circuit ( with no skipped edges ) is obtained, then stop the process immediately as this hamilton circuit is the possibly best minimum hamilton circuit. But if during the process, there are skipped edges, then keep the skipped edges for processing in the next stage.

4S)After a hamilton circuit is obtained by using the first starter vertex, then process the starter edge by taking the right starter vertex. Then from the right starter vertex, apply the nearest neighbour method. If a hamilton circuit ( with no skipped edges ) is obtained, then stop the process immediately as this hamilton circuit is the possibly best minimum hamilton circuit. But if during the process, there are skipped edges, then keep the skipped edges for processing in the next stage.

5S)Collect all the skipped edges and then sort the skipped edges according to their weight in ascending order. Then select the edge with the least weight and then take the edge as a starter edge and process it for a hamilton circuit using Step ‘3S’ and Step ‘4S’ . Do the process for finding the hamilton circuit for all the other skipped edges using Step ‘3S’ and Step ‘4S’ . The process is stopped if a hamilton circuit with no skipped edges is obtained. Otherwise the process is continued until all the skipped edges of all the ‘stages’ have been processed.

6S)Collect all the hamilton circuits obtained during the processing of the starter edge in the beginning and the skipped edges of all the ‘stages’. Then select the hamilton circuit with the least weight among them. This hamilton circuit is the possibly best minimum weight hamilton circuit.

( Step numbers used for numbering the steps in the description are written as ‘1S’, ‘2S’ etc.. )

End of Description

The graph which is used to show how the starter edge method works is the same graph given inFigure 5.23of Chapter 5 in Section 5.8 contained in the book ‘Elements of Discrete Mathematics’ by C.L.Liu.The graph is given the nameGraph1.

Collection_1is a collection of the edges and the weights of all the edges ofGraph1. The edges ofCollection_1are arranged in ascending sorted order of their weights.

Collection_1is :-

w[b,e] = 5 ( ie:- Weight of edge [b,e] is ‘5’ )

w[c,d] = 6

w[a,d] = 7

w[c,e] = 8

w[b,c] = 9

w[a,e] = 10

w[d,e] = 11

w[a,c] = 12

w[b,d] = 13

w[a,b] = 14

Collection_ais a collection of the edges and the weights of all the edges ofGraph1which are connected to{a}( ie:- vertex ‘a’ ofGraph1) . The edges ofCollection_aare arranged in ascending sorted order of their weights.

Collection_ais :-

w[a,d] = 7 ( ie:- Weight of edge [a,d] is ‘7’)

w[a,e] = 10

w[a,c] = 12

w[a,b] =14

Collection_bis a collection of the edges and the weights of all the edges ofGraph1which are connected to{b}. The edges ofCollection_bare arranged in ascending sorted order of their weights.

Collection_bis :-

w[b,e] = 5

w[b,c] = 9

w[b,d] = 13

w[a,b] = 14

Collection_cis a collection of the edges and the weights of all the edges ofGraph1which are connected to{c}. The edges ofCollection_care arranged in ascending sorted order of their weights.

Collection_cis :-

w[c,d] = 6

w[c,e] = 8

w[b,c] = 9

w[a,c] = 12

Collection_dis a collection of the edges and the weights of all the edges ofGraph1which are connected to{d}. The edges ofCollection_dare arranged in ascending sorted order of their weights.

Collection_dis :-

w[c,d] = 6

w[a,d] = 7

w[d,e] = 11

w[b,d] = 13

Collection_eis a collection of the edges and the weights of all the edges ofGraph1which are connected to{e}. The edges ofCollection_eare arranged in ascending sorted order of their weights.

Collection_eis :-

w[b,e] = 5

w[c,e] = 8

w[a,e] = 10

w[d,e] = 11

Collection_a,Collection_b,Collection_c,Collection_dandCollection_eare the collections of the edges ofGraph1which are connected to{a},{b},{c},{d}and{e}respectively.

({a},{b},{c},{d}and{e}are vertices ofGraph1. )

According toCollection_1, edge [b,e] should be taken as the starter edge first, because of the least weight of the edge [b,e]. But in order to create an example of how the method works, an edge [c,e] is taken as the starter edge.

Usage of starter edge method for Graph1

Processing for Graph1 ( Solving Graph1 using se[c,e] ) ( First example )

Beginning of First example

Take edge se[c,e].

Step 1 :-

Take se[c,e] and sv{c}. ( Here ‘c’ is the left starter vertex of se[c,e] )

pc(se[c,e],sv{c}) = (c,e) = PC1(HC1) = 8

Continued in Travelling Salesman Problem - Part 3