Solution of Travelling Salesman Problem with exact solutions for the case of complete graphs.

I have written a more simplified and modified version of the Starter Edge method , in order to make it more easier to understand and which is specially used to get exact solutions for Complete graphs.

I have tried the process on all the 'Complete graph' examples given in the theory sections of the two text books ( ie:- "Elements of Discrete Mathematics by C.L.Liu" and " A First Look at Graph Theory " by John Clark and Derek Allan Holton) and they give exact solutions. Also the method is polynomial time method, since the number of hamilton circuits produced is '2*n' only, no matter how large 'n' may become ( Where 'n' is the number of edges of the Complete graph ).


The method is as follows :-

[ Beginning of method ]
Definitions and Notations

Complete graph :-
A Complete graph is a graph in which each vertex of the graph is connected to every other vertex of the graph.

E(n) :-
This shows an 'nth' edge ( where 'n' is an integer ).

E(n)[p,q] :-
This shows an 'nth' edge ( where 'n' is an integer ) and the edge has a left vertex 'p' and a right vertex 'q'( 'p' and 'q' can be an alphabet or an integer. ). Also 'E(n)[p,q]' can be written as 'E(n)' ,if shortform is required.
( Note :- If 'p' and 'q' are interchanged, the edge remains the same. For eg:- E(1)[a,b] and E(1)[b,a] are both the same edges since it is an edge which connects the vertex a and vertex b. So in order to avoid confusion and duplication of the same edge, a convention can be used in which the lesser value of the two vertices is written on the left and the greater value is written to the right. So for eg:- E(1)[a,b] or E(1)[b,a] can be written as E(1)[a,b]. )

HC(m) :-
This shows the 'mth' hamilton circuit. ( where 'm' is an integer. )

Nearest neighbour method :-
The nearest neighbour method is the method which is given in the book 'Elements of Discrete Mathematics' by C.L.Liu.

w(E(n)) :-
This shows the weight of the 'nth' edge.

w(E(n)[p,q]) :-
This shows the weight of the 'nth' edge. The 'nth' edge connects the vertices 'p' and 'q'.

w(HC(n)) :-
This shows the weight of the 'nth' hamilton circuit.


End of Definitions and Notations




Description of Starter edge method

Step 1) :- Collect all the edges of the graph.

Step 2) :- Take an edge from the graph ( for eg:- E(1)[a,b] is taken. Here the edge 'E(1)' consists of the left vertex 'a' and the right vertex 'b').

Step 3) :- Construct a hamiton circuit ( for eg:- HC(1) ) using the edge E(1) and the nearest neighbour method. The edge E(1) must be the first edge to be included in the hamilton circuit 'HC(1)'. From the left vertex 'a' of the edge 'E(1)', construction of the hamilton circuit should begin using the nearest neighbour method. Then the construction of the hamilton circuit should end at the right vertex ( ie:- 'b' ) of the edge 'E(1)'. So the first hamilton circuit ie:- 'HC(1)' for 'E(1)' is obtained.

Step 4) :- Construct a second hamilton circuit ( for eg:- HC(2) ) using the edge E(1) and the nearest neighbour method. The edge E(1) must be the first edge to be included in the hamilton circuit 'HC(2)'. From the right vertex 'b' of the edge 'E(1)', construction of the hamilton circuit should begin using the nearest neighbour method. Then the construction of the hamilton circuit should end at the left vertex ( ie:- 'a' ) of the edge 'E(1)'. So the second hamilton circuit ie:- 'HC(2)' for 'E(1)' is obtained.

Step 5) :- Thus exactly two hamilton circuits are obtained for the edge 'E(1)'.

Step 6) :- Similarly, using the same process as above ( ie:- using " Step 3 " and " Step 4 " ), construct 2 hamilton circuits for each of the remaining edges left in the graph.

Step 7) :- So if there are 'n' edges in a complete graph, the above process produces '2*n' ( ie:- here '*' means multiplied by ) hamilton circuits.

Step 8) :- Compare all the weights of the hamilton circuits that are produced by the process.

Step 9) :- The hamilton circuit which contains the least weight among the hamilton circuits is the minimum weight hamilton circuit.


End of description



Example for explaining how the hamilton circuit is formed

The edges and their weights of a 4 vertex complete graph is given as follows.

w(E(1)[a,b]) = 2
w(E(2)[b,c]) = 3
w(E(3)[c,d]) = 6
w(E(4)[a,d]) = 1
w(E(5)[a,c]) = 4
w(E(6)[b,d]) = 5

In order to explain how the hamilton circuits are formed, the starter edge method is applied to example edges namely 'E(4)' and 'E(6)'.

1) Applying the starter edge method to an edge for eg:- E(4)[a,d].
Here 'a' is the left vertex and 'd' is the right vertex of E(4).
Here we take E(4) and this edge is the first edge to be included in the hamilton circuit.

The left vertex 'a' of E(4) is taken first.
The nearest neighbour method is applied starting from vertex 'a'.
The last vertex to be included in the hamilton circuit should be right vertex 'd' of E(4) ie:- the construction of the hamilton circuit should end at the right vertex of E(4).
The hamilton circuit formed ( for eg:- HC(1) ) consists of the edges E(4),E(1),E(2) and E(3).
The weight of the hamilton circuit is :-
w(HC(1)) = w(E(4)) + w(E(1)) + w(E(2)) + w(E(3)) = 1+2+3+6 = 12

Now the right vertex 'd' of E(4) is taken.
Here also E(4) must be the first edge to be included in the hamilton circuit.
The nearest neighbour method is applied starting from vertex 'd'.
The last vertex to be included in the hamilton circuit should be the left vertex 'a' of E(4) ie:- the construction of the hamilton circuit should end at the left vertex of E(4).
The hamilton circuit formed ( for eg:- HC(2) ) consists of the edges E(4),E(6),E(2) and E(5) .
The weight of the hamilton circuit is :-
w(HC(2)) = w(E(4)) + w(E(6)) + w(E(2)) + w(E(5)) = 1+5+3+4 = 13

Therefore the two hamilton circuits which are obtained for E(4) are HC(1) and HC(2) with weights of '12' and '13' respectively.

2) Applying the starter edge method to another edge for eg:- E(6)[b,d].
Here 'b' is the left vertex and 'd' is the right vertex of E(6).
Here we take E(6) and this edge is the first edge to be included in the hamilton circuit.

The left vertex 'b' of E(6) is taken first.
The nearest neigbour method is applied starting from vertex 'b'.
The last vertex to be included in the hamilton circuit should be the right vertex 'd' of E(6) ie:- the construction of the hamilton circuit should end at the right vertex of E(6).
The hamilton circuit formed ( for eg:- HC(3) ) consists of the edges E(6),E(1),E(5) and E(3).

The weight of the hamilton circuit is :-
w(HC(3)) = w(E(6)) + w(E(1)) + w(E(5)) + w(E(3)) = 5+2+4+6 = 17


Now the right vertex 'd' of E(6) is taken.
Here also E(6) must be the first edge to be included in the hamilton circuit.
The nearest neighbour method is applied starting from vertex 'd'.
The last vertex to be included in the hamilton circuit should be the left vertex 'b' of E(6) ie:- the construction of the hamilton circuit should end at the left vertex of E(6).
The hamilton circuit formed ( for eg:- HC(4) ) consists of the edges E(6),E(4),E(5) and E(2) .
The weight of the hamilton circuit is :-
w(HC(4)) = w(E(6)) + w(E(4)) + w(E(5)) + w(E(2)) = 5+1+4+3 = 13

Therefore the two hamilton circuits which are obtained for E(6) are HC(3) and HC(4) with weights of '17' and '13' respectively.

The above explanation is given for two example edges of the graph. The above process can similarly be applied to all the remaining edges of the graph. Then from all the weights of the hamilton circuits obtained, the minimum weight hamilton circuit is found out.


[ End of method ]

So is this method a correct solution since it is giving exact solutions?