Travelling Salesman Problem

[varghese]

I have found a new solution to the Travelling Salesman Problem. I have tried the solution on all the "complete" graphs of the examples in the 2 textbooks given in the reference section in the post given below.

I have also attached a document file ie:- " TSP_paper_one.docx " ( which contains figures and which is the same material and content as that of the post ), so that the solution becomes easier to understand.

The solution is as follows :-

Starter Edge method for an improved solution for the Travelling Salesman Problem


Abstract
This paper is mainly about a solution to the graph problem of Figure 5.23 given in the book ‘Elements of Discrete Mathematics’ by C.L.Liu.


General note
In the starter edge method, the edge with the least weight in a graph is selected as the beginning edge to be taken to be processed. Then from the starter edge, a starter vertex is selected. Then from the starter vertex, the ‘nearest neighbour method’ ( This method is the same method that is mentioned in the book ‘Elements of Discrete Mathematics’ by C.L.Liu in Section 5.8 of Chapter 5 ) is applied. A hamilton circuit is obtained. Collect all the edges with lesser weights which are skipped when the process for obtaining the hamilton circuit is carried out. If any lesser weight edges are not skipped when obtaining the hamilton circuit, then this hamilton circuit is the minimum weight hamilton circuit. Collect all these edges for processing in the next stage. After the hamilton circuit is obtained, then the second starter vertex from the starter edge is selected. Then from the second starter vertex, the nearest neighbour method is applied. Then during the process of obtaining the hamilton circuit, if any lesser weight edges are skipped, they are collected to be processed in the next stage. Then in the next stage, sort all the skipped edges according to their weights. Then from the least weight skipped edge, select the skipped edge as the starter edge and start the same type of process that was done at the beginning. Proceed to process all the skipped edges to obtain hamilton circuits ( If there is any hamilton circuit which did not have any skipped edges, then stop the process immediately because the possibly minimum hamilton circuit has been found.). So the process continues ( if there are more skipped edges to be processed ) in further stages until a hamilton circuit with no skipped edges is obtained or until all the skipped edges have been processed. When all the skipped edges have been processed, collect all the hamilton circuits together and find the hamilton circuit with the least weight among them. This hamilton circuit is the possibly best minimum hamilton circuit.


Notations

[n1,n2]
:- It denotes the edge joining the vertices n1 and n2 in a graph where n1 and n2 are alphabets or integers. Also n1 < n2 in order to avoid duplication of edges. ‘n1’ is called the left vertex of the edge [n1,n2] and ‘n2’ is called the right vertex of the edge [n1,n2]. For eg:- [b,c] and [c,b] represent the same edge, so the edge is only represented as [b,c] where b is alphabetically less than c. Also for eg:- in the edge [b,c], ‘b’ is called the left vertex and ‘c’ is called the right vertex.

w[n1,n2]
:- It denotes the weight of the edge connecting the vertices n1 and n2.

{n1}
:- It denotes the vertex n1 of a graph where n1 is an alphabet or an integer.

sv{n1}
:- It denotes the ‘starter vertex’ ie:- the vertex ‘n1’ from which the construction of the hamilton circuit begins. n1 is an alphabet or integer.

se[n1,n2]
:- It denotes the ‘starter edge’ ie:- an edge which joins the vertices ‘n1’ and ‘n2’. n1 and n2 are alphabets or integers. The starter edge is the starting edge from which the construction of the hamilton circuit begins and is the edge which must be included in the hamilton circuit that is being formed. For the sake of convention, the first starter vertex is always taken from the left vertex of the starter edge and the second starter vertex is always taken from the right vertex of the starter edge. For eg:- in ‘se[b,c]’, sv{b} is always taken first for processing the first hamilton circuit and sv{c} is always taken second for processing the second hamilton circuit ie:- the numerically or alphabetically lesser vertex is taken first for constructing the hamilton circuit, for the purpose of convention. Also in the notation ‘se[n1,n2]’, ‘n1’ is called the left starter vertex and ‘n2’ is called the right starter vertex.

PCm
:- It denotes the mth partial circuit where m is an integer.

w(PCm)
:- It denotes the total weight of the mth partial circuit where m is an integer.

pc(se[n1,n2],sv{n2}) = PCm
:- ‘pc(se[n1,n2],sv{n2})’ denotes the partial circuit which has starter edge of [n1,n2] and a starter vertex of ‘n2’. Also to make the notation into shortform, this notation can also be equated to PCm (ie:- the mth partial circuit ). Also to denote the vertices present in the partial circuit, the vertices can also be represented as for eg:- ‘pc(se[n1,n2],sv{n2}) = PCm = (n1,n2,n3)’ denotes the mth partial circuit containing the vertices n1,n2 and n3. Here {n1} is connected to {n2} to form an edge [n1,n2] and {n2} is connected to {n3} to form an edge [n2,n3]. Also the above notation can be written as ‘pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm’ which also has the same meaning.

HCm
:- It denotes the mth hamilton circuit where m is an integer.

w(HCm)
:- It denotes the weight of the mth hamilton circuit where m is an integer.

pc(se[n1,n2],sv{n2}) = PCm(HCz)
:- It denotes the mth partial circuit of the zth hamilton circuit. Here the zth hamilton circuit is not fully formed yet, but is going to be formed later when all the vertices of the graph has been added to the partial circuit in order to form the hamilton circuit. For eg:- ‘pc(se[n1,n2],sv{n2}) = PCm(HCz) = (n1,n2,n3)’ means the mth partial circuit of the zth hamilton circuit (the zth hamilton circuit is the hamilton circuit which is going to be formed later) and consists of the vertices n1,n2 and n3. Also the above notation can be written as ‘pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm(HCz)’ which also has the same meaning.

w(PCm(HCz))
:- It denotes the weight of the mth partial circuit ( where m is an integer ) of the zth hamilton cirucit. ( The hamilton circuit will be formed later when all the vertices of the graph has been included in the partial circuit.)

hc(se[n1,n2],sv{n2}) = HCm
:- ‘hc(se[n1,n2],sv{n2})’ denotes the hamilton circuit which has starter edge of [n1,n2] and a starter vertex of ‘n2’. Also to make the notation into shortform, this notation can also be equated to HCm (ie:- the mth hamilton circuit ). Also to denote the vertices present in the hamilton circuit, the vertices can also be represented as, for eg:- ‘hc(se[n1,n2],sv{n2}) = HCm = (n1,n2,n3,n4)’ which denotes the mth hamilton circuit containing the vertices n1,n2,n3 and n4. Here {n1} is connected to {n2} to form the edge [n1,n2] , {n2} is connected to {n3} to form the edge [n2,n3] , {n3} is connected to {n4} to form the edge [n3,n4] and {n4} is connected to {n1} to form the edge [n1,n4]. Also the above notation can be written as ‘hc(se[n1,n2],sv{n2}) = (n1,n2,n3,n4) = HCm’ which also has the same meaning.

w(HCm)
:- It denotes the total weight of the mth hamilton circuit .

Skipped edge
:- ‘Skipped edge’ means an edge which was considered for forming a part of the hamilton circuit because of its lesser weight, but is not taken because taking this edge will not form a hamilton circuit, since addition of this edge causes more than 2 edges to be attached to a single vertex, since in a hamilton circuit, only 2 edges are allowed to be attached to a single vertex.

Stage r
:- It denotes the processing stage where all the skipped edges are sorted according to their weights and are taken one by one (beginning with the least weight edge) with each edge considered as a starter edge. Also the process for obtaining the hamilton circuits from the skipped edges take place in a particular stage. ‘r’ is an integer.

Step 1
:- It denotes the step where the first starter vertex ( ie:- the left starter vertex ) of the starter edge is taken. For eg :- in step 1 for se[b,c], sv{b} is taken, ie:- vertex b is taken as the first starter vertex. Also taking the left starter vertex as the first starter vertex for ‘step 1’ is for the purpose of convention.

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 in Figure 5.23 of Chapter 5 in Section 5.8 contained in the book ‘Elements of Discrete Mathematics’ by C.L.Liu. The graph is given the name Graph1.


Collection_1 is a collection of the edges and the weights of all the edges of Graph1. The edges of Collection_1 are arranged in ascending sorted order of their weights.
Collection_1 is :-
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_a is a collection of the edges and the weights of all the edges of Graph1 which are connected to {a} ( ie:- vertex ‘a’ of Graph1 ) . The edges of Collection_a are arranged in ascending sorted order of their weights.
Collection_a is :-
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_b is a collection of the edges and the weights of all the edges of Graph1 which are connected to {b}. The edges of Collection_b are arranged in ascending sorted order of their weights.
Collection_b is :-
w[b,e] = 5
w[b,c] = 9
w[b,d] = 13
w[a,b] = 14

Collection_c is a collection of the edges and the weights of all the edges of Graph1 which are connected to {c}. The edges of Collection_c are arranged in ascending sorted order of their weights.
Collection_c is :-
w[c,d] = 6
w[c,e] = 8
w[b,c] = 9
w[a,c] = 12

Collection_d is a collection of the edges and the weights of all the edges of Graph1 which are connected to {d}. The edges of Collection_d are arranged in ascending sorted order of their weights.
Collection_d is :-
w[c,d] = 6
w[a,d] = 7
w[d,e] = 11
w[b,d] = 13

Collection_e is a collection of the edges and the weights of all the edges of Graph1 which are connected to {e}. The edges of Collection_e are arranged in ascending sorted order of their weights.
Collection_e is :-
w[b,e] = 5
w[c,e] = 8
w[a,e] = 10
w[d,e] = 11

Collection_a , Collection_b , Collection_c , Collection_d and Collection_e are the collections of the edges of Graph1 which are connected to {a} , {b} , {c} , {d} and {e} respectively.
( {a} , {b} , {c} , {d} and {e} are vertices of Graph1. )


According to Collection_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

( Applying ‘nearest neighbour method’ to vertex ‘c’ of the edge ‘[c,e]’ and trying to form a hamilton circuit which must include the edge ‘[c,e]’. )

w(PC1(HC1))=8

Adding vertex ‘d’ according to nearest neighbour method.
pc(se[c,e],sv{c}) = (d,c,e) = PC2(HC1) = 8+6 = 14
w(PC2(HC1))=14

Adding vertex ‘a’ according to nearest neighbour method.
pc(se[c,e],sv{c}) = (a,d,c,e) = PC3(HC1) = 8+6+7 = 21
w(PC3(HC1))=21

Adding vertex ‘b’ according to nearest neighbour method.
pc(se[c,e],sv{c}) = (b,a,d,c,e) = PC4(HC1) = 8+6+7+14 = 35
w(PC4(HC1))=35
PC4(HC1) was formed by skipping the edges [a,e] and [a,c] which has a lesser weight of ‘10’ and ‘12’ respectively than the edge [a,b] which has a weight of ‘14’.
( Here Collection_a is used to find out that the edges [a,e] and [a,c] have been skipped from vertex ‘a’ in order to reach vertex ‘b’ when using the nearest neighbour method. )

Joining ‘b’ to ‘e’ in order to form the hamilton circuit.
hc(se[c,e],sv{c}) = (b,a,d,c,e) = HC1 = 8+6+7+14+5 = 40
w(HC1)=40

Therefore the edges which were skipped during the process of forming HC1 were [a,e] and [a,c].


Step 2 :-
Take se[c,e] and sv{e}. ( Here ‘e’ is the right starter vertex of se[c,e]. )
pc(se[c,e],sv{e}) = (c,e) = PC1(HC2) = 8
w(PC1(HC2))=8

( Applying ‘nearest neighbour method’ to vertex ‘e’ of the edge ‘[c,e]’ and trying to form a hamilton circuit which must include the edge ‘[c,e]’. )

Adding vertex ‘b’ according to nearest neighbour method.
pc(se[c,e],sv{e}) = (c,e,b) = PC2(HC2) = 8+5=13
w(PC2(HC2)) = 13

Adding vertex ‘d’ according to nearest neighbour method.
pc(se[c,e],sv{e}) = (c,e,b,d) = PC3(HC2) = 8+5+13=26
PC3(HC2) was formed by skipping the edge [b,c] which has a lesser weight of ‘9’ than the edge [b,d] which has a weight of ‘13’.
( Here Collection_b shows that the edge [b,c] has been skipped from vertex ‘b’ in order to reach vertex ‘d’ when using the nearest neighbour method. )
w(PC3(HC2)) = 26

Adding vertex ‘a’ according to nearest neighbour method.
pc(se[c,e],sv{e}) = (c,e,b,d,a) = PC4(HC2) = 8+5+13+7=33
PC4(HC2) was formed by skipping the edge [c,d] which has a lesser weight of ‘6’ than the edge [a,d] which has a weight of ‘7’.
( Here Collection_d shows that the edge [c,d] has been skipped from vertex ‘d’ in order to reach vertex ‘a’ when using the nearest neighbour method. )
w(PC4(HC2))=33

Joining ‘a’ to ‘c’ in order to form the hamilton circuit.
hc(se[c,e],sv{e}) = (c,e,b,d,a) = HC2 = 8+5+13+7+12=45
HC2 was formed by skipping the edge [a,e] which has a lesser weight of ‘10’ than the edge [a,c] which has a weight of ‘12’.
( Here Collection_a shows that the edge [a,e] has been skipped from vertex ‘a’ in order to reach vertex ‘c’ when using the nearest neighbour method. )
w(HC2)=45

Therefore the edges which were skipped during the process of forming HC2 were [b,c] , [c,d] and [a,e].

Now the process for the edge [c,e] is finished as both the starter vertices ‘c’ and ‘e’ have been processed. Now next is ‘stage 1’ where all the edges which have been skipped has to be processed.


Stage 1 :-

The edges which were skipped were [a,e] , [a,c] , [b,c] and [c,d]. Now sorting the skipped edges according to the weights , we get the sorted order as [c,d] , [b,c] , [a,e] and [a,c].

Now taking se[c,d].

Step 1:-
Take se[c,d],sv{c}.
pc(se[c,d],sv{c}) = (c,d) = PC1(HC3)
pc(se[c,d],sv{c}) = (e,c,d) = PC2(HC3)
pc(se[c,d],sv{c}) = (b,e,c,d) = PC3(HC3)
pc(se[c,d],sv{c}) = (a,b,e,c,d) = PC4(HC3)
PC4(HC3) was formed by skipping the edges [b,c] and [b,d]
hc(se[c,d],sv{c}) = (a,b,e,c,d) = HC3
w(HC3)=6+8+5+14+7=40

Step 2:-
Take se[c,d],sv{d}.
pc(se[c,d],sv{d} = (c,d) = PC1(HC4)
pc(se[c,d],sv{d} = (c,d,a) = PC2(HC4)
pc(se[c,d],sv{d} = (c,d,a,e) = PC3(HC4)
pc(se[c,d],sv{d} = (c,d,a,e,b) = PC4(HC4)
hc(se[c,d],sv{d} = (c,d,a,e,b) = HC4
No edges were skipped while forming HC4. So here the process can be stopped immediately, because the possibly best minimum hamilton circuit is got here. But in order to describe how the process works, the process is continued.
w(HC4)=6+7+10+5+9=37

(In the next example (ie:- second example ), where the least weight edge ie:- [b,e] is taken as the starter edge in the beginning, the process is shown to be stopped when there are no skipped edges while processing for a hamilton circuit. )


Take se[b,c].

Step 1:-
Take se[b,c],sv{b}.
pc(se[b,c],sv{b}) = (b,c) = PC1(HC5)
pc(se[b,c],sv{b}) = (e,b,c) = PC2(HC5)
pc(se[b,c],sv{b}) = (a,e,b,c) = PC3(HC5)
PC3(HC5) was formed by skipping the edge [c,e]
pc(se[b,c],sv{b}) = (d,a,e,b,c) = PC4(HC5)
hc(se[b,c],sv{b}) = (d,a,e,b,c) = HC5
w(HC5) = 9+5+10+7+6=37

Step 2:-
Take se[b,c],sv{c}.
pc(se[b,c],sv{c}) = (b,c) = PC1(HC6)
pc(se[b,c],sv{c}) = (b,c,d) = PC2(HC6)
pc(se[b,c],sv{c}) = (b,c,d,a) = PC3(HC6)
pc(se[b,c],sv{c}) = (b,c,d,a,e) = PC4(HC6)
hc(se[b,c],sv{c}) = (b,c,d,a,e) = HC6
w(HC6)=9+6+7+10+5=37
No edges were skipped while HC6 was formed.

Take se[a,e].

Step 1:-
Take se[a,e],sv{a}.
pc(se[a,e],sv{a}) = (a,e) = PC1(HC7)
pc(se[a,e],sv{a}) = (d,a,e) = PC2(HC7)
pc(se[a,e],sv{a}) = (c,d,a,e) = PC3(HC7)
pc(se[a,e],sv{a}) = (b,c,d,a,e) = PC4(HC7)
PC4(HC7) was formed by skipping the edge [c,e]
hc(se[a,e],sv{a}) = (b,c,d,a,e) = HC7
w(HC7) = 10+7+6+9+5 = 37

Step 2:-
Take se[a,e],sv{e}.
pc(se[a,e],sv{e}) = (a,e) = PC1(HC8)
pc(se[a,e],sv{e}) = (b,c,d) = PC2(HC8)
pc(se[a,e],sv{e}) = (b,c,d,a) = PC3(HC8)
pc(se[a,e],sv{e}) = (b,c,d,a,e) = PC4(HC8)
hc(se[a,e],sv{e}) = (b,c,d,a,e) = HC8
w(HC8)=10+5+9+6+7=37
No edges were skipped while forming HC8.


Take se[a,c].

Step 1:-
Take se[a,c],sv{a}.
pc(se[a,c],sv{a}) = (a,c) = PC1(HC9)
pc(se[a,c],sv{a}) = (d,a,c) = PC2(HC9)
pc(se[a,c],sv{a}) = (e,d,a,c) = PC3(HC9)
PC3(HC9) was formed by skipping the edge [c,d]
pc(se[a,c],sv{a}) = (b,e,d,a,c) = PC4(HC9)
hc(se[a,c],sv{a}) = (b,e,d,a,c) = HC9
w(HC9) = 12+7+11+5+9 = 44

Step 2:-
Take se[a,c],sv{c}.
pc(se[a,c],sv{c}) = (a,c) = PC1(HC10)
pc(se[a,c],sv{c}) = (a,c,d) = PC2(HC10)
pc(se[a,c],sv{c}) = (a,c,d,e) = PC3(HC10)
PC3(HC10) was formed by skipping the edge [a,d]
pc(se[a,c],sv{c}) = (a,c,d,e,b) = PC4(HC10)
hc(se[a,c],sv{c}) = (a,c,d,e,b) = HC10
HC10 was formed by skipping the edges [b,c] and [b,d]
w(HC10)=10+6+11+5+14=46


Stage 2 :-

The edges which were skipped in ‘Stage 1’ were [b,c] , [b,d] , [c,e] , [c,d] and [a,d] . Now sorting the skipped edges according to the weights , we get the sorted order as [c,d] , [a,d] , [c,e] , [b,c] and [b,d]. Edge [c,e] was processed in the beginning as the first starter edge. [c,d] and [b,c] was processed in ‘Stage 1’. So now the edges left for processing in ‘Stage 2’ are [a,d] and [b,d].


Take se[a,d].

Step 1:-
Take se[a,d],sv{a}.
pc(se[a,d],sv{a}) = (a,d) = PC1(HC11)
pc(se[a,d],sv{a}) = (e,a,d) = PC2(HC11)
pc(se[a,d],sv{a}) = (b,e,a,d) = PC3(HC11)
pc(se[a,d],sv{a}) = (c,b,e,a,d) = PC4(HC11)
hc(se[a,d],sv{a}) = (c,b,e,a,d) = HC11
w(HC11) = 7+10+5+9+6=37
No edges were skipped while forming HC11.


Step 2:-
Take se[a,d],sv{d}.
pc(se[a,d],sv{d}) = (a,d) = PC1(HC12)
pc(se[a,d],sv{d}) = (a,d,c) = PC2(HC12)
pc(se[a,d],sv{d}) = (a,d,c,e) = PC3(HC12)
pc(se[a,d],sv{d}) = (a,d,c,e,b) = PC4(HC12)
hc(se[a,d],sv{d}) = (a,d,c,e,b) = HC12
HC12 was formed by skipping the edges [b,c] and [b,d]
w(HC12)=7+6+8+5+14=40


Take se[b,d].

Step 1:-
Take se[b,d],sv{b}.
pc(se[b,d],sv{b}) = (b,d) = PC1(HC14)
pc(se[b,d],sv{b}) = (e,b,d) = PC2(HC14)
pc(se[b,d],sv{b}) = (c,e,b,d) = PC3(HC14)
pc(se[b,d],sv{b}) = (a,c,e,b,d) = PC4(HC14)
PC4(HC14) was formed by skipping the edges [c,d] and [b,c]
hc(se[b,d],sv{b}) = (a,c,e,b,d) = HC14
w(HC14) = 13+5+8+12+7=45


Step 2:-
Take se[b,d],sv{d}.
pc(se[b,d],sv{d}) = (b,d) = PC1(HC15)
pc(se[b,d],sv{d}) = (b,d,c) = PC2(HC15)
pc(se[b,d],sv{d}) = (b,d,c,e) = PC3(HC15)
pc(se[b,d],sv{d}) = (b,d,c,e,a) = PC4(HC15)
PC4(HC15) was formed by skipping the edge [b,e]
hc(se[b,d],sv{d}) = (b,d,c,e,a) = HC15
HC15 was formed by skipping the edge [a,d] and [a,c]
w(HC15)=13+6+8+10+14=51


Stage 3 :-

The edges which were skipped in ‘Stage 2’ were [b,c] , [b,d] , [c,d] , [b,e] , [a,d] and [a,c] . Now sorting the skipped edges according to the weights , we get the sorted order as [b,e], [c,d] , [a,d] , [b,c] , [a,c] and [b,d]. Edges [c,d] , [b,c] and [a,c] was processed in ‘Stage 1’. Edges [a,d] and [b,d] was processed in ‘Stage 2’ . So now the edge left for processing in ‘Stage 3’ is [b,e].


Take se[b,e].

Step 1:-
Take se[b,e],sv{b}.
pc(se[b,e],sv{b}) = (c,b,e) = PC1(HC16)
pc(se[b,e],sv{b}) = (c,b,e) = PC2(HC16)
pc(se[b,e],sv{b}) = (d,c,b,e) = PC3(HC16)
pc(se[b,e],sv{b}) = (a,d,c,b,e) = PC4(HC16)
hc(se[b,e],sv{b}) = (b,e) = HC16
w(HC16) = 5+9+6+7+10=37
No edges were skipped while forming HC16.


Step 2:-
Take se[b,e],sv{e}.
pc(se[b,e],sv{e}) = (b,e) = PC1(HC17)
pc(se[b,e],sv{e}) = (b,e,c) = PC2(HC17)
pc(se[b,e],sv{e}) = (b,e,c,d) = PC3(HC17)
pc(se[b,e],sv{e}) = (b,e,c,d,a) = PC4(HC17)
hc(se[b,e],sv{e}) = (b,e,c,d,a) = HC17
HC17 was formed by skipping the edges [a,e] and [a,c]
w(HC17)=5+8+6+7+14=40


Stage 4 :-

The edges which were skipped in ‘Stage 3’ were [a,e] and [a,c]. Now sorting the skipped edges according to the weights , we get the sorted order as [a,e] and [a,c]. Edges [a,e] and [a,c] was already processed in ‘Stage 1’. So now there are no more edges to be processed in ‘Stage 4’. So the process ends in Stage 4. Now all the weights of the hamiton circuits that are obtained in the beginning ( ie:- when the starter edge ie:- the edge [c,e] was processed ) and in all of the ‘stages’ are taken together and the least weight hamilton circuit from them is taken. This least weight hamilton circuit is the possibly best minimum weight hamilton circuit.

Taking all the hamilton circuits together, we get

HC1 = 40 ( ‘40’ is the weight of the hamilton circuit HC1 )
HC2 = 45
HC3 = 40
HC4 = 37 ( No edges were skipped for HC4 )
HC5 = 37
HC6 = 37 (No edges were skipped for HC6 )
HC7 = 37
HC8 = 37 ( No edges were skipped for HC8 )
HC9 = 44
HC10 = 46
HC11 = 37 ( No edges were skipped for HC11 )
HC12 = 40
HC14 = 45
HC15 = 51
HC16 = 37 ( No edges were skipped for HC16 )
HC17 = 40

HC4 , HC6 , HC8 , HC11 and HC16 are not taken for comparing the weights, because when these hamilton circuits are formed, the process should immediately stop, as these circuits are minimum circuits. But as mentioned earlier, the process is continued even if these circuits are obtained in order to describe how the process works if hamilton circuits ( in which no edges are skipped ) are not formed in the process. So the hamilton circuits HC1 , HC2 , HC3 , HC5 , HC7, HC9 , HC10 , HC12 , HC14 , HC15 and HC17 are taken and their weights are compared in order to get the minimum weight.

The minimum weight circuits are the circuits with weight of ‘37’ and they are ‘HC5’ and ‘HC7’.

End of First Example


Processing for Graph1 ( Solving Graph1 using se[b,e] ) ( Second example )

This is the process in which the minimum weight starter edge from Collection_1 of Graph1 is taken.

Beginning of Second Example

Take se[b,e]

Step 1:-
Take se[b,e],sv{b}
pc(se[b,e],sv{b}) = (b,e) = PC1(HC18)
pc(se[b,e],sv{b}) = (c,b,e) = PC2(HC18)
pc(se[b,e],sv{b}) = (d,c,b,e) = PC3(HC18)
pc(se[b,e],sv{b}) = (a,d,c,b,e) = PC4(HC18)
hc(se[b,e],sv{b}) = (a,d,c,b,e) = HC18
No edges were skipped while forming HC18.
w(HC18)=5+9+6+7+10=37.
Since no lesser weight edges were skipped while forming HC18, the process is immediately stopped.

So in processing Graph1 with se[b,e] and sv{b}, the possibily minumum circuit ‘HC18’ is obtained.

End of Second Example


Conclusion :- The ‘starter edge’ method gives the possibly best hamilton circuit or an improved minimum weight hamilton circuit.


Reference:-
1) " Elements of Discrete Mathematics " by C.L.Liu ( Second Edition )( ISBN of the book is 0-07-100544-7 ).
2) " A First Look at Graph Theory " by John Clark and Derek Allan Holton( ISBN of the book is 81-7023-463-8 ).






Written by :- Samuel Gheverghese

(EDITED BY FOREST_DUMPT TO REMOVE CONFIDENTIAL INFORMATION)

[Natural ChemE]

varghese,

Welcome to the forums!

I would note that threads shouldn't be posted in more than one forum. For this reason, your duplicate post in the Math section has been removed.

As for your post, I'm sure that you know that the travelling salesman problem really isn’t a very difficult problem to solve. The main interest in it is coming up with reliably swift algorithms to solve it quickly. It's currently classified as NP-hard, which has a lot of implications in the Computer Science world.

This said, what would be the advantage to your new approach?

[varghese]

To,
Natural ChemE.

The main advantage of this approach is that the exact solution can be obtained for "complete" graphs in polynomial time. ( Please note that the word "complete" which is mentioned here is the same mathematical term used in graph theory ). I tried out the "complete" graph examples in the textbook using pen and paper and they are giving the exact solutions. Now the only thing is that solution needs to be tested on further complete graph examples using computers and software by scientists. Also the solution is polynomial time, because the solution is a new type of modified and improved version of the nearest neighbour method. And everyone knows that the nearest neighbour method is an approximate method which is polynomial time method. But this new modified method, gives exact solution to "complete" graphs and it is polynomial time also.

Thank You,
Varghese.

[Natural ChemE]

Varghese,

If you managed to do an NP-hard problem in polynomial time, it'd be a truly outstanding finding. Of course folks will apply a lot of skepticism to your claims before accepting them.

The problem for you will be that most of us just don't have time to read what you've written. See, from where I'm sitting, it's more likely that you've made a mistake somewhere along the way. People post crazy things all of the time, and I just don't have time to fix them all. Most folks will feel this way.

To get people interested, you'll want to provide some strong but concise evidence that you're correct. Something that we can look at quickly and say, “Oh, wow, this guy really might be on to something here.”

Since you're posting in the area of Computer Science, you'd probably want to make a computer program demonstrating your algorithm. You could do it Monte Carlo style! Just have the program randomly generate a lot of maps, solve the travelling salesman problem for each, then report the instruction count that it took to solve them along with the number of cities for each map. Make a scatter plot of these, with city count on the -axis and instruction count (or its log) on the -axis. Show us the plot, provide the source code, etc.

I would note that, if you have solved this problem in polynomial time, it'd be a huge discovery. You may want to consider your options instead of just releasing it to the public domain.

[varghese]

Natural ChemE,

In graph theory, a complete graph of n vertices has [ n(n-1)/2 ] edges. So when implementing the algorithm, in the worst case, all the edges may have to be taken for processing. Also for each edge, the left vertex and the right vertex has to be taken for processing. So the number of times the edges have to be taken for processing = number of edges * 2 = [ n(n-1)/2] * 2 = n(n-1) = n^2 - n . So the processing time for the algorithm in the worst case = O(n^2) ie:- it takes polynomial time. ( Here "^" means raised to ).

In the example that I have given for describing how the algorithm works, I have taken a random edge in order to show how the algorithm works. Where the algorithm is taken with the minimum weight edge , the process is shown between the headings "Beginning of second example" and"End of second example" and this description is short and easy for viewing.

My interest in mathematics is more than my interest in computers only because I am not an expert programmer and I am very slow in developing programs. Also my priority in interest is towards mathematics.

Also a peculiar behaviour of scientists is that they make a discovery, they want the to tell the world about it. So I also wanted to become a scientist, and so I am giving the discovery to the public domain.

[Natural ChemE]

Varghese,

If you want to be successful in what clearly seems to be your interest, you’re probably going to have to work on the whole programming thing. Programming’s pretty much a basic skill for researchers these days, and your research here is particularly dependent on it - this entire post is about an algorithm. I just don’t see things going well for you if you don’t learn.

Anyway, so you’re claiming . Do you claim that your method finds the exact solution, or merely one not far from it? Wikipedia cites the current best as (multiplied by a polynomial factor) for an exact method.

Do you know a programming language or have an interest in any? We can try to walk through this. Personally I’d prefer C#, or failing that, Java. C# and Java are just easy languages for quick problems like this one.

[varghese]

Natural ChemE,

I am claiming that I have tried the algorithm on all the examples given in the theory sections of the 2 textbooks and they give exact solutions. But I dont have mathematical proof. For graphs that are not complete, I cannot claim that it will give the exact solution, but I can only say that they might give the best solution. That is how far have I have tested. For other scientists, to get further convinced, it is better, if they try out this algorithm on more complete graphs at least using pen and paper for the time being instead of using computers. I am not forcing anyone to try it out. A lot of Mathematicians are saying that there might never be a solution to this problem, so I thought it was a little exciting if this algorithm would provide any clue which could further advance the research of the scientists. For proof of such problems, advanced degrees in maths is required like B.Sc, M.Sc, PhD etc. I don't even have a B.Sc degree, but only a B.Tech Degree. But the mathematics that I have learnt in B.Tech is not formal enough for finding a proof of such theorems. I can say that what I have given in the post is a " conjecture ". This word is more suitable.

I will try to put the explanation of the algorithm in very simple terms as far as possible. All Discrete Mathematicians know about the nearest neighbour method. In the nearest neighbour method, a random edge is taken and the nearest neighbour method is applied starting from that edge. This is the method that is known that is known to everyone. So when the nearest neighbour method is done, the process is O(1). Now in my method ( if for example the worst case is taken ie:- every edge of the complete graph is taken ( Also suppose the complete graph consists of "n" edges. ) ) , then the nearest neighbour method is applied to each edge ( taking the most minimum weight edge first and proceeding in ascending order of the weights of the edges ) , then the number of hamilton circuits obtained will be "n" hamilton circuits. So now the order will be O(n) because of "n" edges. Now the most important part of the algorithm is that for each edge, the nearest neighbour method should be applied by starting from the left vertex of the edge and then the next hamilton circuit should be obtained by starting from the right vertex of the edge by using the nearest neighbour method. So each edge should contain two hamilton circuits (which is obtained by using the nearest neighbour method ). So now the total number of hamilton circuits obtained for "n" edges will be " 2*n " hamilton circuits. So now the the order is O(2n) ie:- O(n). ( Please note that here the number of edges is taken as "n" and not the number of vertices , for easy understanding.) The most important point is that for each edge, 2 hamilton circuits are required which are produced by starting from the left vertex and the other by starting from the right vertex of the edge.

So the software is already there ie:- nearest neighbour method programs. The only modification that is needed for the software is that the nearest neighbour method should be applied to each edge, and for each edge, the nearest neighbour method should be applied to the left vertex and the right vertex of each edge. So for a complete graph of "n" vertices, in the worst case, there "2n" hamilton circuits. Then the minimum weight hamilton circuit among all these hamilton circuits is taken as the shortest weight hamilton circuit.

[kidjan]

Here's a data set you can use to test with. And obviously it goes without saying that no, you have not found an O(n^2) algorithm if you don't have a mathematical proof. I doubt you would pass serious tests with this algorithm either.

FWIW, I think your algorithm is flawed. The assumption that the shorted segment in a graph would definitely be contained in the optimal hamilton cycle for any given graph--directed or otherwise--is not true.

So when the nearest neighbour method is done, the process is O(1)

Nearest neighbor is not O(1).

[varghese]

kidjan,

About testing the algorithm on other graphs, I was meaning to say that the algorithm should be tested on 5,6,7,8,9 or 10 vertices "Complete" graphs, by giving different weights to the edges and then trying it out. Maximum should be 10 vertices graph because a computer can quickly find out the 100% optimal solution ( Note "complete" here means the same mathematical term used in graph theory) and then compare the result with what the algorithm gives. For graphs that are not "complete" , I can only say that the algorithm might give the best solution.

[Natural ChemE]

varghese,

I’m not sure that I understand the concern with complete graphs. In this context, “complete” just means that you can go from any one point to any other directly, right?

[varghese]

Natural ChemE,

A complete graph means a graph in which there is an edge from each vertex to every other vertex in the graph.

Just for reference purpose, I am giving a link to topic about complete graph in Wikipeida ie:- http://en.wikipedia.org/wiki/Complete_graph

The "starter edge method" given in the post can be written in short form as "SEM". In order to create a software for "SEM" may take a long time. So in order to quickly get results for testing, I am giving a modified version of the starter edge method which I will call as "modified starter edge method" or in short as "MSEM".

The "Nearest Neighbour Method" is written in short form as "NNM". The minimum hamilton circuit can be found from "MSEM" and it will give the same minimum hamilton circuit as the "SEM". Why I am giving the "MSEM" is because the "SEM" may take time to understand because of the many notations, although the algorithm is very simple.

Since the time complexity of the travelling salesman problem is more important and since the time complexity of "MSEM" is O(n^2), "MSEM" can be used for testing and getting the results quickly.

In the "NNM", a random vertex is taken to get the approximate minimum weight hamilton circuit.

The "NNM" is mainly used in the "MSEM".

In "MSEM", eventhough the "NNM" is used, the edges of the graph are considered very important.

So the "MSEM" is as follows.

Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex.

Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained.

Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4".

And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph.

So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed.

Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM".

Now using computers and a using a brute force algorithm, find all the possible hamilton circuits in the graph and find the 100% optimal weight hamilton circuit.

Now compare the weight of this hamilton circuit with the minimum weight hamilton circuit obtained by using the "MSEM".

As far as possible, the complete graph example should be limited to less than 10 or 20 vertices, in order for the computers to quickly find the 100% optimal hamilton circuit and then use the hamilton circuit to compare with the weight of the hamilton circuit obtained by using the "MSEM".

[Natural ChemE]

varghese,

First I’d note that, in most of your posts so far, you’ve mentioned that the graph must be complete. This confuses me because the Traveling Salesman Problem always uses a complete graph, so saying it again seems redundant. Am I missing a point that you’re trying to make about completeness?

Second I’d note that the concern for the order of an algorithm is largely related to how it’d perform for extremely high values of problem size . Polynomial time is so important in theory because, as becomes arbitrarily large , an algorithm that grows in polynomial time (even ) should outrun algorithm that grows in, say, . This is, even if an algorithm did work in polynomial time for a small problem size, it wouldn’t really matter unless you could extend it to larger problem sizes without exiting polynomial time.

Third, I’d note that you really need to program this thing up. Without explicitly providing instructions in a manner like programming, it can be very difficult to understand the actual order of your method. If you don’t know how to program it, you’re probably not able to assess its actual order. Of course, once you do program it up, not only would you be able to assess its order but you’d be able to directly test it many times over.

[varghese]

Natural ChemE,

The "starter edge method" algorithm can be used for any number of vertices "n" and the algorithm still works in polynomial time. An accurate number is that for a graph with n number of edges, there will be 2n hamilton circuits for weight calculation and comparison. So only 2n hamilton circuits needs to be processed no matter how large n may be.

The brute force algorithm I mentioned in the previous post is the different kind of algorithms and software that other scientists might use to get the 100% convincing optimal weight hamilton cirucit or the exact solution, which they can use to compare with the weight of the hamilton circuit that is obtained using my method.

[varghese]

Natural ChemE,

In order to avoid confusion about the "MSEM" in the previous post, I will write this algorithm with beginning and an ending tag. Notations used here are the same as that used in the previous post.


[ Beginning of "MSEM" ]

Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex.

Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained.

Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4".

And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph.

So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed.

Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM".

[ End of "MSEM" ]

[varghese]

Natural ChemE,

I mentioned about the time complexity of the "MSEM" in the previous post. What I meant to say was that the both "SEM" and "MSEM" are polynomial time methods. So which algorithm (ie:- "SEM" or "MSEM") is more efficient is not important, because the aim of all scientists at the present moment is to find a polynomial time solution for the Travelling Salesman Problem. So for the time being it does not matter whether "SEM" or "MSEM" is used to find the minimum weight hamilton circuit. ( As mentioned in the previous post "SEM" denotes "starter edge method" and "MSEM" denotes "modified starter edge method" )

[varghese]

Hello to All,

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 ]

[kidjan]

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.

The number of different Hamiltonian cycles in a complete undirected graph on n vertices is (n - 1)! / 2 and in a complete directed graph on n vertices is (n - 1)! (i.e. not polynomial), and that's not even accounting for the algorithmic complexity to find and construct any given Hamiltonian cycle. Your algorithm basically produces a subset of these Hamiltonian cycles (by your own admission, 2*n Hamiltonian paths), of which you assume the shortest path is contained within.

Not even determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected) is polynomial time; both are NP-complete, which requires superpolynomial time to solve.

In short, I believe you're incorrect on two counts. First, it is incorrect that the lowest-weight Hamiltonian path would be contained in a such a subset (where is your mathematical proof?). Second, you are incorrect in assuming the algorithmic complexity of the various steps outlined; the work you're discussing is not polynomial time based on any algorithm known to me or currently published.

[varghese]

Hello to All,


The following notes are about a php program which uses the nearest neightbour method to find 2 hamilton circuits for each edge of a complete

graph. The lowest total weight circuit among all these hamilton circuits will give the minimum weight hamilton circuit.


The important files are TSPexample_5_vertex.php , TSPexample_5_vertex_weight.php , cleanProcessTables.php , cleanCircuitTables.php and

cleanWeightTables.php.
cleanProcessTables.php cleans the processing tables after each single processing.
cleanCircuitTables.php cleans the table which contains the full results which are all put together.
cleanWeightTables.php cleans the table which contains the full results along with the weight of the individual edges of the graph.
check_table in database is used to temporarily keep all the edges along with the weights of a graph.
Data for check_table can be copied from vertex_5_example_1 or vertex_5_example_2.
table_1 contains the starting edge of a 5 vertex graph.
This edge is used at the beginnning of the processing.
table_2 , table_3 and table_4 are used for processing and the final result is obtained in table_5.
Also the tables are found in the "tsp_5_vertex_graph" database in mysql database.
cleanProcessTables.php cleans table_2 , table_3 , table_4 and table_5, so that new processing can be done.
table_1 is not cleaned since it is used to keep the starting edge of a 5 vertex graph.
cleanCircuitTables.php is used to empty the full results which are obtained in table_5_full. This should be used only if necessary, because it

will clean out a lot of results which are necessary.
Also you can copy the data present in vertex_5_example_1 and put it in check_table using the copying method present in phpmyadmin console.

This way you can easily switch to whichever graph you want to process( in this case the graph is vertex_5_example_1).
Also suppose check_table contains the edges of graph having 5 vertices, then first empty the check_table and then copy the edges of another

graph having 5 vertices into check_table using phpymadmin.
Also suppose you want to test another graph having 5 vertices but the edges are different weights, then make a copy of vertex_5_example_1

using phpmyadmin and rename the table to another name, and then change the values of the edge names and the weights in the new table and

then copy these rows into check_table using phpmyadmin.
Before copying into check_table, you have to empty check_table otherwise the old values of the edges and their weights of other graphs will be

in the check_table.
Also to check the value of the algorithm for each edge of the graph, just put the edge to be processed in table_1.
The weight of the edge need not be given in table_1, because the weights of all the edges are already there in check_table.
Also the edges in check_table are stored in a manner in which each edge is stored along with it's rotated edge.
For eg: edge 'a-b' is also stored as 'b-a' in check_table.
Also in table_1, for eg: if an edge 'b-c' is stored as the edge to be processed, then the meaning is that the left vertex is 'b' and the right vertex

is 'c' and the algorithm starts processing from the right vertex 'c'.
If the edge to be processed is 'c-b', then the meaning is that the left vertex is 'c' and the right vertex is 'b', and the algorithm starts processing

from the right vertex 'b'.
Also after each operation, cleanProcessTables.php is required to be called in order to clean the basic tables.
The version of the computer programs are as follows: "mysql" version 5.5.24, "php" version 5.4.3 ,"apache" version 2.2.22, "phpmyadmin"

version 3.5.1.

Notes about the program
The files for the program are
1) TSPexample_5_vertex.php.
2) TSPexample_5_vertex_weight.php.
3) cleanProcessTables.php.
4) cleanCircuitTables.php.
5) cleanWeightTables.php.




An example of the steps for doing the algorithm.
BEGIN
1) First there should be only one row in table_1 containing an edge ( for example : the edge 'a-b' ).
2) Then execute cleanProcessTables.php.
3) Then execute cleanCircuitTables.php.
4) Then execute cleanWeightTables.php.
5) Then execute TSPexample_5_vertex.php.
6) Then execute cleanProcessTables.php.
7) Then delete the row containing the edge 'a-b' in table_1.
8) Insert a row containing the edge 'b-a' in table_1.
9) Then execute TSPexample_5_vertex.php.
10) Then execute cleanProcessTables.php.
11) Then delete the row containing the edge 'b-a' in table_1.
12) Insert a row containing the edge 'b-c' in table_1.
14) Then execute TSPexample_5_vertex.php.
15) Then to find the weights of the circuits, execute TSPexample_5_vertex_weight.php.
16) The weights will be present in table_5_full_weight table.
END.

Structure of the following tables are given as below.

1) check_table

Field names Type
ck_vx_1 varchar(10)
ck_vx_2 varchar(10)
weight int(11)


2) table_1

Field names Type
tb_1_vx_1 varchar(10)
tb_1_vx_2 varchar(10)

3) table_2

Field names Type
tb_2_vx_1 varchar(10)
tb_2_vx_2 varchar(10)
tb_2_vx_3 varchar(10)
tb_2_vx_4 varchar(10)

4) table_3

Field names Type
tb_3_vx_1 varchar(10)
tb_3_vx_2 varchar(10)
tb_3_vx_3 varchar(10)
tb_3_vx_4 varchar(10)
tb_3_vx_5 varchar(10)
tb_3_vx_6 varchar(10)


5) table_4

Field names Type
tb_4_vx_1 varchar(10)
tb_4_vx_2 varchar(10)
tb_4_vx_3 varchar(10)
tb_4_vx_4 varchar(10)
tb_4_vx_5 varchar(10)
tb_4_vx_6 varchar(10)
tb_4_vx_7 varchar(10)
tb_4_vx_8 varchar(10)


6) table_5

Field names Type
tb_5_vx_1 varchar(10)
tb_5_vx_2 varchar(10)
tb_5_vx_3 varchar(10)
tb_5_vx_4 varchar(10)
tb_5_vx_5 varchar(10)
tb_5_vx_6 varchar(10)
tb_5_vx_7 varchar(10)
tb_5_vx_8 varchar(10)
tb_5_vx_9 varchar(10)
tb_5_vx_10 varchar(10)

7) table_5_full

Field names Type
tb_5_vx_1 varchar(10)
tb_5_vx_2 varchar(10)
tb_5_vx_3 varchar(10)
tb_5_vx_4 varchar(10)
tb_5_vx_5 varchar(10)
tb_5_vx_6 varchar(10)
tb_5_vx_7 varchar(10)
tb_5_vx_8 varchar(10)
tb_5_vx_9 varchar(10)
tb_5_vx_10 varchar(10)

8) table_5_full_weight

Field names Type
tb_5_vx_1 varchar(10)
tb_5_vx_2 varchar(10)
tb_5_vx_3 varchar(10)
tb_5_vx_4 varchar(10)
tb_5_vx_5 varchar(10)
tb_5_vx_6 varchar(10)
tb_5_vx_7 varchar(10)
tb_5_vx_8 varchar(10)
tb_5_vx_9 varchar(10)
tb_5_vx_10 varchar(10)
w1 int(11)
w2 int(11)
w3 int(11)
w4 int(11)
w5 int(11)


9) vertex_5_example_1

Field names Type
ck_vx_1 varchar(10)
ck_vx_2 varchar(10)
weight int(11)

10) vertex_5_example_2

Field names Type
ck_vx_1 varchar(10)
ck_vx_2 varchar(10)
weight int(11)


As an example, the data present in "check_table" is given.

ck_vx_1 ck_vx_2 weight <- ( column names )
a b 14
b a 14
a c 12
c a 12
a d 7
d a 7
a e 10
e a 10
b c 9
c b 9
b d 13
d b 13
b e 5
e b 5
c d 6
d c 6
c e 8
e c 8
d e 11
e d 11


The data present in vertex_5_example_1 is

ck_vx_1 ck_vx_2 weight <- ( column names )
a b 1
b a 1
a c 10
c a 10
a e 6
e a 6
a d 5
d a 5
b e 2
e b 2
b d 8
d b 8
b c 9
c b 9
c e 3
e c 3
c d 4
d c 4
d e 7
e d 7


The data present in vertex_5_example_2 is

ck_vx_1 ck_vx_2 weight <- ( column names )
a b 14
b a 14
a c 12
c a 12
a d 7
d a 7
a e 10
e a 10
b c 9
c b 9
b d 13
d b 13
b e 5
e b 5
c d 6
d c 6
c e 8
e c 8
d e 11
e d 11

For the above example ,
table_1 is

Column names Values in Row 1
tb_5_vx_1 a
tb_5_vx_2 b

While doing the example, the values in the table "table_5_full" for the edge "a-b" in table_1 are

Column names Values in Row 1
tb_5_vx_1 a
tb_5_vx_2 b
tb_5_vx_3 b
tb_5_vx_4 e
tb_5_vx_5 e
tb_5_vx_6 c
tb_5_vx_7 c
tb_5_vx_8 d
tb_5_vx_9 d
tb_5_vx_10 a


Then execute cleanProcessTables.php.
Then rotate the edge "a-b", to get the edge "b-a".
Put the edge "b-a" in table_1 after deleting the row in table_1 containing the edge "a-b".

So table_1 now contains

Column names Values in Row 1
tb_5_vx_1 b
tb_5_vx_2 a

Now execute TSPexample_5_vertex.php. The result will be in table_5_full. The values in table_5_full are

table_5_full
Column names Values in Row 1 Values in Row 2
tb_5_vx_1 a b
tb_5_vx_2 b a
tb_5_vx_3 b a
tb_5_vx_4 e d
tb_5_vx_5 e d
tb_5_vx_6 c c
tb_5_vx_7 c c
tb_5_vx_8 d e
tb_5_vx_9 d e
tb_5_vx_10 a b

Then execute cleanProcessTables.php.
Now suppose, a hamilton circuit for the edge "b-c" needs to be found out. Then the edge "b-c" is put into table_1, after deleting the previous

edge that was present in table_1. So table_1 is as follows.

table_1
Column names Values in Row 1
tb_5_vx_1 b
tb_5_vx_2 c

Now execute TSPexample_5_vertex.php. The result will be in table_5_full. The values in table_5_full are

Column names Values in Row 1 Values in Row 2 Values in Row 3
tb_5_vx_1 a b b
tb_5_vx_2 b a c
tb_5_vx_3 b a c
tb_5_vx_4 e d d
tb_5_vx_5 e d d
tb_5_vx_6 c c a
tb_5_vx_7 c c a
tb_5_vx_8 d e e
tb_5_vx_9 d e e
tb_5_vx_10 a b b

Now suppose , we want to display the weights of the edges present in the hamilton circuit. Only the total weight of the hamilton circuit is done

by pen and paper method. Now execute TSPexample_5_vertex_weight.php. Then the values are obtained in table_5_full_weight. The values

in table_5_full_weight are

Column names Values in Row 1 Values in Row 2 Values in Row 3
tb_5_vx_1 a b b
*tb_5_vx_2 b a c
tb_5_vx_3 b a c
tb_5_vx_4 e d d
tb_5_vx_5 e d d
tb_5_vx_6 c c a
tb_5_vx_7 c c a
tb_5_vx_8 d e e
tb_5_vx_9 d e e
tb_5_vx_10 a b b
w1 14 14 9
w2 5 7 6
w3 8 6 7
w4 6 8 10
w5 7 5 5


The following is the code for the 5 php files.

The code for TSPexample_5_vertex.php is
<?php

/* BEGIN */

/*
* The edges of the 5 vertex graph are
*
* a-b 1
* b-a 1
* a-c 10
* c-a 10
* a-e 6
* e-a 6
* a-d 5
* d-a 5
* b-e 2
* e-b 2
* b-d 8
* d-b 8
* b-c 9
* c-b 9
* c-e 3
* e-c 3
* c-d 4
* d-c 4
* d-e 7
* e-d 7
*
*/






$connection = mysql_connect("localhost","root","");
$db = mysql_select_db("tsp_5_vertex_graph",$connection);

$var_1 ="";
$var_2 ="";
$var_3 ="";
$var_4 ="";
$var_5 = "";
$var_6 ="";
$var_7="";
$var_8="";

$query_ck_tb = "select ck_vx_1 , ck_vx_2 from check_table order by weight";
$result_ck_tb = mysql_query($query_ck_tb) or die(mysql_error()."message_1");
// above code is for the check table which is always needed.

//******************First part

$query_tb_1 = "select tb_1_vx_1,tb_1_vx_2 from table_1";
$result_tb_1 = mysql_query($query_tb_1) or die(mysql_error()."message_2");

while($row_tb_1 = mysql_fetch_array($result_tb_1))
{

while($row_ck_tb = mysql_fetch_array($result_ck_tb))
{

if(($row_tb_1['tb_1_vx_2'] == $row_ck_tb['ck_vx_1']) && ($row_tb_1['tb_1_vx_1'] != $row_ck_tb['ck_vx_2']))
{
$var_1 = $row_tb_1['tb_1_vx_1'];
$var_2 = $row_tb_1['tb_1_vx_2'];
$var_3 = $row_ck_tb['ck_vx_1'];
$var_4 = $row_ck_tb['ck_vx_2'];
break; // comes out of the while loop once a match is found.
}
}
}
$query_ins_1 = "insert into table_2(tb_2_vx_1,tb_2_vx_2,tb_2_vx_3,tb_2_vx_4) values ('$var_1','$var_2','$var_3','$var_4')";
mysql_query($query_ins_1) or die(mysql_error()."message_3");

//*********************** Second part

$result_ck_tb = mysql_query($query_ck_tb) or die(mysql_error()."message_1");

$query_tb_2 = "select tb_2_vx_1,tb_2_vx_2,tb_2_vx_3,tb_2_vx_4 from table_2";
$result_tb_2 = mysql_query($query_tb_2) or die(m*ysql_error()."message_4");

while($row_tb_2 = mysql_fetch_array($result_tb_2))
{

while($row_ck_tb = mysql_fetch_array($result_ck_tb))
{
if(
($row_tb_2['tb_2_vx_4'] == $row_ck_tb['ck_vx_1'])
&& (
($row_tb_2['tb_2_vx_3'] != $row_ck_tb['ck_vx_2'])
&&
($row_ck_tb['ck_vx_2'] != $row_tb_2['tb_2_vx_1'])
)
)
{

$var_1 = $row_tb_2['tb_2_vx_1'];
$var_2 = $row_tb_2['tb_2_vx_2'];
$var_3 = $row_tb_2['tb_2_vx_3'];
$var_4 = $row_tb_2['tb_2_vx_4'];
$var_5 = $row_ck_tb['ck_vx_1'];
$var_6 = $row_ck_tb['ck_vx_2'];
break;
}
}

}

$query_ins_2 = "insert into table_3(tb_3_vx_1,tb_3_vx_2,tb_3_vx_3,tb_3_vx_4,tb_3_vx_5,tb_3_vx_6) values

('$var_1','$var_2','$var_3','$var_4','$var_5','$var_6')";
mysql_query($query_ins_2) or die(mysql_error()."message_5");

/****************Third part

$result_ck_tb = mysql_query($query_ck_tb) or die(mysql_error()."message_1"); // very important code. Needed to bring the file pointer to

read from the beginning of the edge table, so that the edges are taken from the beginning

$query_tb_3 = "select tb_3_vx_1,tb_3_vx_2,tb_3_vx_3,tb_3_vx_4,tb_3_vx_5,tb_3_vx_6 from table_3";
$result_tb_3 = mysql_query($query_tb_3) or die(mysql_error()."message_6");

while($row_tb_3 = mysql_fetch_array($result_tb_3))
{

while($row_ck_tb = mysql_fetch_array($result_ck_tb))
{
if(
($row_ck_tb['ck_vx_1'] == $row_tb_3['tb_3_vx_6']) &&
(
($row_ck_tb['ck_vx_2'] != $row_tb_3['tb_3_vx_5'] ) &&
($row_ck_tb['ck_vx_2'] != $row_tb_3['tb_3_vx_3'] ) &&
($row_ck_tb['ck_vx_2'] != $row_tb_3['tb_3_vx_1'] )
)

)
{

$var_1 = $row_tb_3['tb_3_vx_1'];
$var_2 = $row_tb_3['tb_3_vx_2'];
$var_3 = $row_tb_3['tb_3_vx_3'];
$var_4 = $row_tb_3['tb_3_vx_4'];
$var_5 = $row_tb_3['tb_3_vx_5'];
$var_6 = $row_tb_3['tb_3_vx_6'];
$var_7 = $row_ck_tb['ck_vx_1'];
$var_8 = $row_ck_tb['ck_vx_2'];
* break;
}
}

}

$query_ins_3 = "insert into table_4(tb_4_vx_1 , tb_4_vx_2 , tb_4_vx_3 , tb_4_vx_4 , tb_4_vx_5 , tb_4_vx_6 , tb_4_vx_7 , tb_4_vx_8) values

('$var_1','$var_2','$var_3','$var_4','$var_5','$var_6','$var_7','$var_8')";
mysql_query($query_ins_3) or die(mysql_error()."message_7");

//****************Fourth part

$result_ck_tb = mysql_query($query_ck_tb) or die(mysql_error()."message_1"); // very important code. Needed to bring the file pointer to

read from the beginning of the edge table, so that the edges are taken from the beginning of check_table.

$query_tb_4 = "select tb_4_vx_1,tb_4_vx_2,tb_4_vx_3,tb_4_vx_4,tb_4_vx_5,tb_4_vx_6,tb_4_vx_7,tb_4_vx_8 from table_4";
$result_tb_4 = mysql_query($query_tb_4) or die(mysql_error()."message_8");

while($row_tb_4 = mysql_fetch_array($result_tb_4))
{

while($row_ck_tb = mysql_fetch_array($result_ck_tb))
{
if(
($row_ck_tb['ck_vx_1'] == $row_tb_4['tb_4_vx_8']) &&
($row_ck_tb['ck_vx_2'] == $row_tb_4['tb_4_vx_1'])
)
{

$var_1 = $row_tb_4['tb_4_vx_1'];
$var_2 = $row_tb_4['tb_4_vx_2'];
$var_3 = $row_tb_4['tb_4_vx_3'];
$var_4 = $row_tb_4['tb_4_vx_4'];
$var_5 = $row_tb_4['tb_4_vx_5'];
$var_6 = $row_tb_4['tb_4_vx_6'];
$var_7 = $row_tb_4['tb_4_vx_7'];
$var_8 = $row_tb_4['tb_4_vx_8'];
$var_9 = $row_ck_tb['ck_vx_1'];
$var_10 = $row_ck_tb['ck_vx_2'];

break;
}
}

}

$query_ins_4 = "insert into table_5(tb_5_vx_1 , tb_5_vx_2 , tb_5_vx_3 , tb_5_vx_4 , tb_5_vx_5 , tb_5_vx_6 , tb_5_vx_7 ,

tb_5_vx_8,tb_5_vx_9 , tb_5_vx_10) values ('$var_1','$var_2','$var_3','$var_4','$var_5','$var_6','$var_7','$var_8','$var_9','$var_10')";
mysql_query($query_ins_4) or die(mysql_error()."message_9");

$query_data = "insert into table_5_full select * from table_5";
$result_data = mysql_query($query_data) or die(mysql_error()."message_10");

echo "Obtained a hamilton circuit for the particular edge. <br>The circuit is present in \"table_5_full\".<br> To get circuit for the next edge ,

please execute \"cleanProcessTables.php\" file first. <br> Then put the edge to be processed in \"table_1\" by replacing the edge in \"table_1\"

which was already processed. <br> Then execute \"TSPexample_5_vertex.php\" file to get the circuit for the new edge. <br>The above

process needs to be repeated for each new edge to be processed.<br> If after you finished processing some of the edges of the graph and if

you want to display the weights of the edges, then execute \"TSPexample_5_vertex_weight.php\" file. <br>The weights will be present in

\"table_5_full_weight\" table after execution of the file. <br>Note that the circuits whose weights are to be found must be present in

\"table_5_full\" table which is to be used as input data for the successful execution of \"TSPexample_5_vertex_weight.php\" file.<br> Please

note that execution of \"cleanCircuitTables.php\" file will delete the circuits ie:- clean the data present in \"table_5_full\" table. <br>So if you

want to display the weights of the edges of the circuits in \"table_5_full_weight\" table, then the file \"cleanCircuitTables.php\" should never be

executed. " ;

/* END */

?>


The code for TSPexample_5_vertex_weight.php is
<?php

/* BEGIN */
/*
* This program is for saving the weights of check_table to corresond with the edges in table_5_full and then put them all together in

table_5_full_weight table. table_5_full_weight contains the extra columns w1,w2,w3,w4 and w5 for weights of the edges.
*/


$connection = mysql_connect("localhost","root","");
$db = mysql_select_db("tsp_5_vertex_graph",$connection);

$query = "delete from table_5_full_weight";
mysql_query($query) or die(mysql_error());


$query_1 = "select tb_5_vx_1 , tb_5_vx_2 , tb_5_vx_3 , tb_5_vx_4 , tb_5_vx_5 , tb_5_vx_6 , tb_5_vx_7 , tb_5_vx_8 , tb_5_vx_9 ,

tb_5_vx_10 from table_5_full";
$result_1 = mysql_query($query_1) or die(mysql_error()."message_11");

while($row_1 = mysql_fetch_array($result_1))
{
$vertex_1 = $row_1['tb_5_vx_1'];
$vertex_2 = $row_1['tb_5_vx_2'];
$vertex_3 = $row_1['tb_5_vx_3'];
$vertex_4 = $row_1['tb_5_vx_4'];
$vertex_5 = $row_1['tb_5_vx_5'];
$vertex_6 = $row_1['tb_5_vx_6'];
$vertex_7 = $row_1['tb_5_vx_7'];
$vertex_8 = $row_1['tb_5_vx_8'];
$vertex_9 = $row_1['tb_5_vx_9'];
$vertex_10 = $row_1['tb_5_vx_10'];

//********************


$query = "insert into table_5_full_weight (tb_5_vx_1 , tb_5_vx_2 , tb_5_vx_3 , tb_5_vx_4 , tb_5_vx_5 ,tb_5_vx_6 , tb_5_vx_7 , tb_5_vx_8 ,

tb_5_vx_9 , tb_5_vx_10) values

('$vertex_1','$vertex_2','$vertex_3','$vertex_4','$vertex_5','$vertex_6','$vertex_7','$vertex_8','$vertex_9','$vertex_10')";
mysql_query($query) or die(mysql_error());




//*******************

$query_2 = "select weight from check_table where ck_vx_1 = '$vertex_1' and ck_vx_2 = '$vertex_2' ";
$result_2 = mysql_query($query_2) or die(mysql_error()."message_1");

while($row_2 = mysql_fetch_array($result_2))
{

$w1 = $row_2['weight'];

$query_3 = "update table_5_full_weight set w1 = '$w1' where tb_5_vx_1 = '$vertex_1' and tb_5_vx_2 = '$vertex_2'" ;
$result_3 = mysql_query($query_3) or die(mysql_error()."message_2");

}

//***************

$query_4 = "select weight from check_table where ck_vx_1 = '$vertex_3' and ck_vx_2 = '$vertex_4' ";
$result_4 = mysql_query($query_4) or die(mysql_error()."message_3");

while($row_4 = mysql_fetch_array($result_4))
{

$w2 = $row_4['weight'];

$query_5 = "update table_5_full_weight set w2 = '$w2' where tb_5_vx_3 = '$vertex_3' and tb_5_vx_4 = '$vertex_4'" ;
$result_5 = mysql_query($query_5) or die(mysql_error()."message_4");

}

//*************


$query_6 = "select weight from check_table where ck_vx_1 = '$vertex_5' and ck_vx_2 = '$vertex_6' ";
$result_6 = mysql_query($query_6) or die(mysql_error()."message_5");


while($row_6 = mysql_fetch_array($result_6))
{

$w3 = $row_6['weight'];

$query_7 = "update table_5_full_weight set w3 = '$w3' where tb_5_vx_5 = '$vertex_5' and tb_5_vx_6 = '$vertex_6'" ;
$result_7 = mysql_query($query_7) or die(mysql_error()."message_6");

}


//********************

$query_8 = "select weight from check_table where ck_vx_1 = '$vertex_7' and ck_vx_2 = '$vertex_8' ";
$result_8 = mysql_query($query_8) or die(mysql_error()."message_7");

while($row_8 = mysql_fetch_array($result_8))
{

$w4 = $row_8['weight'];

$query_9 = "update table_5_full_weight set w4 = '$w4' where tb_5_vx_7 = '$vertex_7' and tb_5_vx_8 = '$vertex_8'" ;
$result_9 = mysql_query($query_9) or die(mysql_error()."message_8");

}

//*****************************


$query_10 = "select weight from check_table where ck_vx_1 = '$vertex_9' and ck_vx_2 = '$vertex_10' ";
$result_10 = mysql_query($query_10) or die(mysql_error()."message_9");

while($row_10 = mysql_fetch_array($result_10))
{

$w5 = $row_10['weight'];

$query_11 = "update table_5_full_weight set w5 = '$w5' where tb_5_vx_9 = '$vertex_9' and tb_5_vx_10 = '$vertex_10'" ;
$result_11 = mysql_query($query_11) or die(mysql_error()."message_10");

}



}

echo "The weights are present in \"table_5_full_weight\" table."

/* END */

?>




The code for cleanProcessTables.php is

<?php

/* BEGIN */

// for cleaning table_2, table_3, table_4 and table_5 respectively.


$connection = mysql_connect("localhost","root","");
$db = mysql_select_db("tsp_5_vertex_graph",$connection);

$query_one = "delete from table_2";
$result_one = mysql_query($query_one) or die(mysql_error());
$query_two = "delete from table_3";
$result_two = mysql_query($query_two) or die(mysql_error());
$query_three = "delete from table_4";
$result_three = mysql_query($query_three) or die(mysql_error());
$query_four = "delete from table_5";
$result_four = mysql_query($query_four) or die(mysql_error());

if($result_one && $result_two && $result_three && $result_four)
{
echo "Cleaned the processing tables";
}

/* END */
?>



The code for cleanCircuitTables.php is

<?php

/* BEGIN */

// For cleaning "table_5_full" table.
//Clean this table only after you have finished all the work and only if necessary.

$connection = mysql_connect("localhost","root","");
$db = mysql_select_db("tsp_5_vertex_graph",$connection);

$query = "delete from table_5_full";
$result = mysql_query($query) or die(mysql_error());

if($result)
{
echo "Cleaned the table which contained the output of hamilton circuits";
}

/* END */

?>


The code for cleanWeightTables.php is
<?php

/* BEGIN */

// cleans the "table_5_full_weight" table.
//Clean this table only after you have finished all the work and only if necessary.

$connection = mysql_connect("localhost","root","");
$db = mysql_select_db("tsp_5_vertex_graph",$connection);

$query = "delete from table_5_full_weight";
$result = mysql_query($query) or die(mysql_error());

if($result)
{
echo "Cleaned the weight tables";
}

/* END */

?>

Please Note:- I am not able to edit the notes at all after I have copied it into the site's editor. So I have uploaded 2 document files which

show a little more clearly about the edges and the weights in the tables. Also I am not allowed to upload php files or sql export files in the

site. So I have only attached documents explaining about how the program is to be done.
Also this program is for a 5 vertex complete graph. This program can be modified to solve a complete graph with any number of vertices.
Also this program is for the "MSEM" method which I had given and mentioned in the previous posts.

[kidjan]

You should make it work with standard TSP datasets, such as those found here and here. And then report your results with a large dataset.

[varghese]

Code: Select all

Hello to All,

      I have found a new method which is simpler in another way from the previous method that I had given in the previous posts.  The new method is entirely different from the previous method. Also new notations are given in the method below which are more simpler than the previous notations that I had given for the previous method. I have uploaded MS Word document "TSP_Oct_2014.docx" which contains the same content that I have posted here for reference purpose.

The new method is as given below.


General Note :-  This note is for finding a polynomial time solution for the "Travelling Salesman Problem" for a complete graph for any number of vertices. The solutions that I am getting for the examples given in the textbooks ( References for the textbooks are given in the last part of this posting ) are giving the correct answers.


A brief description about the Notations.

Beginning of Notations.

   A notation is followed by '::-' characters. After '::-' characters, an explanation is given about the
notation starting in the next line. In order to make it simple , I have given the examples in the notation itself , in order to explain the notation.
   The vertices of a graph can be alphabets, numbers or a combination of both ie:- alphanumeric characters. 

[] ::-
The square brackets denote a partial circuit . A partial circuit is a graph in which any vertex of the graph is
joined to another vertex by only a single edge. The partial circuit may be empty or it may consists of vertices or both vertices and edges.

[a] ::-
Denotes a partial circuit containing a single vertex or it denotes a single vertex. Here it denotes a partial
circuit containing a vertex named 'a'.

[a,b] ::-
Denotes that vertex 'a' is joined to vertex 'b' or that there is an edge which joins vertex 'a' with vertex 'b'.
Here each vertex is separated by a comma.

[a,b,c] ::-
Denotes that vertex 'a' is joined to vertex 'b' and vertex 'b' is joined to vertex 'c'.
So in the '[]' notation, any number of vertices( each vertex separtated by comma ) can be written.

[a,b,c,a] ::-
Denotes a partial circuit in which it is also a hamilton circuit, because here vertex 'a' is joined to vertex 'b'
and vertex 'b' is joined to vertex 'c' and vertex 'c' is joined to vertex 'a'. This partial circuit can also be
written as [b,c,a,b]. So [a,b,c,a]  is the same partial circuit as that of [b,c,a,b].

w[a,b,c] ::-
Denotes the weight of the partial circuit. This weight is the sum total of all the individual weights of the edges of the partial circuit. For eg:- if w[a,b] = 20 and w[b,c] = 30, then w[a,b,c] = w[a,b] + w[b,c] = 20 + 30 = 50.

[a,b,c] + [b,c,d] = [a,b,c,d] ::-
Here the two partial circuits [a,b,c] and [b,c,d] are combined to get [a,b,c,d] because the edge of [b,c] is common in both partial circuits. Here the total weight of [a,b,c,d] should be got by taking into consideration the common edge of [b,c]. So w[b,c] only needs to be added once.
For eg:-
if
w[a,b,c] = w[a,b] + w[b,c] = 20 + 30 = 50
and
w[b,c,d] = w[b,c] + w[c,d] = 30 + 40 = 70
and
if [a,b,c,d] = [a,b,c] + [b,c,d]
Then,
w[a,b,c,d] = w[a,b] + w[b,c] + w[c,d] = 20 + 30 + 40 = 90
   So w[a,b,c,d] is not got by directly adding the weights of w[a,b,c] and w[b,c,d] , since there is a common edge of [b,c] present in both [a,b,c] and [b,c,d]. So w[a,b,c,d] is not equal to w[a,b,c] + w[b,c,d] ie:- not equal to 120 (50 + 70 = 120).

ec[a] ::-
Denotes an 'edge count' of the vertex 'a'. An 'edge count' is the number of edges attached to a vertex. For eg:- in [a,b,c] , ec[a] = 1, ec[b] = 2 and ec[c] = 1. Here the edge count of [b] is 2 since there are 2 edges attached to vertex 'b'. ec[a] = 1 , because there is only one edge attached to vertex 'a'. In a partial circuit, the edge count of each vertex should be less than or equal to 2, to satisfy the criterion of a hamilton circuit, when the partial circuit is used to form the hamilton circuit in the end of the process.

Section #1.m (BEGIN) ::-
This denotes the section of "Example 1". 'm' denotes any number greater than or equal to one. Also 'BEGIN' denotes the beginning of the section.

Section #1.m (END) ::-
This denotes the section of "Example 1". 'm' denotes any number greater than or equal to one. Also 'END' denotes the end of the section.

Section #2.m (BEGIN) ::-
This denotes the section of "Example 2". 'm' denotes any number greater than or equal to one. Also 'BEGIN' denotes the beginning of the section.

Section #2.m (END) ::-
This denotes the section of "Example 2". 'm' denotes any number greater than or equal to one. Also 'END' denotes the end of the section.

->{Dm} ::-
Here 'D' means description. 'm' stands for any number greater than or equal to one. This marker ie:- '-->{Dm}' gives the statement number which marks a statement which precedes the '-->{D1}' marker.  This marker is written elsewhere which gives a description of the statement which it marks. This marker is used mainly inside sections when space is required for writing descriptions.

->Dm. ::-
Here 'D' means description and 'm' stands for any number greater than or equal to one. This marker ie:- '->Dm' gives a description of the statement which it has marked.

C(n,r) ::-
This means a 'combination' of 'n' number of edges taken 'r' at a time. Here 'n' and 'r' are numbers. This
'combination' is the same combination that is there in mathematics. Here C(n,r) = n!/(r!*(n-r)!)

End of Notations.

Below are given some examples for describing properties of joining of partial circuits.

1) Two partial circuits are [a,b,c] and [b,d,c]. When these two partial circuits are joined, [b,c] of [a,b,c] can be replaced by [b,d,c]. Since one more vertex 'd' is added, the edge count of each vertex is not violated ( ie:- the edge count of each vertex is less than or equal to 2 ). So the joined partial circuit becomes [a,b,d,c] ( Here the edge [b,c] is replaced by [b,d,c] ).

2) Two partial circuits are [a,b,c] and [a,d,c]. If the hamilton circuit required to be found consists of only 4
vertices, then these partial circuits can be joined. So if the hamilton circuit consists of only 4 vertices, the the two partial circuits can be joined to get the partial circuit [a,b,c,d,a]. This partial circuit ie:- [a,b,c,d,a] is a hamilton circuit consisting of 4 vertices.   But suppose , if the hamilton circuit required consisted of for eg:- 5 vertices, then these two partial circuits cannot be joined, because if they are joined, then they will already form a hamilton circuit of 4 vertices, which is not what is wanted, but instead a hamilton circuit of 5 vertices is required. Also [a,b,c] cannot be replaced by [a,d,c], because if a new vertex is obtained, in its place another vertex becomes lost, for eg:- if vertex 'd' is obtained, then vertex 'b' is lost if [a,b,c] is replaced by [a,d,c].

3) Two partial circuits are [a,b,c] and [c,d,e]. These two partial circuits can be joined at the common vertex 'c'. So the partial circuit after joining is [a,b,c,d,e].

4) Two partial circuits are [a,b,c] and [b,d,e]. These two partial circuits cannot be joined at the common vertex 'b', since if the two partial circuits are joined, it would violate the edge count of vertex 'b' ie:- the edge count of vertex 'b' would be 3 after joining the partial circuits.

5) Two partial circuits are [a,b,c] and [c,b,d]. These two partial circuits cannot be joined at the common edge [b,c], because if the two partial circuits are joined, it would violate the edge count of vertex 'b' ie:- the edge count of vertex 'b' would be 3 after joining the partial circuits.

Example 1
This example is taken from the Book "Elements of Discrete Mathematics" by C.L.Liu.  The solution for the example is got in the process described from Section #1.1 to Section #1.9.

Section #1.1 (BEGIN)

Vertex a      ->{D1}   
w[a,d] = 7    ->{D2}       
w[a,e] = 10
w[a,c] = 12
w[a,b] = 14
   
Vertex b   
w[b,e] = 5
w[b,c] = 9
w[b,d] = 13
w[b,a] = 14
   
Vertex c   
w[c,d] = 6
w[c,e] = 8
w[c,b] = 9
w[c,a] = 12
   
Vertex d   
w[d,c] = 6
w[d,a] = 7
w[d,e] = 11
w[d,b] = 13
   
Vertex e   
w[e,b] = 5
w[e,c] = 8
w[e,a] = 10
w[e,d] = 11


->D1. This shows the heading marked 'Vertex a'.
->D2. This shows the weight of one of the edges ( namely edge [a,d] ) which is connected to Vertex a.

   In this section, the weights of the different edges connected to the different vertices of a 5 vertex graph is shown. The 5 vertex graph is the example taken from the book "Elements of discrete mathematics" .

Section #1.1 (END)


Section #1.2 (BEGIN)

In this section a combination of the edges ( the edges are taken from Section #1.1 ) connected to a particular vertex is taken. For eg:- there are four edges connected to vertex a. So the number of combinations of the four edges connected to 'vertex a' by taking two edges at a time is C(4,2) = 4!/((4-2)!*2!) = 6.

Vertex a    
[a,d] + [a,e] = [d,a,e]
[a,d] + [a,c] = [d,a,c]
[a,d] + [a,b] = [d,a,b]
[a,e] + [a,c] = [e,a,c]
[a,e] + [a,b] = [e,a,b]
[a,c] + [a,b] = [c,a,b]
   
Vertex b    
[b,e] + [b,c] = [e,b,c] 
[b,e] + [b,d] = [e,b,d] 
[b,e] + [b,a] = [e,b,a]
[b,c] + [b,d] = [c,b,d]
[b,c] + [b,a] = [c,b,a] 
[b,d] + [b,a] = [d,b,a]
   
Vertex c    
[c,d] + [c,e] = [d,c,e]
[c,d] + [c,b] = [d,c,b]
[c,d] + [c,a] = [d,c,a] 
[c,e] + [c,b] = [e,c,b] 
[c,e] + [c,a] = [e,c,a] 
[c,b] + [c,a] = [b,c,a]
   
Vertex d    
[d,c] + [d,a] = [c,d,a]
[d,c] + [d,e] = [c,d,e]
[d,c] + [d,b] = [c,d,b]
[d,a] + [d,e] = [a,d,e]
[d,a] + [d,b] = [a,d,b] 
[d,e] + [d,b] = [e,d,b]
   
Vertex e    
[e,b] + [e,c] = [b,e,c]
[e,b] + [e,a] = [b,e,a]
[e,b] + [e,d] = [b,e,d]
[e,c] + [e,a] = [c,e,a]
[e,c] + [e,d] = [c,e,d]
[e,a] + [e,d] = [b,e,c]

Section #1.2 (END)


Section #1.3 (BEGIN)

In this section, the weights of the partial circuits( these partial circuits were obtained in Section #1.2 ) of a
particular vertex are given below.

Vertex a
w[d,a,e] = 7+10 = 17
w[d,a,c] = 7+12 = 19
w[d,a,b] = 7+14 = 21
w[e,a,c] = 10+12 = 22
w[e,a,b] = 10+14 = 24
w[c,a,b] = 12+14 = 26

Vertex b      
w[e,b,c] = 5+9 = 14
w[e,b,d] = 5+13 = 18
w[e,b,a] = 5+14 = 19
w[c,b,d] = 9+13 = 22
w[c,b,a] = 9+14 = 23
w[d,b,a] = 13+14 = 27

Vertex c      
w[d,c,e] = 6+8 = 14
w[d,c,b] = 6+9 = 15
w[d,c,a] = 6+12 = 18
w[e,c,b] = 8+9 = 17
w[e,c,a] = 8+12 = 20
w[b,c,a] = 9+12 = 21

Vertex d      
w[c,d,a] = 6+7 = 13
w[c,d,e] = 6+11 = 17
w[c,d,b] = 6+13 = 19
w[a,d,e] = 7+11 = 18
w[a,d,b] = 7+13 = 20
w[e,d,b] = 11+13 = 24
   
Vertex e   
w[b,e,c] = 5+8 = 13
w[b,e,a] = 5+10 = 15
w[b,e,d] = 5+11 = 16
w[c,e,a] = 8+10 = 18
w[c,e,d] = 8+11 = 19
w[b,e,c] = 10+11 = 21

Section #1.3 (END)


Section #1.4 (BEGIN)

In this section, the partial circuits under each vertex are sorted in 'Ascending order' according to their weights.

Vertex a ( sorted )                  
[a,d] + [a,e] = [d,a,e]          w[d,a,e] = 7+10 = 17
[a,d] + [a,c] = [d,a,c]          w[d,a,c] = 7+12 = 19
[a,d] + [a,b] = [d,a,b]          w[d,a,b] = 7+14 = 21
[a,e] + [a,c] = [e,a,c]          w[e,a,c] = 10+12 = 22
[a,e] + [a,b] = [e,a,b]          w[e,a,b] = 10+14 = 24
[a,c] + [a,b] = [c,a,b]          w[c,a,b] = 12+14 = 26
                  
Vertex b  ( sorted )                  
[b,e] + [b,c] = [e,b,c]          w[e,b,c] =  5+9 = 14
[b,e] + [b,d] = [e,b,d]          w[e,b,d] =  5+13 = 18
[b,e] + [b,a] = [e,b,a]          w[e,b,a] =  5+14 = 19
[b,c] + [b,d] = [c,b,d]          w[c,b,d] =  9+13 = 22
[b,c] + [b,a] = [c,b,a]          w[c,b,a] =  9+14 = 23
[b,d] + [b,a] = [d,b,a]          w[d,b,a] =  13+14 = 27
                  
Vertex c  ( sorted )                  
[c,d] + [c,e] = [d,c,e]          w[d,c,e] =  6+8 = 14
[c,d] + [c,b] = [d,c,b]          w[d,c,b] =  6+9 = 15
[c,e] + [c,b] = [e,c,b]          w[e,c,b] =  8+9 = 17
[c,d] + [c,a] = [d,c,a]          w[d,c,a] =  6+12 = 18
[c,e] + [c,a] = [e,c,a]          w[e,c,a] =  8+12 = 20
[c,b] + [c,a] = [b,c,a]          w[b,c,a] =  9+12 = 21
                  
Vertex d  ( sorted )                  
[d,c] + [d,a] = [c,d,a]          w[c,d,a] =  6+7 = 13
[d,c] + [d,e] = [c,d,e]          w[c,d,e] =  6+11 = 17
[d,a] + [d,e] = [a,d,e]          w[a,d,e] =  7+11 = 18
[d,c] + [d,b] = [c,d,b]          w[c,d,b] =  6+13 = 19
[d,a] + [d,b] = [a,d,b]          w[a,d,b] =  7+13 = 20
[d,e] + [d,b] = [e,d,b]          w[e,d,b] =  11+13 = 24
                  
Vertex e  ( sorted )                  
[e,b] + [e,c] = [b,e,c]          w[b,e,c] =  5+8 = 13
[e,b] + [e,a] = [b,e,a]          w[b,e,a] =  5+10 = 15
[e,b] + [e,d] = [b,e,d]          w[b,e,d] =  5+11 = 16
[e,c] + [e,a] = [c,e,a]          w[c,e,a] =  8+10 = 18
[e,c] + [e,d] = [c,e,d]          w[c,e,d] =  8+11 = 19
[e,a] + [e,d] = [b,e,c]          w[b,e,c] =  10+11 = 21

Section #1.4 (END)

Section #1.5 (BEGIN)

In this section, the partial circuit with the lowest weight under each vertex is taken individually and written
below.

[a,d] + [a,e] = [d,a,e]          w[d,a,e] = 7+10 = 17   ->{D3}
[b,e] + [b,c] = [e,b,c]          w[e,b,c] = 5+9 = 14     ->{D4}
[c,d] + [c,e] = [d,c,e]          w[d,c,e] = 6+8 = 14
[d,c] + [d,a] = [c,d,a]          w[c,d,a] = 6+7 = 13
[e,b] + [e,c] = [b,e,c]          w[b,e,c] = 5+8 = 13

->D3. Here [d,a,e] is the lowest weight combination taken from Vertex a.
->D4. Here [e,b,c] is the lowest weight combination taken from Vertex b.

Section #1.5 (END)


Section #1.6 (BEGIN)

In this section, the partial circuits written in Section #1.5 are sorted in 'Descending order' of their weights and written here.

[a,d] + [a,e] = [d,a,e]    w[d,a,e] = 7+10 = 17   ( vertex a )   ->{D5}
[b,e] + [b,c] = [e,b,c]          w[e,b,c] = 5+9 = 14    ( vertex b )
[c,d] + [c,e] = [d,c,e]          w[d,c,e] = 6+8 = 14    ( vertex c )
[d,c] + [d,a] = [c,d,a]          w[c,d,a] = 6+7 = 13    ( vertex d )
[e,b] + [e,c] = [b,e,c]          w[b,e,c] = 5+8 = 13    ( vertex e )

->D5. [d,a,e] is a partial circuit having the highest weight in the group in this section.

Section #1.6 (END)


Section #1.7 (BEGIN)

In this section, in order to choose a partial circuit ( or the  order of which vertex to choose from ) is given by the order in Section #1.6. So the order is as follows ie:- vertex a, vertex b , vertex c, vertex d, vertex e.

Vertex a ( sorted )
[a,d] + [a,e] = [d,a,e]          w[d,a,e] = 7+10 = 17
[a,d] + [a,c] = [d,a,c]          w[d,a,c] = 7+12 = 19
[a,d] + [a,b] = [d,a,b]          w[d,a,b] = 7+14 = 21
[a,e] + [a,c] = [e,a,c]          w[e,a,c] = 10+12 = 22
[a,e] + [a,b] = [e,a,b]          w[e,a,b] = 10+14 = 24
[a,c] + [a,b] = [c,a,b]          w[c,a,b] = 12+14 = 26
                  
Vertex b ( sorted )
[b,e] + [b,c] = [e,b,c]          w[e,b,c] = 5+9 = 14
[b,e] + [b,d] = [e,b,d]          w[e,b,d] = 5+13 = 18
[b,e] + [b,a] = [e,b,a]          w[e,b,a] = 5+14 = 19
[b,c] + [b,d] = [c,b,d]          w[c,b,d] = 9+13 = 22
[b,c] + [b,a] = [c,b,a]          w[c,b,a] = 9+14 = 23
[b,d] + [b,a] = [d,b,a]          w[d,b,a] = 13+14 = 27

Vertex c ( sorted )                  
[c,d] + [c,e] = [d,c,e]          w[d,c,e] = 6+8 = 14
[c,d] + [c,b] = [d,c,b]          w[d,c,b] = 6+9 = 15
[c,e] + [c,b] = [e,c,b]          w[e,c,b] = 8+9 = 17
[c,d] + [c,a] = [d,c,a]          w[d,c,a] = 6+12 = 18
[c,e] + [c,a] = [e,c,a]          w[e,c,a] = 8+12 = 20
[c,b] + [c,a] = [b,c,a]          w[b,c,a] = 9+12 = 21
                  
Vertex d ( sorted )
[d,c] + [d,a] = [c,d,a]          w[c,d,a] = 6+7 = 13
[d,c] + [d,e] = [c,d,e]          w[c,d,e] = 6+11 = 17
[d,a] + [d,e] = [a,d,e]          w[a,d,e] = 7+11 = 18
[d,c] + [d,b] = [c,d,b]          w[c,d,b] = 6+13 = 19
[d,a] + [d,b] = [a,d,b]          w[a,d,b] = 7+13 = 20
[d,e] + [d,b] = [e,d,b]          w[e,d,b] = 11+13 = 24
                  
Vertex e ( sorted )
[e,b] + [e,c] = [b,e,c]          w[b,e,c] = 5+8 = 13
[e,b] + [e,a] = [b,e,a]          w[b,e,a] = 5+10 = 15
[e,b] + [e,d] = [b,e,d]          w[b,e,d] = 5+11 = 16
[e,c] + [e,a] = [c,e,a]          w[c,e,a] = 8+10 = 18
[e,c] + [e,d] = [c,e,d]          w[c,e,d] = 8+11 = 19
[e,a] + [e,d] = [b,e,c]          w[b,e,c] = 10+11 = 21

Section #1.7 (END)

Section #1.8 (BEGIN)

Now from Section #1.7, take a partial circuit from each vertex ( the order of the vertex to be taken , should be the same order in which the vertices are written in Section #1.7 ) and join them together in order to form a hamilton circuit. The process is as follows :-

1) Take [d,a,e] from Vertex a. Since hamilton circuit rule is not violated, [d,a,e] is taken.
2) Take [e,b,c] from Vertex b. [e,b,c] fits with [d,a,e]. So [e,b,c] is also taken. The new partial circuit is
[d,a,e,b,c].
3) Take [d,c,e] from Vertex c. [d,c,e] does not fit with [d,a,e,b,c]. So the next step is not to go to the next
vertex but to take another partial circuit from the same vertex to see if it fits with [d,a,e,b,c]. So take [d,c,b] from Vertex c. [d,c,b] fits with [d,a,e,b,c]. Fitting [d,c,b] with [d,a,e,b,c] creates the hamilton circuit
[d,a,e,b,c,d]. The weight of the hamilton circuit w[d,a,e,b,c,d] = w[d,a] + w[a,e] + w[e,b] + w[b,c] + w[c,d] = 7 + 10 + 5 + 9 + 6 = 37.
Also [d,a,e,b,c,d] = [d,a,e] + [e,b,c] + [d,c,b].
The hamilton circuit was obtained, and to know if it is the minimum circuit, checking is needed if any lower partial circuits which have been bypassed will form lesser weight hamilton circuits. To know which all are the lesser weight partial circuits, the next section ( ie:- Section #1.9 ) onwards shows the lesser weight partial circuits.

Section #1.8 (END)


Section #1.9 (BEGIN)

Group the partial circuits of the different vertices present in Section #1.7 into one group and then sort it. So first grouping the partial circuits, we obtain as below :-                  
                  
[a,d] + [a,e] = [d,a,e]          w[d,a,e] = 7+10 = 17
[a,d] + [a,c] = [d,a,c]          w[d,a,c] = 7+12 = 19
[a,d] + [a,b] = [d,a,b]          w[d,a,b] = 7+14 = 21
[a,e] + [a,c] = [e,a,c]          w[e,a,c] = 10+12 = 22
[a,e] + [a,b] = [e,a,b]          w[e,a,b] = 10+14 = 24
[a,c] + [a,b] = [c,a,b]          w[c,a,b] = 12+14 = 26
[b,e] + [b,c] = [e,b,c]          w[e,b,c] = 5+9 = 14
[b,e] + [b,d] = [e,b,d]          w[e,b,d] = 5+13 = 18
[b,e] + [b,a] = [e,b,a]          w[e,b,a] = 5+14 = 19
[b,c] + [b,d] = [c,b,d]          w[c,b,d] = 9+13 = 22
[b,c] + [b,a] = [c,b,a]          w[c,b,a] = 9+14 = 23
[b,d] + [b,a] = [d,b,a]          w[d,b,a] = 13+14 = 27
[c,d] + [c,e] = [d,c,e]          w[d,c,e] = 6+8 = 14
[c,d] + [c,b] = [d,c,b]          w[d,c,b] = 6+9 = 15
[c,e] + [c,b] = [e,c,b]          w[e,c,b] = 8+9 = 17
[c,d] + [c,a] = [d,c,a]          w[d,c,a] = 6+12 = 18
[c,e] + [c,a] = [e,c,a]          w[e,c,a] = 8+12 = 20
[c,b] + [c,a] = [b,c,a]          w[b,c,a] = 9+12 = 21
[d,c] + [d,a] = [c,d,a]          w[c,d,a] = 6+7 = 13
[d,c] + [d,e] = [c,d,e]          w[c,d,e] = 6+11 = 17
[d,a] + [d,e] = [a,d,e]          w[a,d,e] = 7+11 = 18
[d,c] + [d,b] = [c,d,b]          w[c,d,b] = 6+13 = 19
[d,a] + [d,b] = [a,d,b]          w[a,d,b] = 7+13 = 20
[d,e] + [d,b] = [e,d,b]          w[e,d,b] = 11+13 = 24
[e,b] + [e,c] = [b,e,c]          w[b,e,c] = 5+8 = 13
[e,b] + [e,a] = [b,e,a]          w[b,e,a] = 5+10 = 15
[e,b] + [e,d] = [b,e,d]          w[b,e,d] = 5+11 = 16
[e,c] + [e,a] = [c,e,a]          w[c,e,a] = 8+10 = 18
[e,c] + [e,d] = [c,e,d]          w[c,e,d] = 8+11 = 19
[e,a] + [e,d] = [b,e,c]          w[b,e,c] = 10+11 = 21

Section #1.9 (END)


Section #1.10 (BEGIN)

Now sort the group obtained in Section #1.9 according to their weights.
The sorted list of the different partial circuits are as follows.                  
                     
[d,c] + [d,a] = [c,d,a]          w[c,d,a] = 6+7 = 13   
[e,b] + [e,c] = [b,e,c]          w[b,e,c] = 5+8 = 13   
[b,e] + [b,c] = [e,b,c]          w[e,b,c] = 5+9 = 14    ->{D7}
[c,d] + [c,e] = [d,c,e]          w[d,c,e] = 6+8 = 14   
[c,d] + [c,b] = [d,c,b]          w[d,c,b] = 6+9 = 15     ->{D8}
[e,b] + [e,a] = [b,e,a]          w[b,e,a] = 5+10 = 15   
[e,b] + [e,d] = [b,e,d]          w[b,e,d] = 5+11 = 16   
[a,d] + [a,e] = [d,a,e]          w[d,a,e] = 7+10 = 17   ->{D6}
[c,e] + [c,b] = [e,c,b]          w[e,c,b] = 8+9 = 17   
[d,c] + [d,e] = [c,d,e]          w[c,d,e] = 6+11 = 17   
[b,e] + [b,d] = [e,b,d]          w[e,b,d] = 5+13 = 18   
[c,d] + [c,a] = [d,c,a]          w[d,c,a] = 6+12 = 18   
[d,a] + [d,e] = [a,d,e]          w[a,d,e] = 7+11 = 18   
[e,c] + [e,a] = [c,e,a]          w[c,e,a] = 8+10 = 18   
[a,d] + [a,c] = [d,a,c]          w[d,a,c] = 7+12 = 19   
[b,e] + [b,a] = [e,b,a]          w[e,b,a] = 5+14 = 19   
[d,c] + [d,b] = [c,d,b]          w[c,d,b] = 6+13 = 19   
[e,c] + [e,d] = [c,e,d]          w[c,e,d] = 8+11 = 19   
[c,e] + [c,a] = [e,c,a]          w[e,c,a] = 8+12 = 20   
[d,a] + [d,b] = [a,d,b]          w[a,d,b] = 7+13 = 20   
[a,d] + [a,b] = [d,a,b]          w[d,a,b] = 7+14 = 21   
[c,b] + [c,a] = [b,c,a]          w[b,c,a] = 9+12 = 21   
[e,a] + [e,d] = [b,e,c]          w[b,e,c] = 10+11 = 21   
[a,e] + [a,c] = [e,a,c]          w[e,a,c] = 10+12 = 22   
[b,c] + [b,d] = [c,b,d]          w[c,b,d] = 9+13 = 22   
[b,c] + [b,a] = [c,b,a]          w[c,b,a] = 9+14 = 23   
[a,e] + [a,b] = [e,a,b]          w[e,a,b] = 10+14 = 24   
[d,e] + [d,b] = [e,d,b]          w[e,d,b] = 11+13 = 24   
[a,c] + [a,b] = [c,a,b]          w[c,a,b] = 12+14 = 26   
[b,d] + [b,a] = [d,b,a]          w[d,b,a] = 13+14 = 27   

->D6. [d,a,e] was used in forming the hamilton circuit.
->D7. [e,b,c] was used in forming the hamilton circuit.
->D8. [d,c,b] was used in forming the hamilton circuit.

[c,d,a] , [b,e,c] , [d,c,e] , [b,e,a] and [b,e,d] was not used in forming the hamilton circuits even though they had lesser weights. So these partial circuits are taken individually and are used to form hamilton circuits and to find whether these hamilton circuits have lesser weight than the hamilton circuit found out earlier ( ie:- [d,a,e,b,c,d] was the hamilton circuit found out earlier ). ( The lesser weight partial circuits which were not used while forming the hamilton circuits for [c,d,a] , [b,e,c] , [d,c,e] , [b,e,a] and [b,e,d] need not be used for processing again. )

Now first [c,d,a] has to be taken as a necessary partial circuit and then the same process that occurred in Section #1.8 has to be done. 'Necessary partial circuit' means that [c,d,a] should be used as the first partial circuit for finding the hamilton circuit.
1) So first [c,d,a] is taken. Since hamilton circuit rule is not violated, [c,d,a] is taken.
2) Take [d,a,e] from Vertex a. [d,a,e] fits with [c,d,a]. So [d,a,e] is taken. The new partial circuit is [c,d,a,e].
3) Take [e,b,c] from Vertex b. [e,b,c] fits with [c,d,a,e]. So [e,b,c] is taken. The new hamilton circuit formed is [c,d,a,e,b,c]. The weight of the hamilton circuit w[c,d,a,e,b,c] = w[c,d] + w[d,a] + w[a,e] + w[e,b] + w[b,c] = 6+7+10+5+9=37
Therefore [c,d,a,e,b,c] = [c,d,a] + [d,a,e] + [e,b,c].
w[c,d,a,e,b,c] = 37.

Now [b,e,c] has to be taken as a necessary partial circuit and then the same process that occurred in Section #1.8 has to be done.
1) First [b,e,c] is taken. Since hamilton circuit rule is not violated, [b,e,c] is taken.
2) Take [d,a,e] from Vertex a. [d,a,e] does not fit with [b,e,c]. So take the next partial circuit from Vertex a. Take [d,a,c] from Vertex a. [d,a,c] fits with [b,e,c]. So the new partial circuit is [b,e,c,a,d]. Since a partial circuit from Vertex a which fits is got, then a partial circuit from the next vertex is got.
3) Take [e,b,c] from Vertex b. [e,b,c] does not fit with [b,e,c,a,d]. So take [e,b,d] from Vertex b. [e,b,d] fits with [b,e,c,a,d]. Fitting [e,b,d] with [b,e,c,a,d] creates the hamilton circuit [b,e,c,a,d,b]. The weight of the hamilton circuit w[b,e,c,a,d,b] = w[b,e] + w[e,c] + w[c,a] + w[a,d] + w[d,b] = 5+8+12+7+13=45
Therefore [b,e,c,a,d,b] = [b,e,c] + [d,a,c] + [e,b,d].
w[b,e,c,a,d,b] = 45.

Now [d,c,e] has to be taken as a necessary partial circuit and then the same process that occurred in Section #1.8 has to be done.
1) First [d,c,e] is taken. Since hamilton circuit rule is not violated, [d,c,e] is taken.
2) Take [d,a,e] from Vertex a. [d,a,e] does not fit with [d,c,e]. So take [d,a,c] from Vertex a. Here [d,a,c] can replace [d,c] of [d,c,e], since according to the properties of joining of partial circuits, it is allowed.  So
[d,a,c] fits with [d,c,e]. So the new partial circuit is [d,a,c,e].
3) Take [e,b,c] from Vertex b. Here [e,b,c] can replace [c,e] of [d,a,c,e], since according to the properties of joining of partial circuits, it is allowed. So [e,b,c] fits with [d,a,c,e]. So the new partial circuit is
[d,a,c,b,e].
4) Take [d,c,e] from Vertex c. [d,c,e] does not fit with [d,a,c,b,e]. So also [d,c,b] , [e,c,b] , [d,c,a] and
[e,c,a] from vertex c does not fit with [d,a,c,b,e]. [b,c,a] from vertex c is already present in [d,a,c,b,e]. So all partial circuits from Vertex c are exhausted. So go to the next vertex ie:- Vertex d.
5) Take [c,d,a] from Vertex d. [c,d,a] does not fit with [d,a,c,b,e]. Take [c,d,e] from vertex d. [c,d,e] does not fit with [d,a,c,b,e]. Take [a,d,e] from Vertex d. [a,d,e] fits with [d,a,c,b,e] to create the hamilton circuit
[d,a,c,b,e,d]. The weight of the hamilton circuit w[d,a,c,b,e,d] = w[d,a] + w[a,c] + w[c,b] + w[b,e] + w[e,d] = 44
So [d,a,c,b,e,d] = [d,c,e] + [d,a,c] + [e,b,c] + [a,d,e]
w[d,a,c,b,e,d] = 44.

Now take [b,e,a] as a necessary partial circuit and then the same process that occurred in Section #1.8 has to be done.
1) First [b,e,a] is taken. Since hamilton circuit rule is not violated, [b,e,a] is taken.
2) Take [d,a,e] from Vertex a. [d,a,e] fits with [b,e,a]. So take [d,a,e] from Vertex a. The new partial circuit is [b,e,a,d].
3) Take [e,b,c] from Vertex b. [e,b,c] fits with [b,e,a,d]. The new partial circuit is [c,b,e,a,d].
4) Take [d,c,e] from Vertex c. [d,c,e] does not fit with [c,b,e,a,d]. Take [d,c,b] from Vertex c. [d,c,b] fits with [c,b,e,a,d] to form the hamilton circuit [c,b,e,a,d,c].
The hamilton circuit for [b,e,a] is :-
[b,e,a] + [d,a,e] + [e,b,c] + [d,c,b] = [b,e,a,d,c,b]
w[b,e,a,d,c,b] = 37

In the same way that the hamilton circuit has been obtained for [c,d,a] , [b,e,c] , [d,c,e] and [b,e,a] , it is also done here for [b,e,d]. The result is only written here.
Now taking [b,e,d] as a necessary partial circuit. The hamilton circuit for [b,e,d] is :-
[b,e,d] + [d,a,e] + [e,b,c] + [d,c,b] = [b,e,a,d,c,b].
w[b,e,a,d,c,b] = 37


The lowest weight for a hamilton circuit is 37 among the hamilton circuits taken for the partial circuits of [c,d,a] , [b,e,c] , [d,c,e] , [b,e,a] and [b,e,d]. Also the lowest weight of the hamilton circuit obtained in Section #1.8 is also 37. So the hamilton circuit obtained in Section #1.8 or in Section #1.10 with lowest weight of "37" is taken as the minimum weight hamilton circuit.

Section #1.10 (END)


Example 2
This example is taken from "Section 3.4" of the Book "A First Look at Graph Theory" by John Clark and Derek Allan Holton. The solution for the example is got in the process described from Section #2.1 to Section #2.8. "Example 2" is solved in the same way as "Example 1" was solved.

Section #2.1 (BEGIN)
   
Vertex b   
w[b,c] = 10
w[b,m] = 11
w[b,r] = 11
w[b,s] = 6
w[b,v] = 10
   
Vertex v   
w[v,b] = 10
w[v,c] = 20
w[v,m] = 19
w[v,r] = 20
w[v,s] = 11
   
Vertex s   
w[s,v] = 11
w[s,b] = 6
w[s,c] = 15
w[s,m] = 15
w[s,r] = 15
   
Vertex r   
w[r,s] = 15
w[r,v] = 20
w[r,b] = 11
w[r,c] = 15
w[r,m] = 10
   
Vertex m   
w[m,r] = 10
w[m,s] = 15
w[m,v] = 19
w[m,b] = 11
w[m,c] = 17
   
Vertex c   
w[c,m] = 17
w[c,r] = 15
w[c,s] = 15
w[c,v] = 20
w[c,b] = 10

   In this section, the weights of the different edges connected to the different vertices of a 6 vertex graph is shown.

Section #2.1 (END)

Section #2.2 (BEGIN)

In this section a combination of the edges connected to a particular vertex is taken. For eg:- there are five edges connected to vertex b. So the number of combinations of the five edges connected to 'vertex b' by taking two edges at a time is C(5,2) = 5!/((5-2)!*2!) = 10.
Also the weights of the partial circuits of a particular vertex are also written to the right of the partial
circuits.


Vertex b                  
[b,c] + [b,m] = [c,b,m]          w[c,b,m] = 10+11 = 21
[b,c] + [b,r] = [c,b,r]          w[c,b,r] = 10+11 = 21
[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6  = 16
[b,c] + [b,v] = [c,b,v]          w[c,b,v] = 10+10 = 20
[b,m] + [b,r] = [m,b,r]          w[m,b,r] = 11+11 = 22
[b,m] + [b,s] = [m,b,s]          w[m,b,s] = 11+6 = 17
[b,m] + [b,v] = [m,b,v]          w[m,b,v] = 11+10 = 21
[b,r] + [b,s] = [r,b,s]          w[r,b,s] = 11+6 = 17
[b,r] + [b,v] = [r,b,v]          w[r,b,v] = 11+10 = 21
[b,s] + [b,v] = [s,b,v]          w[s,b,v] = 6+10 = 16
                  
Vertex v                  
[v,b] + [v,c] = [b,v,c]          w[b,v,c] = 10+20 = 30
[v,b] + [v,m] = [b,v,m]          w[b,v,m] = 10+19 = 29
[v,b] + [v,r] = [b,v,r]          w[b,v,r] = 10+20 = 30
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21
[v,c] + [v,m] = [c,v,m]          w[c,v,m] = 20+19 = 39
[v,c] + [v,r] = [c,v,r]          w[c,v,r] = 20+20 = 40
[v,c] + [v,s] = [c,v,s]          w[c,v,s] = 20+11 = 31
[v,m] + [v,r] = [m,v,r]          w[m,v,r] = 19+20 = 39
[v,m] + [v,s] = [m,v,s]          w[m,v,s] = 19+11 = 30
[v,r] + [v,s] = [r,v,s]          w[r,v,s] = 20+11 = 31
                  
Vertex s                  
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17
[s,v] + [s,c] = [v,s,c]          w[v,s,c] = 11+15 = 26
[s,v] + [s,m] = [v,s,m]          w[v,s,m] = 11+15 = 26
[s,v] + [s,r] = [v,s,r]          w[v,s,r] = 11+15 = 26
[s,b] + [s,c] = [b,s,c]          w[b,s,c] = 6+15 = 21
[s,b] + [s,m] = [b,s,m]          w[b,s,m] = 6+15 = 21
[s,b] + [s,r] = [b,s,r]          w[b,s,r] = 6+15 = 21
[s,c] + [s,m] = [c,s,m]          w[c,s,m] = 15+15 = 30
[s,c] + [s,r] = [c,s,r]          w[c,s,r] = 15+15 = 30
[s,m] + [s,r] = [m,s,r]          w[m,s,r] = 15+15 = 30
                  
Vertex r                  
[r,s] + [r,v] = [s,r,v]          w[s,r,v] = 15+20 = 35
[r,s] + [r,b] = [s,r,b]          w[s,r,b] = 15+11 = 26
[r,s] + [r,c] = [s,r,c]          w[s,r,c] = 15+15 = 30
[r,s] + [r,m] = [s,r,m]          w[s,r,m] = 15+10 = 25
[r,v] + [r,b] = [v,r,b]          w[v,r,b] = 20+11 = 31
[r,v] + [r,c] = [v,r,c]          w[v,r,c] = 20+15 = 35
[r,v] + [r,m] = [v,r,m]          w[v,r,m] = 20+10 = 30
[r,b] + [r,c] = [b,r,c]          w[b,r,c] = 11+15 = 26
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21
[r,c] + [r,m] = [c,r,m]          w[c,r,m] = 15+10 = 25
                  
Vertex m                  
[m,r] + [m,s] = [r,m,s]          w[r,m,s] = 10+15 = 25
[m,r] + [m,v] = [r,m,v]          w[r,m,v] = 10+19 = 29
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21
[m,r] + [m,c] = [r,m,c]          w[r,m,c] = 10+17 = 27
[m,s] + [m,v] = [s,m,v]          w[s,m,v] = 15+19 = 34
[m,s] + [m,b] = [s,m,b]          w[s,m,b] = 15+11 = 26
[m,s] + [m,c] = [s,m,c]          w[s,m,c] = 15+17 = 32
[m,v] + [m,b] = [v,m,b]          w[v,m,b] = 19+11 = 30
[m,v] + [m,c] = [v,m,c]          w[v,m,c] = 19+17 = 36
[m,b] + [m,c] = [b,m,c]          w[b,m,c] = 11+17 = 28
                  
Vertex c                  
[c,m] + [c,r] = [m,c,r]          w[m,c,r] = 17+15 = 32
[c,m] + [c,s] = [m,c,s]          w[m,c,s] = 17+15 = 32
[c,m] + [c,v] = [m,c,v]          w[m,c,v] = 17+20 = 37
[c,m] + [c,b] = [m,c,b]          w[m,c,b] = 17+10 = 27
[c,r] + [c,s] = [r,c,s]          w[r,c,s] = 15+15 = 30
[c,r] + [c,v] = [r,c,v]          w[r,c,v] = 15+20 = 35
[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25
[c,s] + [c,v] = [s,c,v]          w[s,c,v] = 15+20 = 35
[c,s] + [c,b] = [s,c,b]          w[s,c,b] = 15+10 = 25
[c,v] + [c,b] = [v,c,b]          w[v,c,b] = 20+10 = 30

Section #2.2 (END)


Section #2.3 (BEGIN)

In this section, the partial circuits under each vertex are sorted in 'Ascending order' according to their weights.

Vertex b ( sorted )                  
[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16
[b,s] + [b,v] = [s,b,v]          w[s,b,v] = 6+10 = 16
[b,m] + [b,s] = [m,b,s]          w[m,b,s] = 11+6 = 17
[b,r] + [b,s] = [r,b,s]          w[r,b,s] = 11+6 = 17
[b,c] + [b,v] = [c,b,v]          w[c,b,v] = 10+10 = 20
[b,c] + [b,m] = [c,b,m]          w[c,b,m] = 10+11 = 21
[b,c] + [b,r] = [c,b,r]          w[c,b,r] = 10+11 = 21
[b,m] + [b,v] = [m,b,v]          w[m,b,v] = 11+10 = 21
[b,r] + [b,v] = [r,b,v]          w[r,b,v] = 11+10 = 21
[b,m] + [b,r] = [m,b,r]          w[m,b,r] = 11+11 = 22
                  
Vertex v ( sorted )                  
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21
[v,b] + [v,m] = [b,v,m]          w[b,v,m] = 10+19 = 29
[v,b] + [v,c] = [b,v,c]          w[b,v,c] = 10+20 = 30
[v,b] + [v,r] = [b,v,r]          w[b,v,r] = 10+20 = 30
[v,m] + [v,s] = [m,v,s]          w[m,v,s] = 19+11 = 30
[v,c] + [v,s] = [c,v,s]          w[c,v,s] = 20+11 = 31
[v,r] + [v,s] = [r,v,s]          w[r,v,s] = 20+11 = 31
[v,c] + [v,m] = [c,v,m]          w[c,v,m] = 20+19 = 39
[v,m] + [v,r] = [m,v,r]          w[m,v,r] = 19+20 = 39
[v,c] + [v,r] = [c,v,r]          w[c,v,r] = 20+20 = 40
                  
Vertex s (sorted)                  
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17
[s,b] + [s,c] = [b,s,c]          w[b,s,c] = 6+15 = 21
[s,b] + [s,m] = [b,s,m]          w[b,s,m] = 6+15 = 21
[s,b] + [s,r] = [b,s,r]          w[b,s,r] = 6+15 = 21
[s,v] + [s,c] = [v,s,c]          w[v,s,c] = 11+15 = 26
[s,v] + [s,m] = [v,s,m]          w[v,s,m] = 11+15 = 26
[s,v] + [s,r] = [v,s,r]          w[v,s,r] = 11+15 = 26
[s,c] + [s,m] = [c,s,m]          w[c,s,m] = 15+15 = 30
[s,c] + [s,r] = [c,s,r]          w[c,s,r] = 15+15 = 30
[s,m] + [s,r] = [m,s,r]          w[m,s,r] = 15+15 = 30
                  
Vertex r ( sorted )                  
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21
[r,s] + [r,m] = [s,r,m]          w[s,r,m] = 15+10 = 25
[r,c] + [r,m] = [c,r,m]          w[c,r,m] = 15+10 = 25
[r,s] + [r,b] = [s,r,b]          w[s,r,b] = 15+11 = 26
[r,b] + [r,c] = [b,r,c]          w[b,r,c] = 11+15 = 26
[r,s] + [r,c] = [s,r,c]          w[s,r,c] = 15+15 = 30
[r,v] + [r,m] = [v,r,m]          w[v,r,m] = 20+10 = 30
[r,v] + [r,b] = [v,r,b]          w[v,r,b] = 20+11 = 31
[r,s] + [r,v] = [s,r,v]          w[s,r,v] = 15+20 = 35
[r,v] + [r,c] = [v,r,c]          w[v,r,c] = 20+15 = 35
                  
Vertex m ( sorted )                  
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21
[m,r] + [m,s] = [r,m,s]          w[r,m,s] = 10+15 = 25
[m,s] + [m,b] = [s,m,b]          w[s,m,b] = 15+11 = 26
[m,r] + [m,c] = [r,m,c]          w[r,m,c] = 10+17 = 27
[m,b] + [m,c] = [b,m,c]          w[b,m,c] = 11+17 = 28
[m,r] + [m,v] = [r,m,v]          w[r,m,v] = 10+19 = 29
[m,v] + [m,b] = [v,m,b]          w[v,m,b] = 19+11 = 30
[m,s] + [m,c] = [s,m,c]          w[s,m,c] = 15+17 = 32
[m,s] + [m,v] = [s,m,v]          w[s,m,v] = 15+19 = 34
[m,v] + [m,c] = [v,m,c]          w[v,m,c] = 19+17 = 36
                  
Vertex c ( sorted )                  
[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25
[c,s] + [c,b] = [s,c,b]          w[s,c,b] = 15+10 = 25
[c,m] + [c,b] = [m,c,b]          w[m,c,b] = 17+10 = 27
[c,r] + [c,s] = [r,c,s]          w[r,c,s] = 15+15 = 30
[c,v] + [c,b] = [v,c,b]          w[v,c,b] = 20+10 = 30
[c,m] + [c,r] = [m,c,r]          w[m,c,r] = 17+15 = 32
[c,m] + [c,s] = [m,c,s]          w[m,c,s] = 17+15 = 32
[c,r] + [c,v] = [r,c,v]          w[r,c,v] = 15+20 = 35
[c,s] + [c,v] = [s,c,v]          w[s,c,v] = 15+20 = 35
[c,m] + [c,v] = [m,c,v]          w[m,c,v] = 17+20 = 37

Section #2.3 (END)

Section #2.4 (BEGIN)

In this section, the partial circuit with the lowest weight under each vertex is taken individually and written

below.

[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16      ->{D9}   
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21    ->{D10}   
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17      
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21      
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21      
[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25   

->D9. Here [c,b,s] is the lowest weight combination taken from Vertex b.
->D10. Here [b,v,s] is the lowest weight combination taken from Vertex v.

Section #2.4 (END)


Section #2.5 (BEGIN)

In this section, the partial circuits written in Section #2.4 are sorted in 'Descending order' of their weights and

written here.

[c,r] + [c,b] = [r,c,b]     w[r,c,b] = 15+10 = 25  ( Vertex c )   ->{D11}
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21     ( Vertex v )   
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21     ( Vertex r )
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21     ( Vertex m )
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17      ( Vertex s )   
[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16      ( Vertex b )   

->D11. [r,c,b] is a partial circuit having the highest weight in the group in this section.

Section #2.5 (END)


Section #2.6 (BEGIN)

In this section, in order to choose a partial circuit ( or the order of which vertex to choose from ) is given by the order in Section #2.5. So the order is as follows ie:- vertex c , vertex v , vertex r , vertex m , vertex s , vertex b.

Vertex c ( sorted )                  
[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25
[c,s] + [c,b] = [s,c,b]          w[s,c,b] = 15+10 = 25
[c,m] + [c,b] = [m,c,b]          w[m,c,b] = 17+10 = 27
[c,r] + [c,s] = [r,c,s]          w[r,c,s] = 15+15 = 30
[c,v] + [c,b] = [v,c,b]          w[v,c,b] = 20+10 = 30
[c,m] + [c,r] = [m,c,r]          w[m,c,r] = 17+15 = 32
[c,m] + [c,s] = [m,c,s]          w[m,c,s] = 17+15 = 32
[c,r] + [c,v] = [r,c,v]          w[r,c,v] = 15+20 = 35
[c,s] + [c,v] = [s,c,v]          w[s,c,v] = 15+20 = 35
[c,m] + [c,v] = [m,c,v]          w[m,c,v] = 17+20 = 37
                  
Vertex v ( sorted )                  
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21
[v,b] + [v,m] = [b,v,m]          w[b,v,m] = 10+19 = 29
[v,b] + [v,c] = [b,v,c]          w[b,v,c] = 10+20 = 30
[v,b] + [v,r] = [b,v,r]          w[b,v,r] = 10+20 = 30
[v,m] + [v,s] = [m,v,s]          w[m,v,s] = 19+11 = 30
[v,c] + [v,s] = [c,v,s]          w[c,v,s] = 20+11 = 31
[v,r] + [v,s] = [r,v,s]          w[r,v,s] = 20+11 = 31
[v,c] + [v,m] = [c,v,m]          w[c,v,m] = 20+19 = 39
[v,m] + [v,r] = [m,v,r]          w[m,v,r] = 19+20 = 39
[v,c] + [v,r] = [c,v,r]          w[c,v,r] = 20+20 = 40
                  
Vertex r ( sorted )                  
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21
[r,s] + [r,m] = [s,r,m]          w[s,r,m] = 15+10 = 25
[r,c] + [r,m] = [c,r,m]          w[c,r,m] = 15+10 = 25
[r,s] + [r,b] = [s,r,b]          w[s,r,b] = 15+11 = 26
[r,b] + [r,c] = [b,r,c]          w[b,r,c] = 11+15 = 26
[r,s] + [r,c] = [s,r,c]          w[s,r,c] = 15+15 = 30
[r,v] + [r,m] = [v,r,m]          w[v,r,m] = 20+10 = 30
[r,v] + [r,b] = [v,r,b]          w[v,r,b] = 20+11 = 31
[r,s] + [r,v] = [s,r,v]          w[s,r,v] = 15+20 = 35
[r,v] + [r,c] = [v,r,c]          w[v,r,c] = 20+15 = 35
                  
Vertex m ( sorted )                  
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21
[m,r] + [m,s] = [r,m,s]          w[r,m,s] = 10+15 = 25
[m,s] + [m,b] = [s,m,b]          w[s,m,b] = 15+11 = 26
[m,r] + [m,c] = [r,m,c]          w[r,m,c] = 10+17 = 27
[m,b] + [m,c] = [b,m,c]          w[b,m,c] = 11+17 = 28
[m,r] + [m,v] = [r,m,v]          w[r,m,v] = 10+19 = 29
[m,v] + [m,b] = [v,m,b]          w[v,m,b] = 19+11 = 30
[m,s] + [m,c] = [s,m,c]          w[s,m,c] = 15+17 = 32
[m,s] + [m,v] = [s,m,v]          w[s,m,v] = 15+19 = 34
[m,v] + [m,c] = [v,m,c]          w[v,m,c] = 19+17 = 36
                  
Vertex s (sorted)                  
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17
[s,b] + [s,c] = [b,s,c]          w[b,s,c] = 6+15 = 21
[s,b] + [s,m] = [b,s,m]          w[b,s,m] = 6+15 = 21
[s,b] + [s,r] = [b,s,r]          w[b,s,r] = 6+15 = 21
[s,v] + [s,c] = [v,s,c]          w[v,s,c] = 11+15 = 26
[s,v] + [s,m] = [v,s,m]          w[v,s,m] = 11+15 = 26
[s,v] + [s,r] = [v,s,r]          w[v,s,r] = 11+15 = 26
[s,c] + [s,m] = [c,s,m]          w[c,s,m] = 15+15 = 30
[s,c] + [s,r] = [c,s,r]          w[c,s,r] = 15+15 = 30
[s,m] + [s,r] = [m,s,r]          w[m,s,r] = 15+15 = 30
                  
Vertex b ( sorted )                  
[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16
[b,s] + [b,v] = [s,b,v]          w[s,b,v] = 6+10 = 16
[b,m] + [b,s] = [m,b,s]          w[m,b,s] = 11+6 = 17
[b,r] + [b,s] = [r,b,s]          w[r,b,s] = 11+6 = 17
[b,c] + [b,v] = [c,b,v]          w[c,b,v] = 10+10 = 20
[b,c] + [b,m] = [c,b,m]          w[c,b,m] = 10+11 = 21
[b,c] + [b,r] = [c,b,r]          w[c,b,r] = 10+11 = 21
[b,m] + [b,v] = [m,b,v]          w[m,b,v] = 11+10 = 21
[b,r] + [b,v] = [r,b,v]          w[r,b,v] = 11+10 = 21
[b,m] + [b,r] = [m,b,r]          w[m,b,r] = 11+11 = 22

Section #2.6 (END)

Section #2.7 (BEGIN)

Now from Section #2.6, take a partial circuit from each vertex ( the order of the vertex to be taken, should be the same order in which the vertices are written in Section #2.6 ) and join them together in order to form a hamilton circuit. The process is as follows :-

1) Take [r,c,b] from Vertex c. Since hamilton circuit rule is not violated, [r,c,b] is taken.
2) Take [b,v,s] from Vertex v. [b,v,s] fits with [r,c,b]. So [b,v,s] is also taken. The new partial circuit is
[r,c,b,v,s].
3) Take [b,r,m] from Vertex r. [b,r,m] does not fit with [r,c,b,v,s]. So the next step is not to go to the next
vertex , but to take another partial circuit from the same vertex to see if it fits with [r,c,b,v,s]. So take
[s,r,m] from Vertex r. [s,r,m] does not fit with [r,c,b,v,s]. So take the next partial circuit from the same vertex to see if fits with [r,c,b,v,s]. So take [c,r,m] from Vertex r. [c,r,m] fits with [r,c,b,v,s]. Fitting [c,r,m] with [r,c,b,v,s] gives the partial circuit [m,r,c,b,v,s].
4) Take [r,m,b] from Vertex m. [r,m,b] does not fit with [m,r,c,b,v,s]. Take [r,m,s] from vertex m. [r,m,s] fits with [m,r,c,b,v,s] to create the hamilton circuit [r,c,b,v,s,m,r]. The weight of the hamilton circuit w
[r,c,b,v,s,m,r] = w[r,c] + w[c,b] +w[b,v] + w[v,s] + w[s,m] + w[m,r] = 15 + 10 + 10+ 11+ 15 + 10 = 71.
So [r,c,b,v,s,m,r] = [r,c,b] + [b,v,s] + [c,r,m] + [r,m,s].
w[r,c,b,v,s,m,r] = 71
The hamilton circuit was obtained, and to know if it is the minimum weight hamilton circuit, checking is needed to see if any lower partial circuits which have been bypassed will form lesser weight hamilton circuits. To know which all are the lesser weight partial circuits, the next section ( ie:- Section #2.8 ) onwards shows the lesser weight partial circuits.

Section #2.7 (END)


Section #2.8 (BEGIN)

Group the partial circuits of the different vertices present in Section #2.6 into one group and then sort it. So first grouping the partial circuits, we obtain as below :-   

[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25
[c,s] + [c,b] = [s,c,b]          w[s,c,b] = 15+10 = 25
[c,m] + [c,b] = [m,c,b]          w[m,c,b] = 17+10 = 27
[c,r] + [c,s] = [r,c,s]          w[r,c,s] = 15+15 = 30
[c,v] + [c,b] = [v,c,b]          w[v,c,b] = 20+10 = 30
[c,m] + [c,r] = [m,c,r]          w[m,c,r] = 17+15 = 32
[c,m] + [c,s] = [m,c,s]          w[m,c,s] = 17+15 = 32
[c,r] + [c,v] = [r,c,v]          w[r,c,v] = 15+20 = 35
[c,s] + [c,v] = [s,c,v]          w[s,c,v] = 15+20 = 35
[c,m] + [c,v] = [m,c,v]          w[m,c,v] = 17+20 = 37
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21
[v,b] + [v,m] = [b,v,m]          w[b,v,m] = 10+19 = 29
[v,b] + [v,c] = [b,v,c]          w[b,v,c] = 10+20 = 30
[v,b] + [v,r] = [b,v,r]          w[b,v,r] = 10+20 = 30
[v,m] + [v,s] = [m,v,s]          w[m,v,s] = 19+11 = 30
[v,c] + [v,s] = [c,v,s]          w[c,v,s] = 20+11 = 31
[v,r] + [v,s] = [r,v,s]          w[r,v,s] = 20+11 = 31
[v,c] + [v,m] = [c,v,m]          w[c,v,m] = 20+19 = 39
[v,m] + [v,r] = [m,v,r]          w[m,v,r] = 19+20 = 39
[v,c] + [v,r] = [c,v,r]          w[c,v,r] = 20+20 = 40
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21
[r,s] + [r,m] = [s,r,m]          w[s,r,m] = 15+10 = 25
[r,c] + [r,m] = [c,r,m]          w[c,r,m] = 15+10 = 25
[r,s] + [r,b] = [s,r,b]          w[s,r,b] = 15+11 = 26
[r,b] + [r,c] = [b,r,c]          w[b,r,c] = 11+15 = 26
[r,s] + [r,c] = [s,r,c]          w[s,r,c] = 15+15 = 30
[r,v] + [r,m] = [v,r,m]          w[v,r,m] = 20+10 = 30
[r,v] + [r,b] = [v,r,b]          w[v,r,b] = 20+11 = 31
[r,s] + [r,v] = [s,r,v]          w[s,r,v] = 15+20 = 35
[r,v] + [r,c] = [v,r,c]          w[v,r,c] = 20+15 = 35
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21
[m,r] + [m,s] = [r,m,s]          w[r,m,s] = 10+15 = 25
[m,s] + [m,b] = [s,m,b]          w[s,m,b] = 15+11 = 26
[m,r] + [m,c] = [r,m,c]          w[r,m,c] = 10+17 = 27
[m,b] + [m,c] = [b,m,c]          w[b,m,c] = 11+17 = 28
[m,r] + [m,v] = [r,m,v]          w[r,m,v] = 10+19 = 29
[m,v] + [m,b] = [v,m,b]          w[v,m,b] = 19+11 = 30
[m,s] + [m,c] = [s,m,c]          w[s,m,c] = 15+17 = 32
[m,s] + [m,v] = [s,m,v]          w[s,m,v] = 15+19 = 34
[m,v] + [m,c] = [v,m,c]          w[v,m,c] = 19+17 = 36
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17
[s,b] + [s,c] = [b,s,c]          w[b,s,c] = 6+15 = 21
[s,b] + [s,m] = [b,s,m]          w[b,s,m] = 6+15 = 21
[s,b] + [s,r] = [b,s,r]          w[b,s,r] = 6+15 = 21
[s,v] + [s,c] = [v,s,c]          w[v,s,c] = 11+15 = 26
[s,v] + [s,m] = [v,s,m]          w[v,s,m] = 11+15 = 26
[s,v] + [s,r] = [v,s,r]          w[v,s,r] = 11+15 = 26
[s,c] + [s,m] = [c,s,m]          w[c,s,m] = 15+15 = 30
[s,c] + [s,r] = [c,s,r]          w[c,s,r] = 15+15 = 30
[s,m] + [s,r] = [m,s,r]          w[m,s,r] = 15+15 = 30
[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16
[b,s] + [b,v] = [s,b,v]          w[s,b,v] = 6+10 = 16
[b,m] + [b,s] = [m,b,s]          w[m,b,s] = 11+6 = 17
[b,r] + [b,s] = [r,b,s]          w[r,b,s] = 11+6 = 17
[b,c] + [b,v] = [c,b,v]          w[c,b,v] = 10+10 = 20
[b,c] + [b,m] = [c,b,m]          w[c,b,m] = 10+11 = 21
[b,c] + [b,r] = [c,b,r]          w[c,b,r] = 10+11 = 21
[b,m] + [b,v] = [m,b,v]          w[m,b,v] = 11+10 = 21
[b,r] + [b,v] = [r,b,v]          w[r,b,v] = 11+10 = 21
[b,m] + [b,r] = [m,b,r]          w[m,b,r] = 11+11 = 22


Section #2.8 (END)



Section #2.9 (BEGIN)

Now sort the group obtained in Section #2.8 according to their weights.
The sorted list of the different partial circuits are as follows.   


[b,c] + [b,s] = [c,b,s]          w[c,b,s] = 10+6 = 16
[b,s] + [b,v] = [s,b,v]          w[s,b,v] = 6+10 = 16
[s,v] + [s,b] = [v,s,b]          w[v,s,b] = 11+6 = 17
[b,m] + [b,s] = [m,b,s]          w[m,b,s] = 11+6 = 17
[b,r] + [b,s] = [r,b,s]          w[r,b,s] = 11+6 = 17
[b,c] + [b,v] = [c,b,v]          w[c,b,v] = 10+10 = 20
[v,b] + [v,s] = [b,v,s]          w[b,v,s] = 10+11 = 21    ->{D14}
[r,b] + [r,m] = [b,r,m]          w[b,r,m] = 11+10 = 21
[m,r] + [m,b] = [r,m,b]          w[r,m,b] = 10+11 = 21
[s,b] + [s,c] = [b,s,c]          w[b,s,c] = 6+15 = 21
[s,b] + [s,m] = [b,s,m]          w[b,s,m] = 6+15 = 21
[s,b] + [s,r] = [b,s,r]          w[b,s,r] = 6+15 = 21
[b,c] + [b,m] = [c,b,m]          w[c,b,m] = 10+11 = 21
[b,c] + [b,r] = [c,b,r]          w[c,b,r] = 10+11 = 21
[b,m] + [b,v] = [m,b,v]          w[m,b,v] = 11+10 = 21
[b,r] + [b,v] = [r,b,v]          w[r,b,v] = 11+10 = 21
[b,m] + [b,r] = [m,b,r]          w[m,b,r] = 11+11 = 22
[c,r] + [c,b] = [r,c,b]          w[r,c,b] = 15+10 = 25    ->{D12}
[c,s] + [c,b] = [s,c,b]          w[s,c,b] = 15+10 = 25
[r,s] + [r,m] = [s,r,m]          w[s,r,m] = 15+10 = 25
[r,c] + [r,m] = [c,r,m]          w[c,r,m] = 15+10 = 25    ->{D15}
[m,r] + [m,s] = [r,m,s]          w[r,m,s] = 10+15 = 25    ->{D16}
[r,s] + [r,b] = [s,r,b]          w[s,r,b] = 15+11 = 26
[r,b] + [r,c] = [b,r,c]          w[b,r,c] = 11+15 = 26
[m,s] + [m,b] = [s,m,b]          w[s,m,b] = 15+11 = 26
[s,v] + [s,c] = [v,s,c]          w[v,s,c] = 11+15 = 26
[s,v] + [s,m] = [v,s,m]          w[v,s,m] = 11+15 = 26
[s,v] + [s,r] = [v,s,r]          w[v,s,r] = 11+15 = 26
[c,m] + [c,b] = [m,c,b]          w[m,c,b] = 17+10 = 27
[m,r] + [m,c] = [r,m,c]          w[r,m,c] = 10+17 = 27
[m,b] + [m,c] = [b,m,c]          w[b,m,c] = 11+17 = 28
[v,b] + [v,m] = [b,v,m]          w[b,v,m] = 10+19 = 29
[m,r] + [m,v] = [r,m,v]          w[r,m,v] = 10+19 = 29
[c,r] + [c,s] = [r,c,s]          w[r,c,s] = 15+15 = 30
[c,v] + [c,b] = [v,c,b]          w[v,c,b] = 20+10 = 30
[v,b] + [v,c] = [b,v,c]          w[b,v,c] = 10+20 = 30
[v,b] + [v,r] = [b,v,r]          w[b,v,r] = 10+20 = 30
[v,m] + [v,s] = [m,v,s]          w[m,v,s] = 19+11 = 30
[r,s] + [r,c] = [s,r,c]          w[s,r,c] = 15+15 = 30
[r,v] + [r,m] = [v,r,m]          w[v,r,m] = 20+10 = 30
[m,v] + [m,b] = [v,m,b]          w[v,m,b] = 19+11 = 30
[s,c] + [s,m] = [c,s,m]          w[c,s,m] = 15+15 = 30
[s,c] + [s,r] = [c,s,r]          w[c,s,r] = 15+15 = 30
[s,m] + [s,r] = [m,s,r]          w[m,s,r] = 15+15 = 30
[v,c] + [v,s] = [c,v,s]          w[c,v,s] = 20+11 = 31
[v,r] + [v,s] = [r,v,s]          w[r,v,s] = 20+11 = 31
[r,v] + [r,b] = [v,r,b]          w[v,r,b] = 20+11 = 31
[c,m] + [c,r] = [m,c,r]          w[m,c,r] = 17+15 = 32
[c,m] + [c,s] = [m,c,s]          w[m,c,s] = 17+15 = 32
[m,s] + [m,c] = [s,m,c]          w[s,m,c] = 15+17 = 32
[m,s] + [m,v] = [s,m,v]          w[s,m,v] = 15+19 = 34
[c,r] + [c,v] = [r,c,v]          w[r,c,v] = 15+20 = 35
[c,s] + [c,v] = [s,c,v]          w[s,c,v] = 15+20 = 35
[r,s] + [r,v] = [s,r,v]          w[s,r,v] = 15+20 = 35
[r,v] + [r,c] = [v,r,c]          w[v,r,c] = 20+15 = 35
[m,v] + [m,c] = [v,m,c]          w[v,m,c] = 19+17 = 36
[c,m] + [c,v] = [m,c,v]          w[m,c,v] = 17+20 = 37
[v,c] + [v,m] = [c,v,m]          w[c,v,m] = 20+19 = 39
[v,m] + [v,r] = [m,v,r]          w[m,v,r] = 19+20 = 39
[v,c] + [v,r] = [c,v,r]          w[c,v,r] = 20+20 = 40

->D12. [r,c,b] was used in forming the hamilton circuit.
->D14. [b,v,s] was used in forming the hamilton circuit.
->D15. [c,r,m] was used in forming the hamilton circuit.
->D16. [r,m,s] was used in forming the hamilton circuit.

[c,b,s] , [s,b,v] , [v,s,b] , [m,b,s] , [r,b,s] , [c,b,v] , [b,r,m] , [r,m,b] , [b,s,c] , [b,s,m] , [b,s,r] ,
[c,b,m] , [c,b,r] , [m,b,v] , [r,b,v] , [m,b,r] , [s,c,b] and [s,r,m] was not used in forming the hamilton circuit even though they had lesser weights. So these partial circuits are taken individually and are used to form hamilton circuits ,to find whether these hamilton circuits have lesser weight than the hamilton circuit found out earlier ( ie:- [r,c,b,v,s,m,r] was the hamilton circuit found out earlier ). ( The lesser weight partial circuits which were not used while forming the hamilton circuits for [c,b,s] , [s,b,v] , [v,s,b] , [m,b,s] , [r,b,s] , [c,b,v] , [b,r,m] , [r,m,b] , [b,s,c] , [b,s,m] , [b,s,r] , [c,b,m] , [c,b,r] , [m,b,v] , [r,b,v] , [m,b,r] , [s,c,b] and [s,r,m] need not be used for processing again.)

Now first [c,b,s] has to be taken as a necessary partial circuit and then the same process that occurred in Section #2.7 has to be done.
1) So first [c,b,s] is taken. Since hamilton circuit rule is not violated, [c,b,s] is taken.
2) Take [r,c,b]  from Vertex c. [r,c,b] fits with [c,b,s]. So [r,c,b] is taken. The new partial circuit is
[r,c,b,s].
3) Take [b,v,s] from Vertex v. Here [b,v,s] can replace [b,s] of [r,c,b,s] , since according to the properties of joining of partial circuits, it is allowed. So [b,v,s] fits with [r,c,b,s] to create the partial circuit
[r,c,b,v,s].
4) Take [b,r,m] from Vertex r. [b,r,m] does not fit with [r,c,b,v,s]. So take [s,r,m] from Vertex r. [s,r,m] does not fit with [r,c,b,v,s]. So take [c,r,m] from Vertex r. [c,r,m] fits with [r,c,b,v,s] to create the partial circuit [m,r,c,b,v,s].
5) Take [r,m,b] from Vertex m. [r,m,b] does not fit with [m,r,c,b,v,s]. So take [r,m,s] from Vertex m. [r,m,s] fits with [m,r,c,b,v,s] to create the hamilton circuit [m,r,c,b,v,s,m]. Weight of the hamilton circuit w[m,r,c,b,v,s,m] = w[m,r] + w[r,c] + w[c,b] + w[b,v] + w[v,s] + w[s,m] = 10 + 15 + 10 + 10 + 11 + 15 = 71.
So [m,r,c,b,v,s,m] = [c,b,s] + [r,c,b] + [b,v,s] + [c,r,m] + [r,m,s].
w[m,r,c,b,v,s,m] = 71


Now [s,b,v] has to be taken as a necessary partial circuit and then the same process that occurred in Section #2.7 has to be done.
1) First [s,b,v] is taken. Since hamilton circuit rule is not violated, [s,b,v] is taken.
2) Take [r,c,b] from Vertex c. [r,c,b] does not fit with [s,b,v]. So take [s,c,b] from Vertex c. [s,c,b] can replace [s,b] of [s,b,v], since according to the properties of joining of partial circuits, it is allowed. So [s,c,b] fits with [s,b,v] to form the partial circuit [s,c,b,v].
3) Take [b,v,s] from Vertex v. [b,v,s] does not fit with [s,c,b,v] because if [b,v,s] is joined with [s,c,b,v], then it will form a hamilton ciruit [s,c,b,v,s] of 4 vertices, which is not what is required because a hamilton circuit of 6 vertices is required. So take [b,v,m] from vertex v. [b,v,m] fits with [s,c,b,v] to form the partial circuit [s,c,b,v,m].
4) Take [b,r,m] from Vertex r. [b,r,m] does not fit with [s,c,b,v,m], since if [b,r,m] is made to join [s,c,b,v,m], then [b,r,m] will replace [b,v,m] of [s,c,b,v,m], so in the process if vertex r is gained, then vertex v is lost. So such joining is not allowed according to the principle of joining of partial circuits given in the top section of the article. Take [s,r,m] of vertex r. [s,r,m] fits with [s,c,b,v,m]
to form the hamilton circuit [s,c,b,v,m,r,s]. The weight of the hamilton circuit w[s,c,b,v,m,r,s] = w[s,c] + w[c,b] + w[b,v] + w[v,m] + w[m,r] + w[r,s] = 79
So [s,c,b,v,m,r,s] = [s,b,v] + [s,c,b] + [b,v,m] + [s,r,m]
w[s,c,b,v,m,r,s] = 79


Now [v,s,b] has to be taken as a necessary partial circuit and then the same process that occurred in Section #2.7 has to be done.
1) First [v,s,b] is taken. Since hamilton circuit rule is not violated, [v,s,b] is taken.
2) Take [r,c,b] from Vertex c. [r,c,b] fits with [v,s,b] to form the partial circuit [v,s,b,c,r]
3) Take [b,v,s] from vertex v. [b,v,s] does not fit with [v,s,b,c,r]. Because here [b,s] of [v,s,b,c,r] may replace [b,v] of [b,v,s] but the  weight of [b,v] ( ie:- 10 ) is more than the weight of [b,s] ( ie:- 6) being replaced. Also the edge may be replaced, because no vertices are lost and an edge is replaced by another edge. But the weight here is greater, so it is not replaced. Take [b,v,m] from Vertex v. [b,v,m] does not fit with [v,s,b,c,r]. So also [b,v,c] and [b,v,r] of vertex v does not fit with [v,s,b,c,r]. Take [m,v,s] of vertex v. [m,v,s] fits with [v,s,b,c,r] to form the partial circuit [m,v,s,b,c,r].
4) Take [b,r,m] from Vertex r. [b,r,m] does not fit with [m,v,s,b,c,r]. Take [s,r,m] from Vertex r. [s,r,m] does not fit with [m,v,s,b,c,r]. Take [c,r,m] from Vertex r. [c,r,m] fits with [m,v,s,b,c,r] to create the hamilton circuit [m,v,s,b,c,r,m]. The weight of the hamilton circuit w[m,v,s,b,c,r,m] = w[m,v] + w[v,s] + w[s,b] + w[b,c] + w[c,r] + w[r,m] = 71.
So [m,v,s,b,c,r,m] = [v,s,b] + [r,c,b] + [m,v,s] + [c,r,m]
w[m,v,s,b,c,r,m] = 71


In the same way that the hamilton circuit has been obtained for [c,b,s] , [s,b,v] and [v,s,b] , it is also done here for [m,b,s] , [r,b,s] , [c,b,v] , [b,r,m] , [r,m,b] , [b,s,c] , [b,s,m] , [b,s,r] , [c,b,m] , [c,b,r] , [m,b,v] ,
[r,b,v] , [m,b,r] , [s,c,b] and [s,r,m]. Only the final result is written below in order to make the example as
brief as possible.

Taking [m,b,s] as a necessay partial circuit, the hamilton circuit for [m,b,s] is :-
[m,v,b,c,s,r,m] = [m,b,s] + [s,c,b] + [b,v,m] + [s,r,m]
w[m,v,b,c,s,r,m] = 79

Taking [r,b,s] as a necessary partial circuit, the hamilton circuit for [r,b,s] is :-
[r,m,s,v,b,c,r] = [r,b,s] + [r,c,b] + [b,v,s] + [c,r,m] + [r,m,s]
w[r,m,s,v,b,c,r] = 78


Taking [c,b,v] as a necessary partial circuit, the hamilton circuit for [c,b,v] is :-
[c,b,v,s,m,r,c] = [c,b,v] + [r,c,b] + [b,v,s] + [c,r,m] + [r,m,s]
w[c,b,v,s,m,r,c] = 71

Taking [b,r,m] as a necessary partial circuit, the hamilton circuit for [b,r,m] is:-
[b,c,r,m,s,v,b] = [b,r,m] + [r,c,b] + [b,v,s] + [r,m,s].
w[b,c,r,m,s,v,b] = 71

Taking [r,m,b] as a necessary partial circuit, the hamilton circuit for [r,m,b] is:-
[r,m,v,b,c,s,r] = [r,m,b] + [s,c,b] + [b,v,m] + [s,r,m]
w[r,m,v,b,c,s,r] = 79

Taking [b,s,c] as a necessary partial circuit, the hamilton circuit for [b,s,c] is:-
[b,v,s,c,r,m,b] = [b,s,c] + [r,c,s] + [b,v,s] + [c,r,m] + [r,m,b]
w[b,v,s,c,r,m,b] = 72

Taking [b,s,m] as a necessary partial circuit, the hamilton circuit for [b,s,m] is:-
[b,v,s,m,r,c,b] = [b,s,m] + [r,c,b] + [b,v,s] + [c,r,m]
w[b,v,s,m,r,c,b] = 71

Taking [b,s,r] as a necessary partial circuit, the hamilton circuit for [b,s,r] is:-
[b,c,s,r,m,v,b] = [b,s,r] + [s,c,b] + [b,v,m] + [s,r,m]
w[b,c,s,r,m,v,b] = 79

Taking [c,b,m] as a necessary partial circuit, the hamilton circuit for [c,b,m] is:-
[c,b,v,m,s,r,c] = [c,b,m] + [r,c,b] + [b,v,m] + [s,r,c] + [s,m,v]
w[c,b,v,m,s,r,c] = 84

Taking [c,b,r] as a necessary partial circuit, the hamilton circuit for [c,b,r] is:-
[c,v,b,r,m,s,c] = [c,b,r] + [s,c,b] + [b,v,c] + [b,r,m] + [r,m,s]
w[c,v,b,r,m,s,c] = 81

Taking [m,b,v] as a necessary partial circuit, the hamilton circuit for [m,b,v] is:-
[m,c,b,v,s,r,m] = [m,b,v] + [m,c,b] + [b,v,s] + [s,r,m]
w[m,c,b,v,s,r,m] = 73

Taking [r,b,v] as a necessary partial circuit, the hamilton circuit for [r,b,v] is:-
[r,m,s,v,b,c,r] = [r,b,v] + [r,c,b] + [b,v,s] + [c,r,m]
w[r,m,s,v,b,c,r] = 71

Taking [m,b,r] as a necessary partial circuit, the hamilton circuit for [m,b,r] is:-
[m,s,r,c,b,v,m] = [m,b,r] + [r,c,b] + [b,v,m] + [s,r,c] + [s,m,v]
w[m,s,r,c,b,v,m] = 84

Taking [s,c,b] as a necessary partial circuit, the hamilton circuit for [s,c,b] is:-
[s,c,b,v,m,r,s] = [s,c,b] + [b,v,m] + [s,r,m]
w[s,c,b,v,m,r,s] = 79

Taking [s,r,m] as a necessary partial circuit, the hamilton circuit for [s,r,m] is:-
[s,r,m,v,b,c,s] = [s,r,m] + [s,c,b] + [b,v,m]
w[s,r,m,v,b,c,s] = 79

The lowest weight for a hamilton circuit is 71 among the hamilton circuits taken for the partial circuits of [c,b,s] , [s,b,v] , [v,s,b] , [m,b,s] , [r,b,s] , [c,b,v] , [b,r,m] , [r,m,b] , [b,s,c] , [b,s,m] , [b,s,r] , [c,b,m] ,
[c,b,r] , [m,b,v] , [r,b,v] , [m,b,r] , [s,c,b] and [s,r,m]. Also the weight of the hamilton circuit obtained in
Section #2.7 is also 71. So the hamilton circuit obtained in Section #2.7 or in Section #2.9 with weight of "71" is taken as the minimum weight hamilton circuit.

Section #2.9 (END)



Reference:-
1) "Elements of Discrete Mathematics " by C.L.Liu ( Second Edition ) (ISBN : 0-07-100544-7).
2) "A First Look at Graph Theory" by John Clark and Derek Allan Holton (ISBN : 81-7023-463-8 ).



[CincyJim]

Really ???

I simply;
1) do NOT answer a doorbell unless I feel like it,
2) say "No Thanks", and SLAM the door closed.
END OF "problem".

[varghese]

Code: Select all

Hello to All,

   I have made an imporvement in the method of the previous post. This improved method is also much simpler than previous post. I have also uploaded MS Word Document "TSP_Latest_M5_2016.docx" which contains the same content as this post ( but also contains more details of 'NPC-6' and 'NPC-7' process , since I am not allowed to enter more than 60000 characters in the editor ) for reference purpose.

The new method is as given below.


General Note :-  This note is for finding a polynomial time solution for the "Travelling Salesman Problem" for a complete graph for any number of vertices. The solutions that I am getting for the examples given in the textbooks ( References for the textbooks are given in the last part of this posting ) are giving the correct answers.
   The example that is solved in this document is taken from the internet, because this example gives a more detailed view of how the solution works.


A brief description about the Notations.

Beginning of Notations.

   A notation is followed by '::-' characters. After '::-' characters, an explanation is given about the notation starting in the next line. In order to make it simple , I have given the examples in the notation itself , in order to explain the notation.
   The vertices of a graph can be alphabets, numbers or a combination of both ie:- alphanumeric characters. 

[] ::-
The square brackets denote a partial circuit . A partial circuit is a graph in which any vertex of the graph is joined to another vertex by only a single edge. The partial circuit may be empty or it may consists of vertices or both vertices and edges.

[a] ::-
Denotes a partial circuit containing a single vertex or it denotes a single vertex. Here it denotes a partial circuit containing a vertex named 'a'.

[a,b] ::-
Denotes that vertex 'a' is joined to vertex 'b' or that there is an edge which joins vertex 'a' with vertex 'b'. Here each vertex is separated by a comma.

[a,b,c] ::-
Denotes that vertex 'a' is joined to vertex 'b' and vertex 'b' is joined to vertex 'c'.
So in the '[]' notation, any number of vertices( each vertex separtated by comma ) can be written.

[a,b,c,a] ::-
Denotes a partial circuit in which it is also a hamilton circuit, because here vertex 'a' is joined to vertex 'b' and vertex 'b' is joined to vertex 'c' and vertex 'c' is joined to vertex 'a'. This partial circuit can also be written as [b,c,a,b]. So [a,b,c,a]  is the same partial circuit as that of [b,c,a,b].

w[a,b,c] ::-
Denotes the weight of the partial circuit. This weight is the sum total of all the individual weights of the edges of the partial circuit. For eg:- if w[a,b] = 20 and w[b,c] = 30, then w[a,b,c] = w[a,b] + w[b,c] = 20 + 30 = 50.

[a,b,c] + [b,c,d] = [a,b,c,d] ::-
Here the two partial circuits [a,b,c] and [b,c,d] are combined to get [a,b,c,d] because the edge of [b,c] is common in both partial circuits. Here the total weight of [a,b,c,d] should be got by taking into consideration the common edge of [b,c]. So w[b,c] only needs to be added once.
For eg:-
if
w[a,b,c] = w[a,b] + w[b,c] = 20 + 30 = 50
and
w[b,c,d] = w[b,c] + w[c,d] = 30 + 40 = 70
and
if [a,b,c,d] = [a,b,c] + [b,c,d]
Then,
w[a,b,c,d] = w[a,b] + w[b,c] + w[c,d] = 20 + 30 + 40 = 90
   So w[a,b,c,d] is not got by directly adding the weights of w[a,b,c] and w[b,c,d] , since there is a common edge of [b,c] present in both [a,b,c] and [b,c,d]. So w[a,b,c,d] is not equal to w[a,b,c] + w[b,c,d] ie:- not equal to 120 (50 + 70 = 120).

ec[a] ::-
Denotes an 'edge count' of the vertex 'a'. An 'edge count' is the number of edges attached to a vertex. For eg:- in [a,b,c] , ec[a] = 1, ec[b] = 2 and ec[c] = 1. Here the edge count of [b] is 2 since there are 2 edges attached to vertex 'b'. ec[a] = 1 , because there is only one edge attached to vertex 'a'. In a partial circuit, the edge count of each vertex should be less than or equal to 2, to satisfy the criterion of a hamilton circuit, when the partial circuit is used to form the hamilton circuit in the end of the process.

Section #1.m (BEGIN) ::-
This denotes the section of "Example 1". 'm' denotes any number greater than or equal to one. Also 'BEGIN' denotes the beginning of the section.

Section #1.m (END) ::-
This denotes the section of "Example 1". 'm' denotes any number greater than or equal to one. Also 'END' denotes the end of the section.

Step-m ::-
Here 'Step-m' means the step number of an algorithm where 'm' denotes any number greater than or equal to one.

->{Dm} ::-
Here 'D' means description. 'm' stands for any number greater than or equal to one. This marker ie:- '->{Dm}' gives the statement number of the statement which it marks ( The statement which is marked precedes the '->{Dm}' marker ).  This marker is then written as '->Dm' elsewhere which gives a description of the statement which '->{Dm}' has marked. This marker is used mainly inside sections when space is required for writing descriptions. (The description of the notation '->Dm' is given below.)

->Dm. ::-
Here 'D' means description and 'm' stands for any number greater than or equal to one. This marker ie:- '->Dm' gives a description of the statement which it has marked.

->Lm ::-
Here 'L' means Level and 'm' stands for any number greater than or equal to one. This marker ie:- '->Lm' gives the Level number to which the partial circuit will be assigned.

NPC ::-
Here 'NPC' means necessary partial circuit. A necessary partial circuit is a partial circuit which will the first partial circuit used in the process of finding a hamilton circuit.

->{NPC-m} ::-
Here 'NPC' means 'necessary partial circuit'. 'm' stand for any number greater than or equal to one. This marker ie:- '->{NPC-m}' serves as a marker of the partial circuit which is to be taken as a necessary partial circuit.

->NPC-m ::-
Here 'NPC' means 'necessary partial circuit' and 'm' stands for any number greater than or equal to one. This marker shows the statement number which gives the details of the process that occurs with the necessary partial circuit when used in finding the minimum weight hamilton circuit.

[NPC-m-BEGIN] ::-
Here 'NPC' means 'necessary partial circuit' and 'm' stands for any number greater than or equal to one. This marker ie:- '[NPC-m-BEGIN]' marks the beginning of the process of finding the hamilton circuit using 'NPC-m'.

[NPC-m-END] ::-
Here 'NPC' means 'necessary partial circuit' and 'm' stands for any number greater than or equal to one. This marker ie:- '[NPC-m-END]' marks the end of the process of finding the hamilton circuit using 'NPC-m'.

PR-m ::-
Here 'PR-m' means property number 'm' where 'm' is any number greater than or equal to one. 'PR-m' is a marker of the description of a particular property of the joining of partial circuits.

C(n,r) ::-
This means a 'combination' of 'n' number of edges taken 'r' at a time. Here 'n' and 'r' are numbers. This 'combination' is the same combination that is there in mathematics. Here C(n,r) = n!/(r!*(n-r)!)

End of Notations.

Below are given some examples for describing properties of joining of partial circuits.

1) PR-1
Two partial circuits are [a,b,c,d,e] and [e,f,g]. These two partial circuits can be joined at the common vertex 'e'. So the partial circuit after joining is [a,b,c,d,e,f,g].

2) PR-2
Two partial circuits are [a,b,c,d,e] and [d,e,f]. These two partial circuits can be joined at the common edge [d,e]. So the partial circuit after joining is [a,b,c,d,e,f].

3) PR-3
Two partial circuits are [a,b,c,d,e] and [c,f,d]. If these two partial circuits are joined, then ec[c] = 3 and ec[d] = 3 and the property of a hamilton circuit will be violated.  But only this type of joining is allowed as an exception in which the edge [c,d] of [a,b,c,d,e] can be replaced by the partial circuit [c,f,d]. So the new partial circuit after joining is [a,b,c,f,d,e] while preserving the property of the hamilton circuit. In this joining of partial circuits , the edge of the partial circuit is replaced by two new edges and a new vertex is also added to the partial circuit.

4) PR-4 
Two partial circuits are [a,b,c] and [a,d,c]. If the hamilton circuit required to be found consists of only 4 vertices, then these partial circuits can be joined. So if the hamilton circuit consists of only 4 vertices, then the two partial circuits can be joined to get the partial circuit [a,b,c,d,a]. This partial circuit ie:- [a,b,c,d,a] is a hamilton circuit consisting of 4 vertices.

5) PR-5
Two partial circuits are [a,b,c,d,e] and [c,f,e]. They cannot be joined, because ec[c] will become 3 and so it would violate the hamilton circuit property.  Also here [c,d,e] cannot be replaced by [c,f,e] because if a new vertex 'f' is obtained, in its place another vertex 'd' becomes lost. So such a joining is not allowed.

6) PR-6
Two partial circuits are [a,b,c,d,e] and [d,f,g]. These two partial circuits cannot be joined at the common vertex 'd', since if the two partial circuits are joined, it would violate the edge count of vertex 'd' ie:- ec[d] would become 3.

7) PR-7
Two partial circuits are [a,b,c,d,e] and [e,d,f]. These two partial circuits cannot be joined at the common edge [d,e], because if the two partial circuits are joined, it would violate the edge count of vertex 'd' ie:- the ec[d] would become 3.

8) PR-8
Two partial circuits are [a,b,c,d,e] and [c,e,f]. These two partial circuits cannot be joined because if [c,e,f] is joined to [a,b,c,d,e], then ec[c] = 3 and ec[e] = 3. So such a joining is not allowed.

9) PR-9
Two partial circuits are [a,b,c,d,e] and [c,e,d]. These two partial circuits cannot be joined because if [c,e,d] is joined to [a,b,c,d,e], then the ec[c] will become 3. So such a joining is not allowed.

   So the only type of joining of partial circuits which are allowed are given in PR-1 , PR-2 and PR-3. PR-4 joining is only allowed for examples in which the hamilton circuit consists of 4 vertices only. PR-5 , PR-6 , PR-7 , PR-8 and PR-9 are important examples where joining of partial circuits are not allowed. A main point is that only PR-1 , PR-2 , PR-3 and PR-4 are the only type of joinings that are allowed and no other type of joinings are allowed.


A very brief algorithm which gives a brief description of the main important points of the process of finding the minimum weight hamilton circuit is given below .

Beginning of Algorithm

Step-1.
Take the partial circuits of each vertex of the graph.

Step-2.
Sort the partial circuits of each vertex in ascending order according to their weights.

Step-3.
Put the sorted partial circuits present under each vertex into the appropriate Level numbers.

Step-4.
Sort the partial circuits under each level numbers in descending order according to their weights.

Step-5.
Carry out the process for finding the hamilton circuit as shown in Section #1.8 for the example in the document. The hamilton circuit obtained in this step of the algorithm is assumed to be the minimum weight hamilton circuit.

Step-6.
To find out if there are lesser weight hamilton circuits than the hamilton circuit obtained in Step-5 , further processing is to be done which is as follows. Group the partial circuits of the graph (the partial circuits which are present in Section #1.2 in this example ) together and sort them in ascending order according to their weights as done in Section #1.10 in this example. ( Please note that in Section #1.9, it is not necesssary to sort the partial circuits in ascending order, as all the partial circuits have to be processed anyway , but because if it is sorted, minimum weight hamilton circuits will be got quicker. But even if it is quicker, still all the partial circuits have to be processed. So it is not a necessity to sort the partial circuits in Section #1.9 ).

Step-7.
Take each necessary partial circuit from the sorted group (as given in Section #1.10 of this example ) and carry out the same process that is done in Step-5 for each of the necessary partial circuit that is present in Section #1.10.

Step-8.
From the hamilton circuit obtained in Step-5 and all the other hamilton circuits obtained from the necessary partial circuits as done in Step-7, find the minimum weight hamilton circuit among them ( as shown in Section #1.12 for this example ). This minimum weight hamilton circuit is the final minimum weight hamilton circuit that is got by the algorithm.

End of Algorithm


Example 1

This example is taken from the Internet. The solution for the example is got in the process described from Section #1.1 to Section #1.9.

Section #1.1 (BEGIN)

In this section, the weights of the different edges connected to the different vertices of a 5 vertex graph is shown below.  The minimum weight hamilton circuit of this graph has a weight of '16' as given in the internet.

Vertex a
w[a,b] = 1   ->{D1}
w[a,c] = 4   ->{D2}
w[a,d] = 4
w[a,e] = 3

Vertex b
w[b,a] = 1
w[b,c] = 2
w[b,d] = 2
w[b,e] = 4

Vertex c
w[c,a] = 4
w[c,b] = 2
w[c,d] = 6
w[c,e] = 5

Vertex d
w[d,a] = 4
w[d,b] = 2
w[d,c] = 6
w[d,e] = 7

Vertex e
w[e,a] = 3
w[e,b] = 4
w[e,c] = 5
w[e,d] = 7

->D1. This shows the heading marked 'Vertex a'.
->D2. This shows the weight of one of the edges ( namely edge [a,c] ) which is connected to Vertex a.

Section #1.1 (END)


Section #1.2 (BEGIN)

In this section a combination of the edges ( the edges are taken from Section #1.1 ) connected to a particular vertex is taken. For eg:- there are four edges connected to vertex a. So the number of combinations of the four edges connected to 'vertex a' by taking two edges at a time is C(4,2) = 4!/((4-2)!*2!) = 6.


Vertex a
[b,a] + [a,c] = [b,a,c]
[b,a] + [a,d] = [b,a,d]
[b,a] + [a,e] = [b,a,e]
[c,a] + [a,d] = [c,a,d]
[c,a] + [a,e] = [c,a,e]
[d,a] + [a,e] = [d,a,e]

Vertex b
[a,b] + [b,c] = [a,b,c]
[a,b] + [b,d] = [a,b,d]
[a,b] + [b,e] = [a,b,e]
[c,b] + [b,d] = [c,b,d]
[c,b] + [b,e] = [c,b,e]
[d,b] + [b,e] = [d,b,e]

Vertex c
[a,c] + [c,b] = [a,c,b]
[a,c] + [c,d] = [a,c,d]
[a,c] + [c,e] = [a,c,e]
[b,c] + [c,d] = [b,c,d]
[b,c] + [c,e] = [b,c,e]
[d,c] + [c,e] = [d,c,e]

Vertex d
[a,d] + [d,b] = [a,d,b]
[a,d] + [d,c] = [a,d,c]
[a,d] + [d,e] = [a,d,e]
[b,d] + [d,c] = [b,d,c]
[b,d] + [d,e] = [b,d,e]
[c,d] + [d,e] = [c,d,e]

Vertex e
[a,e] + [e,b] = [a,e,b]
[a,e] + [e,c] = [a,e,c]
[a,e] + [e,d] = [a,e,d]
[b,e] + [e,c] = [b,e,c]
[b,e] + [e,d] = [b,e,d]
[c,e] + [e,d] = [c,e,d]


Section #1.2 (END)



Section #1.3 (BEGIN)

In this section, the weights of the partial circuits( these partial circuits were obtained in Section #1.2 ) of a particular vertex are given below.


Vertex a
w[b,a,c] = 1+4 = 5
w[b,a,d] = 1+4 = 5
w[b,a,e] = 1+3 = 4
w[c,a,d] = 4+4 = 8
w[c,a,e] = 4+3 = 7
w[d,a,e] = 4+3 = 7

Vertex b
w[a,b,c] = 1+2 = 3
w[a,b,d] = 1+2 = 3
w[a,b,e] = 1+4 = 5
w[c,b,d] = 2+2 = 4
w[c,b,e] = 2+4 = 6
w[d,b,e] = 2+4 = 6

Vertex c
w[a,c,b] = 4+2 = 6
w[a,c,d] = 4+6 = 10
w[a,c,e] = 4+5 = 9
w[b,c,d] = 2+6 = 8
w[b,c,e] = 2+5 = 7
w[d,c,e] = 6+5 = 11

Vertex d
w[a,d,b] = 4+2 = 6
w[a,d,c] = 4+6 = 10
w[a,d,e] = 4+7 = 11
w[b,d,c] = 2+6 = 8
w[b,d,e] = 2+7 = 9
w[c,d,e] = 6+7 = 13

Vertex e
w[a,e,b] = 3+4 = 7
w[a,e,c] = 3+5 = 8
w[a,e,d] = 3+7 = 10
w[b,e,c] = 4+5 = 9
w[b,e,d] = 4+7 = 11
w[c,e,d] = 5+7 = 12


Section #1.3 (END)



Section #1.4 (BEGIN)

In this section, the partial circuits ( ie:- the partial circuits present in Section #1.2 ) under each vertex are sorted in 'Ascending order' according to their weights.


Vertex a ( Sorted in ascending order )
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8
   
Vertex b ( Sorted in ascending order )
[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6
   
Vertex c ( Sorted in ascending order )
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11
   
Vertex d ( Sorted in ascending order )
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13
   
Vertex e ( Sorted in ascending order )
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12


Section #1.4 (END)



Section #1.5 (BEGIN)

Partial circuits from Section #1.4 are taken and written in this section.  Here the partial circuits are marked with level numbers in order to determine to which the Level number the partial circuits will be assigned. The lowest weight partial circuit under a particular vertex will always go to Level number 1, and similarly the next higher weight partial circuits under a particular vertex will go the higher level numbers.  So the marking is as follows.

Vertex a ( Sorted in ascending order )
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4    ->L1    ->{D3}     
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5    ->L2    ->{D4}
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5    ->L3    ->{D5}
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7    ->L4    ->{D6}
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7    ->L5    ->{D7}
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8    ->L6    ->{D8}
      
Vertex b ( Sorted in ascending order )
[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3    ->L1    ->{D9}
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3    ->L2    ->{D10}
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4    ->L3
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5    ->L4
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6    ->L5
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6    ->L6
      
Vertex c ( Sorted in ascending order )
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6    ->L1
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7    ->L2
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8    ->L3
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9    ->L4
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10    ->L5
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11    ->L6
      
Vertex d ( Sorted in ascending order )
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6    ->L1
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8    ->L2
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9    ->L3
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10    ->L4
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11    ->L5
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13    ->L6
      
Vertex e ( Sorted in ascending order )
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7    ->L1
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8    ->L2
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9    ->L3
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10    ->L4
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11    ->L5
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12    ->L6


->D3. [b,a,e] is the lowest weight partial circuit in vertex a. So it is grouped in Level1 as indicated by '->L1'.

->D4. [b,a,c] is the next higher weight partial circuit in vertex a. So it is grouped in Level2 as indicated by '->L2'.

->D5. [b,a,d] is the next higher weight partial circuit in vertex a. So it is grouped in Level3 as indicated by '->L3'.

->D6. [c,a,e] is the next higher weight partial circuit in vertex a. So it is grouped in Level4 as indicated by '->L4'.


->D7. [d,a,e] is the next higher weight partial circuit in vertex a. So it is grouped in Level5 as indicated by '->L5'.

->D8. [c,a,d] is the next higher weight partial circuit in vertex a. So it is grouped in Level6 as indicated by '->L6'.

->D9. [a,b,c] is the lowest weight partial circuit in vertex b. So it is grouped in Level1 as indicated by '->L1'.

->D10. [a,b,d] is the next higher weight in vertex b. So it is grouped in Level2 as indicated by '->L2'.

In the same way, all the other partial circuits are grouped in the various levels as given in the next section.


Section #1.5 (END)


Section #1.6 (BEGIN)

This section consists of the different Levels where the partial circuits ( the partial circuits are got from Section #1.5 ) which were marked in Section #1.5 are grouped together. Note that the group of partial circuits under Level1 is written at the beginning and the all the higher Level number groups are written subsequently below each other with the Level numbers of each level having an ascending order. For eg:- Level1 group is written first, then Level2 group , then Level3 group and so on until the last Level number group ( in this example the Last Level number is Level6 ).

Level1   
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4
[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7
   
Level2   
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8
   
Level3   
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9
   
Level4   
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10
   
Level5   
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11
   
Level6   
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12

Section #1.6 (END)



Section #1.7 (BEGIN)

In this section , the partial circuits under each Level (The Levels are taken from Section #1.6 ) are sorted in descending order of their weights.

Level1 ( sorted in descending order )   
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4
[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3
   
Level2 ( sorted in descending order )   
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3
   
Level3 ( sorted in descending order )   
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4
   
Level4 ( sorted in descending order )   
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5
   
Level5 ( sorted in descending order )   
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6
   
Level6 ( sorted in descending order )   
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6

Section #1.7 (END)


Section #1.8 (BEGIN)

Now in order to find the minimum weight hamilton circuit, the partial circuits which are necessary for forming the minimum weight hamilton circuit are found from the Level groups given in Section #1.7. The partial circuits are taken one by one for checking starting from the beginning of Level1 and proceeding downwards towards the last partial circuit of the last Level until a hamilton circuit is found.

1) Take [a,e,b] from Level1. Since hamilton circuit rule is not violated, [a,e,b] is taken for forming the hamilton circuit. So the partial circuit is [a,e,b].

2) Take [a,c,b] from Level1. [a,c,b] does not fit with [a,e,b] since [a,c,b] does not satisfy PR-1 , PR-2 or PR-3 properties of the joining of partial circuits. Also PR-4 property is not satisfied here, since a 5 vertex hamilton circuit is required here and not a 4 vertex hamilton circuit ( 'PR-1' , 'PR-2' , PR-3' and 'PR-4' are properties of the joining of partial circuits as given in the explanation examples given after the notation explanations ). So [a,c,b] is not taken.

3) Take [a,d,b] from Level1. [a,d,b] does not fit with [a,e,b] , since [a,d,b] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not fit with [a,e,b] , since [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not fit with [a,e,b] , since [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,b,c] is not taken. 

6) Take [b,d,c] from Level2. [b,d,c] satisfies PR-1 property. [b,d,c] fits with [a,e,b] to form the partial circuit [a,e,b,d,c].

7) Take [a,e,c] from Level2. [a,e,c] does not fit with [a,e,b,d,c] , since [a,e,c] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,e,c] is not taken. 

8) Take [b,c,e] from Level2. [b,c,e] does not fit with [a,e,b,d,c] , since [b,c,e] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,c,e] is not taken.

9) Take [b,a,c] from Level2. [b,a,c] does not fit with [a,e,b,d,c] , since [b,a,c] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,a,c] is not taken.

10) Take [a,b,d] from Level2. [a,b,d] does not fit with [a,e,b,d,c] , since [a,b,d] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,b,d] is not taken.

11) Take [b,d,e] from Level3. [b,d,e] does not fit with [a,e,b,d,c] , since [b,d,e] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,d,e] is not taken.

12) Take [b,e,c] from Level3. [b,e,c] does not fit with [a,e,b,d,c] , since [b,e,c] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,e,c] is not taken.

13) Take [b,c,d] from Level3. [b,c,d] does not fit with [a,e,b,d,c] , since [b,c,d] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,c,d] is not taken.

14) Take [b,a,d] from Level3. [b,a,d] does not fit with [a,e,b,d,c] , since [b,a,d] does not satisfy PR-1 , PR-2 or PR-3 properties. So [b,a,d] is not taken.

15) Take [c,b,d] from Level3. [c,b,d] does not fit with [a,e,b,d,c] , since [c,b,d] does not satisfy PR-1 , PR-2 or PR-3 properties. So [c,b,d] is not taken.

16) Take [a,d,c] from Level4. [a,d,c] does not fit with [a,e,b,d,c] , since [a,d,c] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,d,c] is not taken.

17) Take [a,e,d] from Level4. [a,e,d] does not fit with [a,e,b,d,c] , since [a,e,d] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,e,d] is not taken.

18) Take [a,c,e] from Level4. [a,c,e] does not fit with [a,e,b,d,c] , since [a,c,e] does not satisfy PR-1 , PR-2 or PR-3 properties. So [a,c,e] is not taken.

19) Take [c,a,e] from Level4. [c,a,e] satisfies PR-2 property. [c,a,e] fits with [a,e,b,d,c] to form the hamilton circuit [a,e,b,d,c,a].

Therefore the hamilton circuit which is assumed to be of minimum weight is [a,e,b,d,c,a].
So [a,e,b,d,c,a] = [a,e,b] + [b,d,c] + [c,a,e]
Weight of [a,e,b,d,c,a] ie:- w[a,e,b,d,c,a] = w[a,e] + w[e,b] + w[b,d] + w[d,c] + w[c,a] = 3 + 4 + 2 + 6 + 4 = 19.

In order to know if there are lesser weight hamilton circuits , group the partial circuits of the different vertices present in Section #1.2 into one group. This group is written in the next section ie:- in Section #1.9.

Section #1.8 (END)



Section #1.9 (BEGIN)

Group the partial circuits present in Section #1.2 into one group here. The group is given below.

[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7
[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12


Section #1.9 (END)


Section #1.10 (BEGIN)

Sort the group in Section #1.9 according to their weights in ascending order. The sorted group is given below.


[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3   
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3   
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4   
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4   
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5   
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5   
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5   
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6   
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6   
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6   
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6   
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7   
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7   
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7   
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7   
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8   
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8   
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8   
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8   
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9   
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9   
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9   
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10   
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10   
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10   
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11   
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11   
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11   
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12   
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13   

Section #1.10 (END)



Section #1.11 (BEGIN)

The sorted group from Section #1.10 is written here. Here each partial circuit is marked with necessary partial circuit number.


[a,b] + [b,c] = [a,b,c]    w[a,b,c] = 1+2 = 3    ->{NPC-1}
[a,b] + [b,d] = [a,b,d]    w[a,b,d] = 1+2 = 3    ->{NPC-2}
[b,a] + [a,e] = [b,a,e]    w[b,a,e] = 1+3 = 4    ->{NPC-3}
[c,b] + [b,d] = [c,b,d]    w[c,b,d] = 2+2 = 4    ->{NPC-4}
[b,a] + [a,c] = [b,a,c]    w[b,a,c] = 1+4 = 5    ->{NPC-5}
[b,a] + [a,d] = [b,a,d]    w[b,a,d] = 1+4 = 5    ->{NPC-6}
[a,b] + [b,e] = [a,b,e]    w[a,b,e] = 1+4 = 5    ->{NPC-7}
[c,b] + [b,e] = [c,b,e]    w[c,b,e] = 2+4 = 6    ->{NPC-8}
[d,b] + [b,e] = [d,b,e]    w[d,b,e] = 2+4 = 6    ->{NPC-9}
[a,c] + [c,b] = [a,c,b]    w[a,c,b] = 4+2 = 6    ->{NPC-10}
[a,d] + [d,b] = [a,d,b]    w[a,d,b] = 4+2 = 6    ->{NPC-11}
[c,a] + [a,e] = [c,a,e]    w[c,a,e] = 4+3 = 7    ->{NPC-12}
[d,a] + [a,e] = [d,a,e]    w[d,a,e] = 4+3 = 7    ->{NPC-13}
[b,c] + [c,e] = [b,c,e]    w[b,c,e] = 2+5 = 7    ->{NPC-14}
[a,e] + [e,b] = [a,e,b]    w[a,e,b] = 3+4 = 7    ->{NPC-15}
[c,a] + [a,d] = [c,a,d]    w[c,a,d] = 4+4 = 8    ->{NPC-16}
[b,c] + [c,d] = [b,c,d]    w[b,c,d] = 2+6 = 8    ->{NPC-17}
[b,d] + [d,c] = [b,d,c]    w[b,d,c] = 2+6 = 8    ->{NPC-18}
[a,e] + [e,c] = [a,e,c]    w[a,e,c] = 3+5 = 8    ->{NPC-19}
[a,c] + [c,e] = [a,c,e]    w[a,c,e] = 4+5 = 9    ->{NPC-20}
[b,d] + [d,e] = [b,d,e]    w[b,d,e] = 2+7 = 9    ->{NPC-21}
[b,e] + [e,c] = [b,e,c]    w[b,e,c] = 4+5 = 9    ->{NPC-22}
[a,c] + [c,d] = [a,c,d]    w[a,c,d] = 4+6 = 10    ->{NPC-23}
[a,d] + [d,c] = [a,d,c]    w[a,d,c] = 4+6 = 10    ->{NPC-24}
[a,e] + [e,d] = [a,e,d]    w[a,e,d] = 3+7 = 10    ->{NPC-25}
[d,c] + [c,e] = [d,c,e]    w[d,c,e] = 6+5 = 11    ->{NPC-26}
[a,d] + [d,e] = [a,d,e]    w[a,d,e] = 4+7 = 11    ->{NPC-27}
[b,e] + [e,d] = [b,e,d]    w[b,e,d] = 4+7 = 11    ->{NPC-28}
[c,e] + [e,d] = [c,e,d]    w[c,e,d] = 5+7 = 12    ->{NPC-29}
[c,d] + [d,e] = [c,d,e]    w[c,d,e] = 6+7 = 13    ->{NPC-30}

Section #1.11 (END)



Section #1.12 (BEGIN)

In this section, each necessary partial circuit present in Section #1.11 is used in finding the hamilton circuits.

Here the process of finding the hamilton circuits begins with 'NPC-1' .

->NPC-1.
[NPC-1-BEGIN]
Take [a,b,c] as a necessary partial circuit. Since hamilton circuit rule is not violated, [a,b,c] is taken for forming the hamilton circuit. So the partial circuit is [a,b,c].

Now use the same process that is done in Section #1.8.

1) Take [a,e,b] from Level1. [a,e,b] satisfies PR-3 property. So [a,e,b] fits with [a,b,c] to form [a,e,b,c].

2) Take [a,c,b] from Level1. [a,c,b] does not satisfy PR-4 property since a 5 vertex hamilton circuit is required here. So [a,c,b] is not taken.

3) Take [a,d,b] from Level1. [a,d,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,c] is not taken.

6) Take [b,d,c] from Level2. [b,d,c] satisfies PR-3 property. So [b,d,c] is joined with [a,e,b,c] to form [a,e,b,d,c].

7) Take [a,e,c] from Level2. [a,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,c] is not taken.

8) Take [b,c,e] from Level2. [b,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,e] is not taken.

9) Take [b,a,c] from Level2. [b,a,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,c] is not taken.

10) Take [a,b,d] from Level2. [a,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,d] is not taken.

11) Take [b,d,e] from Level3. [b,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,d,e] is not taken.

12) Take [b,e,c] from Level3. [b,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,c] is not taken.

13) Take [b,c,d] from Level3. [b,c,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,d] is not taken.

14) Take [b,a,d] from Level3. [b,a,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,d] is not taken.

15) Take [c,b,d] from Level3. [c,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,b,d] is not taken.

16) Take [a,d,c] from Level4. [a,d,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,c] is not taken.

17) Take [a,e,d] from Level4. [a,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,d] is not taken.

18) Take [a,c,e] from Level4. [a,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,e] is not taken.

19) Take [c,a,e] from Level4. [c,a,e] satisfies PR-2 property. So [c,a,e] is joined with [a,e,b,d,c] to form [a,e,b,d,c,a].

So [a,e,b,d,c,a] = [a,b,c] + [a,e,b] + [b,d,c] + [c,a,e]
w[a,e,b,d,c,a] = w[e,b] + w[b,d] + w[d,c] + w[c,a] + w[a,e] = 4 + 2 + 6 + 4 + 3 = 19.
[NPC-1-END]


->NPC-2.
[NPC-2-BEGIN]
Take [a,b,d] as a necessary partial circuit. Since hamilton circuit rule is not violated, [a,b,d] is taken for forming the hamilton circuit. So the partial circuit is [a,b,d].

Use the same process that is done in Section #1.8.

1) Take [a,e,b] from Level1. [a,e,b] satisfies PR-3 property. So [a,e,b] fits with [a,b,d] to form [a,e,b,d].

2) Take [a,c,b] from Level1. [a,c,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,b] is not taken.

3) Take [a,d,b] from Level1. [a,d,b] does not satisfy PR-4 property since a 5 vertex hamilton circuit is required. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,c] is not taken.

6) Take [b,d,c] from Level2. [b,d,c] satisfies PR-2 property. So [b,d,c] is joined with [a,e,b,d] to form [a,e,b,d,c].

7) Take [a,e,c] from Level2. [a,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,c] is not taken.

8) Take [b,c,e] from Level2. [b,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,e] is not taken.

9) Take [b,a,c] from Level2. [b,a,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,c] is not taken.

10) Take [a,b,d] from Level2. [a,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,d] is not taken.

11) Take [b,d,e] from Level3. [b,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,d,e] is not taken.

12) Take [b,e,c] from Level3. [b,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,c] is not taken.

13) Take [b,c,d] from Level3. [b,c,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,d] is not taken.

14) Take [b,a,d] from Level3. [b,a,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,d] is not taken.

15) Take [c,b,d] from Level3. [c,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,b,d] is not taken.

16) Take [a,d,c] from Level4. [a,d,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,c] is not taken.

17) Take [a,e,d] from Level4. [a,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,d] is not taken.

18) Take [a,c,e] from Level4. [a,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,e] is not taken.

19) Take [c,a,e] from Level4. [c,a,e] satisfies PR-2 property. So [c,a,e] fits with [a,e,b,d,c] to form [a,e,b,d,c,a].

[a,e,b,d,c,a] = [a,b,d] + [a,e,b] + [b,d,c] + [c,a,e]
w[a,e,b,d,c,a] = w[e,b] + w[b,d] + w[d,c] + w[c,a] + w[a,e] = 4 + 2 + 6 + 4 + 3 = 19
[NPC-2-END]


->NPC-3.
[NPC-3-BEGIN]
Take [b,a,e] as a necessary partial circuit. Since hamilton circuit rule is not violated, [b,a,e] is taken for forming the hamilton circuit. So the partial circuit is [b,a,e].

Use the same process that is done in Section #1.8.

1) Take [a,e,b] from Level1. If [a,e,b] is joined with [b,a,e] , a 3 vertex hamilton circuit will be obtained. But a 5 vertex hamilton circuit is required here and not a 3 vertex hamilton circuit. So
[a,e,b] is not taken.

2) Take [a,c,b] from Level1. [a,c,b] satisfies PR-3 property. So [a,c,b] fits with [b,a,e] to form [b,c,a,e].

3) Take [a,d,b] from Level1. [a,d,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,c] is not taken.

6) Take [b,d,c] from Level2. [b,d,c] satisfies PR-3 property. So [b,d,c] fits with [b,c,a,e] to form [b,d,c,a,e].

7) Take [a,e,c] from Level2. [a,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,c] is not taken.

8) Take [b,c,e] from Level2. [b,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,e] is not taken.

9) Take [b,a,c] from Level2. [b,a,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,c] is not taken.

10) Take [a,b,d] from Level2. [a,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,d] is not taken.

11) Take [b,d,e] from Level3. [b,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,d,e] is not taken.

12) Take [b,e,c] from Level3. [b,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,c] is not taken.

13) Take [b,c,d] from Level3. [b,c,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,d] is not taken.

14) Take [b,a,d] from Level3. [b,a,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,d] is not taken.

15) Take [c,b,d] from Level3. [c,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,b,d] is not taken.

16) Take [a,d,c] from Level4. [a,d,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,c] is not taken.

17) Take [a,e,d] from Level4. [a,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,d] is not taken.

18) Take [a,c,e] from Level4. [a,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,e] is not taken.

19) Take [c,a,e] from Level4. [c,a,e] is already present in [b,d,c,a,e]. Therefore there is no need to take [c,a,e].

20) Take [a,b,e] from Level4. [a,b,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,e] is not taken.

21) Take [a,d,e] from Level5. [a,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,e] is not taken.

22) Take [b,e,d] from Level5. [b,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,d] is not taken.

23) Take [a,c,d] from Level5. [a,c,d] is already present in [b,d,c,a,e]. Therefore there is no need to take [a,c,d].

24) Take [d,a,e] from Level5. [d,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [d,a,e] is not taken.

25) Take [c,b,e] from Level5. [c,b,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,b,e] is not taken.

26) Take [c,d,e] from Level6. [c,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,d,e] is not taken.

27) Take [c,e,d] from Level6. [c,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,e,d] is not taken.

28) Take [d,c,e] from Level6. [d,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [d,c,e] is not taken.

29) Take [c,a,d] from Level6. [c,a,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,a,d] is not taken.

30) Take [d,b,e] from Level6. [d,b,e] satisfies PR-2 property. So [d,b,e] fits with [b,d,c,a,e] to form [b,d,c,a,e,b].

[b,d,c,a,e,b] = [b,a,e] + [a,c,b] + [b,d,c] + [d,b,e]
w[b,d,c,a,e,b] = w[d,c] + w[c,a] + w[a,e] + w[e,b] + w[b,d] = 6 + 4 + 3 + 4 + 2 = 19
[NPC-3-END]


->NPC-4.
[NPC-4-BEGIN]
Take [c,b,d] as a necessary partial circuit. Since hamilton circuit rule is not violated, [c,b,d] is taken for forming the hamilton circuit. So the partial circuit is [c,b,d].

Use the same process that is done in Section #1.8.

1) Take [a,e,b] from Level1. [a,e,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,b] is not taken.

2) Take [a,c,b] from Level1. [a,c,b] satisfies PR-2 property. So [a,c,b] fits with [c,b,d] to form [a,c,b,d].

3) Take [a,d,b] from Level1. [a,d,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,c] is not taken.

6) Take [b,d,c] from Level2. [b,d,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,d,c] is not taken.

7) Take [a,e,c] from Level2. [a,e,c] satisfies PR-3 property. So [a,e,c] fits with [a,c,b,d] to form [a,e,c,b,d].

8) Take [b,c,e] from Level2. [b,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,e] is not taken.

9) Take [b,a,c] from Level2. [b,a,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,c] is not taken.

10) Take [a,b,d] from Level2. [a,b,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,d] is not taken.

11) Take [b,d,e] from Level3. [b,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,d,e] is not taken.

12) Take [b,e,c] from Level3. [b,e,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,c] is not taken.

13) Take [b,c,d] from Level3. [b,c,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,c,d] is not taken.

14) Take [b,a,d] from Level3. [b,a,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,d] is not taken.

15) Take [c,b,d] from Level3. [c,b,d] is already present in [a,c,b,d]. Therefore there is no need to take [c,b,d].

16) Take [a,d,c] from Level4. [a,d,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,c] is not taken.

17) Take [a,e,d] from Level4. [a,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,e,d] is not taken.

18) Take [a,c,e] from Level4. [a,c,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,e] is not taken.

19) Take [c,a,e] from Level4. [c,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [c,a,e] is not taken.

20) Take [a,b,e] from Level4. [a,b,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,e] is not taken.

21) Take [a,d,e] from Level5. [a,d,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,e] is not taken.

22) Take [b,e,d] from Level5. [b,e,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,e,d] is not taken.

23) Take [a,c,d] from Level5. [a,c,d] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,c,d] is not taken.

24) Take [d,a,e] from Level5. [d,a,e] satisfies PR-2 property. So [d,a,e] fits with [a,e,c,b,d] to form [a,e,c,b,d,a].

[a,e,c,b,d,a] = [c,b,d] + [a,c,b] + [a,e,c] + [d,a,e]
w[a,e,c,b,d,a] = w[a,e] + w[e,c] + w[c,b] + w[b,d] + w[d,a] = 3 + 5 + 2 + 2 + 4 = 16
[NPC-4-END]


->NPC-5.
[NPC-5-BEGIN]
Take [b,a,c] as a necessary partial circuit. Since hamilton circuit rule is not violated, [b,a,c] is taken for forming the hamilton circuit. So the partial circuit is [b,a,c].

Use the same process that is done in Section #1.8.

1) Take [a,e,b] from Level1. [a,e,b] satisfies PR-3 property. So [a,e,b] fits with [b,a,c] to form [b,e,a,c].

2) Take [a,c,b] from Level1. Since a 5 vertex hamilton circuit is required and not a 4 vertex hamilton circuit, [a,c,b] is not taken.

3) Take [a,d,b] from Level1. [a,d,b] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,d,b] is not taken.

4) Take [b,a,e] from Level1. [b,a,e] does not satisfy PR-1 , PR-2 or PR-3 property. So [b,a,e] is not taken.

5) Take [a,b,c] from Level1. [a,b,c] does not satisfy PR-1 , PR-2 or PR-3 property. So [a,b,c] is not taken.

6) Take [b,d,c] from Level2. [b,d,c] satisfies PR-1 property. So [b,d,c] fits with [b,e,a,c] to form [b,e,a,c,d,b].

[b,e,a,c,d,b] = [b,a,c] + [a,e,b] + [b,d,c]
w[b,e,a,c,d,b] = w[e,a] + w[a,c] + w[c,d] + w[d,b] + w[b,e] = 3 + 4 + 6 + 2 + 4 = 19
[NPC-5-END]

From the next necessary partial circuit onwards, only the hamilton circuit result for the necessary partial circuit is written in order to make the document as brief as possible.

->NPC-6.
[NPC-6-BEGIN]
Take [b,a,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
[b,c,e,a,d,b] = [b,a,d] + [a,e,b] + [b,c,e] + [c,b,d]
w[b,c,e,a,d,b] = w[c,e] + w[e,a] + w[a,d] + w[d,b] + w[b,c] = 5 + 3 + 4 + 2 + 2 = 16
[NPC-6-END]


->NPC-7.
[NPC-7-BEGIN]
Take [a,b,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
[a,c,d,b,e,a] = [a,b,e] + [a,c,b] + [b,d,c] + [c,a,e]
w[a,c,d,b,e,a] = w[c,d] + w[d,b] + w[b,e] + w[e,a] + w[a,c] = 6 + 2 + 4 + 3 + 4 = 19
[NPC-7-END]


->NPC-8.
[NPC-8-BEGIN]
Take [c,b,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [d,b,e,a,c,d].
[d,b,e,a,c,d] = [c,b,e] + [a,e,b] + [b,d,c] + [c,a,e]
w[d,b,e,a,c,d] = w[d,b] + w[b,e] + w[e,a] + w[a,c] + w[c,d] = 2 + 4 + 3 + 4 + 6 = 19
[NPC-8-END]


->NPC-9.
[NPC-9-BEGIN]
Take [d,b,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,d,c,a,e,b].
[b,d,c,a,e,b] = [d,b,e] + [a,e,b] + [b,d,c] + [c,a,e]
w[b,d,c,a,e,b] = w[b,d] + w[d,c] + w[c,a] + w[a,e] + w[e,b] = 2 + 6 + 4 + 3 + 4 = 19
[NPC-9-END]


->NPC-10.
[NPC-10-BEGIN]
Take [a,c,b] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [e,c,d,b,a,e].
[e,c,d,b,a,e] = [a,c,b] + [b,d,c] + [a,e,c] + [a,b,d]
w[e,c,d,b,a,e] = w[e,c] + w[c,d] + w[d,b] + w[b,a] + w[a,e] = 5 + 6 + 2 + 1 + 3 = 17
[NPC-10-END]


->NPC-11.
[NPC-11-BEGIN]
Take [a,d,b] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [d,a,e,c,b,d].
[d,a,e,c,b,d] = [a,d,b] + [a,e,c] + [b,c,e]
w[d,a,e,c,b,d] = w[a,d] + w[d,b] + w[b,c] + w[c,e] + w[e,a] = 4 + 2 + 2 + 5 + 3 = 16
[NPC-11-END]


->NPC-12.
[NPC-12-BEGIN]
Take [c,a,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,c,d,b,e,a].
[a,c,d,b,e,a] = [c,a,e] + [a,e,b] + [b,d,c]
w[a,c,d,b,e,a] = w[c,a] + w[a,e] + w[e,b] + w[b,d] + w[d,c] = 4 + 3 + 4 + 2 + 6 = 19
[NPC-12-END]


->NPC-13.
[NPC-13-BEGIN]
Take [d,a,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,e,c,b,d,a].
[a,e,c,b,d,a] = [d,a,e] + [a,e,b] + [b,c,e] + [c,b,d]
w[a,e,c,b,d,a] = w[a,e] + w[e,c] + w[c,b] + w[b,d] + w[d,a] = 3 + 5 + 2 + 2 + 4 = 16
[NPC-13-END]


->NPC-14.
[NPC-14-BEGIN]
Take [b,c,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [c,e,a,d,b,c].
[c,e,a,d,b,c] = [b,c,e] + [a,d,b] + [a,e,c]
w[c,e,a,d,b,c] = w[c,e] + w[e,a] + w[a,d] + w[d,b] + w[b,c] = 5 + 3 + 4 + 2 + 2 = 16
[NPC-14-END]


->NPC-15.
[NPC-15-BEGIN]
Take [a,e,b] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,e,b,d,c,a].
[a,e,b,d,c,a] = [a,e,b] + [b,d,c] + [c,a,e]
w[a,e,b,d,c,a] = w[a,e] + w[e,b] + w[b,d] + w[d,c] + w[c,a] = 3 + 4 + 2 + 6 + 4 = 19
[NPC-15-END]


->NPC-16.
[NPC-16-BEGIN]
Take [c,a,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [e,a,d,b,c,e].
[e,a,d,b,c,e] = [c,a,d] + [a,c,b] + [a,e,c] + [c,b,d]
w[e,a,d,b,c,e] = w[e,a] + w[a,d] + w[d,b] + w[b,c] + w[c,e] = 3 + 4 + 2 + 2 + 5 = 16
[NPC-16-END]


->NPC-17.
[NPC-17-BEGIN]
Take [b,c,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,c,d,a,e,b].
[b,c,d,a,e,b] = [b,c,d] + [a,e,b] + [a,d,c]
w[b,c,d,a,e,b] = w[c,d] + w[d,a] + w[a,e] + w[e,b] + w[b,c] = 6 + 4 + 3 + 4 + 2 = 19
[NPC-17-END]


->NPC-18.
[NPC-18-BEGIN]
Take [b,d,c] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,d,c,a,e,b].
[b,d,c,a,e,b] = [b,d,c] + [a,e,b] + [c,a,e]
w[b,d,c,a,e,b] = w[b,d] + w[d,c] + w[c,a] +w[a,e] + w[e,b] = 2 + 6 + 4 + 3 + 4 = 19
[NPC-18-END]


->NPC-19.
[NPC-19-BEGIN]
Take [a,e,c] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,e,c,b,d,a].
[a,e,c,b,d,a] = [a,e,c] + [a,d,b] + [b,c,e]
w[a,e,c,b,d,a] = w[a,e] + w[e,c] + w[c,b] + w[b,d] + w[d,a] = 3 + 5 + 2 + 2 + 4 = 16
[NPC-19-END]


->NPC-20.
[NPC-20-BEGIN]
Take [a,c,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,c,e,b,d,a].
[a,c,e,b,d,a] = [a,c,e] + [a,d,b] + [b,e,c]
w[a,c,e,b,d,a] = w[a,c] + w[c,e] + w[e,b] + w[b,d] + w[d,a] = 4 + 5 + 4 + 2 + 4 = 19
[NPC-20-END]


->NPC-21.
[NPC-21-BEGIN]
Take [b,d,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,d,e,a,c,b].
[b,d,e,a,c,b] = [b,d,e] + [a,c,b] + [a,e,d]
w[b,d,e,a,c,b] = w[b,d] + w[d,e] + w[e,a] + w[a,c] + w[c,b] = 2 + 7 + 3 + 4 + 2 = 18
[NPC-21-END]


->NPC-22.
[NPC-22-BEGIN]
Take [b,e,c] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,e,c,a,d,b].
[b,e,c,a,d,b] = [b,e,c] + [a,d,b] + [a,c,e]
w[b,e,c,a,d,b] = w[b,e] + w[e,c] + w[c,a] + w[a,d] + w[d,b] = 4 + 5 + 4 + 4 + 2 = 19
[NPC-22-END]


->NPC-23.
[NPC-23-BEGIN]
Take [a,c,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,c,d,b,e,a].
[a,c,d,b,e,a] = [a,c,d] + [a,e,b] + [b,d,c]
w[a,c,d,b,e,a] = w[a,c] + w[c,d] + w[d,b] + w[b,e] + w[e,a] = 4 + 6 + 2 + 4 + 3 = 19
[NPC-23-END]


->NPC-24.
[NPC-24-BEGIN]
Take [a,d,c] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,d,c,b,e,a].
[a,d,c,b,e,a] = [a,d,c] + [a,e,b] + [b,c,d]
w[a,d,c,b,e,a] = w[a,d] + w[d,c] + w[c,b] + w[b,e] + w[e,a] = 4 + 6 + 2 + 4 + 3 = 19
[NPC-24-END]


->NPC-25.
[NPC-25-BEGIN]
Take [a,e,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,e,d,b,c,a].
[a,e,d,b,c,a] = [a,e,d] + [a,c,b] + [b,d,e]
w[a,e,d,b,c,a] = w[a,e] + w[e,d] + w[d,b] + w[b,c] + w[c,a] = 3 + 7 + 2 + 2 + 4 = 18
[NPC-25-END]


->NPC-26.
[NPC-26-BEGIN]
Take [d,c,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [d,c,e,a,b,d].
[d,c,e,a,b,d] = [d,c,e] + [b,a,e] + [b,d,c]
w[d,c,e,a,b,d] = w[d,c] + w[c,e] + w[e,a] + w[a,b] + w[b,d] = 6 + 5 + 3 + 1 + 2 = 17
[NPC-26-END]


->NPC-27.
[NPC-27-BEGIN]
Take [a,d,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [a,d,e,b,c,a].
[a,d,e,b,c,a] = [a,d,e] + [a,c,b] + [b,e,d]
w[a,d,e,b,c,a] = w[a,d] + w[d,e] + w[e,b] + w[b,c] + w[c,a] = 4 + 7 + 4 + 2 + 4 = 21
[NPC-27-END]


->NPC-28.
[NPC--BEGIN]
Take [b,e,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [b,e,d,a,c,b].
[b,e,d,a,c,b] = [b,e,d] + [a,c,b] + [a,d,e]
w[b,e,d,a,c,b] = w[b,e] + w[e,d] + w[d,a] + w[a,c] + w[c,b] = 4 + 7 + 4 + 4 + 2 = 21
[NPC-28-END]


->NPC-29.
[NPC-29-BEGIN]
Take [c,e,d] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [c,e,d,a,b,c].
[c,e,d,a,b,c] = [c,e,d] + [a,b,c] + [b,a,d]
w[c,e,d,a,b,c] = w[c,e] + w[e,d] + w[d,a] + w[a,b] + w[b,c] = 5 + 7 + 4 + 1 + 2 = 19
[NPC-29-END]


->NPC-30.
[NPC-30-BEGIN]
Take [c,d,e] as a necessary partial circuit.
Use the same process that is done in Section #1.8.
The hamilton circuit is [c,d,e,a,b,c].
[c,d,e,a,b,c] = [c,d,e] + [b,a,e] + [a,b,c]
w[c,d,e,a,b,c] = w[c,d] + w[d,e] + w[e,a] + w[a,b] + w[b,c] = 6 + 7 + 3 + 1 + 2 = 19
[NPC-30-END]


All the necessary partial circuits present in Section #1.11 has been processed. Now compare the different hamilton circuits obtained.

The hamilton circuit obtained in Section #1.8 ie:- [a,e,b,d,c,a] has a weight of 19.

The lowest weight hamilton circuits obtained by processing the necessary partial circuits as given in this section are as follows.

( The results are written in the format of :-

line number) necessary partial circuit number ; necessary partial circuit ; hamilton circuit obtained from the necessary partial circuit ; weight of the hamilton circuit.

The values in the result are separated by a semicolon. )

1) NPC-4 ; [c,b,d] ; [a,e,c,b,d,a] ; 16.
2) NPC-6 ; [b,a,d] ; [b,c,e,a,d,b] ; 16.
3) NPC-11 ; [a,d,b] ; [d,a,e,c,b,d] ; 16.
4) NPC-13 ; [d,a,e] ; [a,e,c,b,d,a] ; 16.
5) NPC-14 ; [b,c,e] ; [c,e,a,d,b,c] ; 16.
6) NPC-16 ; [c,a,d] ; [e,a,d,b,c,e] ; 16.
7) NPC-19 ; [a,e,c] ; [a,e,c,b,d,a] ; 16.

Seven hamilton circuits formed from the necessary partial circuits have the least weight of 16. So the hamilton circuit ( for eg:- the hamilton circuit [a,e,c,b,d,a] formed from NPC-4 ( ie:- [c,b,d] ) ) with weight of 16 is the minimum weight hamilton circuit.


Section #1.12 (END)



Reference:-
1) "Elements of Discrete Mathematics " by C.L.Liu ( Second Edition ) (ISBN : 0-07-100544-7).
2) "A First Look at Graph Theory" by John Clark and Derek Allan Holton (ISBN : 81-7023-463-8 ).




[uninfinite]

Please pardon my near absolute ignorance, but if you have a starting point - does not ''proceed to the next nearest point not previously visited'' have the same effect? Surely not - because otherwise, why the problem, but if not, why not?

[jackk]

the TSP method is a easy but a logical for solving.

[varghese]

Hello to All,

I am uploading the php files as MS Word files, because the files with .php extensions are not allowed to be uploaded. These Word files contain the code for a heuristic method for solving the Travelling Salesman Problem. This method is considered heuristic because there is no proof that this method will always give the optimal circuit for the Travelling Salesman Problem.

Since the files which are uploaded are Word files, first copy the code exactly from these files and paste them into any code editor and save the new files as '.php' files when these files are required for execution. So convert 'tsp_1.docx' to 'tsp_1.php' , 'tsp_2.docx' to 'tsp_2.php' , 'tsp_3.docx' to 'tsp_3.php' and 'tsp_4.docx' to 'tsp_4.php' files. The order of execution of the php files is 'tsp_1.php' , 'tsp_2.php' , 'tsp_3.php' and then 'tsp_4.php'.

Some important properties of the program are given below.

1) The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

2) The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

2) When 33 vertices or higher number of vertices are given for processing to the program, errors showing 'undefined weights' are given as output. Maybe in higher versions of php, the settings 'max_input_vars' can be changed , so that these errors will not show. Also closely associated with this error is the error of 'input values of 1000 exceeded'. So this program can process upto to a maximum of 32 vertices only ,until somehow the 'max_input_vars' settings in php can be set to any value that is required.

3) Vertex names should begin with an enlgish alphabet. The rest of the name should contain english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

4) Each vertex name should be different from every other vertex name. No two vertices should have the same name.

5) Only positive integers should be used for the weight values of the edges.

6) No edge should have a weight with a value of 0.

7) This program was executed on Wampserver 2.2, which has php of version 5.4.3 and apache of version 2.2.22 .

8) In tsp_4.php , in line no 3 and line no 4, the following code is given. The code is

ini_set('memory_limit', '1024M');
ini_set('max_execution_time', 7200);

This code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default given in php. To prevent this, the code 'ini_set('max_execution_time', 7200);' is given.

9) Also for the code '<?php session_start(); ?>', please note that there should not be a space or even an empty line above this code when copying this code into the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code is at the very beginning of the code file, without even a single space preceeding this line of code.

[varghese]

Hello to All,

I am uploading the php files and the .sql file as text files, because the files with .php and .sql extensions are not allowed to be uploaded in the forum.

The program in this post uses the same algorithm of the program as given in the latest post which preceeds this post , but the difference here is that this program uses a database so that input data need not always be typed in if the graph contains a large number of vertices. In this program a 'Mysql' database is used for executing the program.

In this program , a 'Mysql' database is used , so that input need not always be typed when executing the program. There are four word files which contain the php code for executing the program with a database. Since the files are Word files, first copy the code exactly from these files and paste them into any code editor ( preferably Notepad++ ) and save the new files as '.php' files when these files are required for execution. So convert 'tsp_1_db.docx' to 'tsp_1_db.php' , 'tsp_2_db.docx' to 'tsp_2_db.php' , 'tsp_3_db.docx' to 'tsp_3_db.php' and 'tsp_4_db.docx' to 'tsp_4_db.php' files.

The order of execution of the php files is 'tsp_1_db.php' , 'tsp_2_db.php' , 'tsp_3_db.php' and then 'tsp_4_db.php'. The execution need only to be started from 'tsp_1_db.php'.

The 'XAMPP' Web Server is used for executing the php files and for processing the table data present in the database. All the four 'php' files can be put in 'C:\xampp\htdocs' folder.

"tsp_data_for_program_database_db.txt" should be opened preferably in an editor like Notepad++ for example and saved as "tsp_data_for_program_database_db.sql". ( Please note that "tsp_data_for_program_database_db.txt" should be converted into a '.sql' extension file, otherwise, Mysql database will not be able to import the database ).

"tsp_data_for_program_database_db.sql" is the sql file for importing the database into the mysql database. This file has to be imported into the database, otherwise the database php files will not work , since the "tsp_data_for_program_database" database should be present in the main database. All the tables needed for storing the data of the graphs should be present in the "tsp_data_for_program_database" database.

An example of a table given in the database of "tsp_data_for_program_database" is as follows. A table 'vertex_7' is already present as an example of data of a seven vertex graph in the "tsp_data_for_program_database" database. For running the example of a seven vertex graph, the 'vertex_7' can be selected from the drop down list of the tables , when the file 'tsp_1_db.php' is executed.

Some important properties of the program are given below.

1) The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

2) The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

3) When a 33 vertex graph or a graph containing more than 33 vertices are given for processing to the program, errors showing 'undefined weights' and 'input values of 1000 exceeded' are given as output. This is because the default value of the constant 'max_input_vars' in php is 1000.

In a 33 vertex graph, there are 1056 edges ( ie:- 33*32 = 1056 , since there are 33 vertices in the graph and there are 32 edges attached to each vertex ) or 1056 input values. 1056 is greater than 1000 and so the program will output an error since the number of input values exceed 1000.

For eg:- if a 50 vertex graph is to be processed, then there are 2450 edges ( ie:- 50*49 = 2450 , since there are 50 vertices in the graph and there are 49 edges attached to each vertex ) or 2450 input values. So 'max_input_vars' can be given a value higher than 2450 for eg:- 3000. So the 'max_input_vars' constant in php can be changed by uncommenting the line 'max_input_vars=1000' and giving a value of 'max_input_vars=3000' to the 'max_input_vars' constant.

The 'max_input_vars' constant can be found in 'php.ini' file which is present in 'c:/xampp/php' folder.

To verify if 'max_input_vars' has the required value, the function 'phpinfo()' can be typed in any empty php file and the file executed. This information displayed after the execution of the 'phpinfo()' function will contain the value of 'max_input_vars' along with other information that the function will display.

4) Vertex names should begin with an english alphabet. The rest of the name should contain a combination of english alphabets or positive integer numbers or a combination of both english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

5) Each vertex name should be different from every other vertex name. No two or more vertices should have the same name.

6) Only positive integers should be used for the weight values of the edges.

7) No edge should have a weight with a value of 0.

8) In tsp_4_db.php , in line no 3 and line no 4, the following code is given. The code is as follows :-

ini_set('memory_limit', '1024M');
ini_set('max_execution_time', 10800);

The above code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default value given in php. To prevent this, the code 'ini_set('max_execution_time', 10800);' is given.

9) Also for the code '<?php session_start(); ?>', ( present at the very beginning of a php file ) please note that there should not be a space or even an empty line above this code if any code modification is made in the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code (ie:- the code included between the apostrophies ie:- '<?php session_start(); ?>') is present at the very beginning of the code file, without even a single space preceeding this line of code.

[varghese]

Hello to All,

I am uploading the php files and the .sql file as text files, because the files with .php and .sql extensions are not allowed to be uploaded in the forum.

I am writing about 2 programs as 2 posts so as to avoid confusion. I am writing about the first program in this post. Details about the second program is written in the next post.



A Quick General Guidline for executing the PHP Program

( IMPORTANT. PLEASE NOTE. First copy the code exactly as it is from the Word files and paste them into an editor ( for eg:- Notepad++ ) and save them as '.php' files or as '.sql' files as the case may be. For eg:- 'tsp_1_db_PCHA_1.docx' should be converted into 'tsp_1_db_PCHA_1.php' file. 'tsp_tables.docx' should be converted into 'tsp_tables.sql' file. )

The list of files to be converted is given below.
1) 'tsp_1_db_PCHA_1.docx' should be converted into 'tsp_1_db_PCHA_1.php'.
2) 'tsp_2_db_PCHA_1.docx' should be converted into 'tsp_2_db_PCHA_1.php'.
3) 'tsp_3_db_PCHA_1.docx' should be converted into 'tsp_3_db_PCHA_1.php'.
4) 'tsp_4_db_PCHA_1.docx' should be converted into 'tsp_4_db_PCHA_1.php'.
5) 'tsp_tables.docx' should be converted into 'tsp_tables.sql'.

The algorithm in this posting is called 'Partial Circuit Heuristic Algorithm_1' or 'PCHA_1'. The algorithm in the next posting is given the title of 'Partial Circuit Heuristic Algorithm_2 or 'PCHA_2'. This posting gives an explanation about 'PCHA_1'.

The general guideline is given below in 9 steps. These steps may vary according to the different type of computers and the different versions of XAMPP Webservers , PHP etc.. that are used in each type of computer.

1) Download 'XAMPP' for Windows from the internet and install 'XAMPP' Web server.
2) Create a folder for eg:- 'tsp_programs' in "C:\xampp\htdocs" folder.
3) Copy the php files ( ie :- 'tsp_1_db_PCHA_1.php' , 'tsp_2_db_PCHA_1.php' , 'tsp_3_db_PCHA_1.php' and 'tsp_4_db_PCHA_1.php' ) and paste the php files into ' C:\xampp\htdocs\tsp_programs' folder.
4) Open 'XAMPP' Control Panel and start Apache first and then start MySql.
5) Open Google Chrome browser and in the URL address, type 'localhost/phpmyadmin' and press enter.
The phpmyadmin page will be shown.
6) From phpmyadmin , create a database named 'tsp_data_for_program_database'.
( VERY IMPORTANT. PLEASE NOTE. When creating the new database, the database name should be exactly 'tsp_data_for_program_database'. If the name is different, the php files will not work. )
7) Import the example tables into "tsp_data_for_program_database" database.
8) Open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs' and press enter.
9) A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_db_PCHA_1.php'. From 'tsp_1_db_PCHA_1.php', the execution of the program can start, by clicking on 'tsp_1_db_PCHA_1.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )


A General Note about the PHP Program.

The main advantage of this heuristic program, is that the program takes a very small amount of time to get the result.

Some results which are not got in PCHA_1 may be got in PCHA_2. Also some results which are not got in PCHA_2 may be got in PCHA_1. So both algorithms are useful. But the main difference is that PCHA_2 takes much less time for getting a result than PCHA_1.

"https://en.wikipedia.org/wiki/Christofides_algorithm" is the website address for an article about Christofides Algorithm. Also in the article it mentions that the results are got within 3/2 of the optimal value. Also Triangle inequality condition needs to be satisfied for Christofides Algorithm to work.

A short form for 'Partial Circuit Heuristic Algorithm_1' can be written as 'PCHA_1'. In PCHA_1 , the Triangle inequality condition need not be satisfied and the results that are got are better than 3/2 of the optimum solution length.

This PHP program finds the 'polynomial time' heuristic solution to the Travelling Salesman Problem for a 'Complete' graph using a database, so that data does not have to be typed in always.

This is a general heuristic program in 'PHP' for solving the Travelling Salesman Problem for any number of vertices.

The input data during the execution of the program is only the name of each vertex and the weight of each edge present in the graph.

( PLEASE NOTE :- If for an example graph, if there is no edge between two vertices, then assign a weight to the imaginary edge connecting the two vertices. The weight can be equal to the sum of the weights of all the real edges present in the example graph. This imaginary edge with a weight is necessary because of the condition that this program works on 'Complete' graphs only. A 'Complete' graph is the exactly the same mathematical object used in Graph Theory. Also please note that no edge in the example graph should have a weight of 0. )

To work with PHP files , 'XAMPP' Web Server has to be installed in the Computer. 'XAMPP' Web Server is available on the internet.

After installing XAMPP and when XAMPP Web Server is running , it is better not to connect to the internet , because of 'XAMPP' itself being a Web Server and so when XAMPP is running and if the computer is connected to the internet, other insecure connections can become connected to the computer. So as far as possible, once XAMPP is fully installed , and before starting to run XAMPP, it is better to disconnect the computer from the internet. After php program has finished executing, and Apache and Mysql has been stopped from the XAMPP control panel , and when XAMPP has been quit completely, then the computer can be connected to the internet.

The site from where data for the example tables is taken is 'https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html'. The website contains bigger data problems which can be used as input data when running this program.

Name of datasets and their correct minimum weights according to website are as given below.
1) DANTZIG42 ( Dataset of 42 vertices ). Correct minimum weight according to website equals 699.
2) FRI26 ( 26 vertices ). Correct minimum weight is 937.
3) GR17 ( 17 vertices ). Correct minimum weight is 2085.
4) PO1 ( 15 vertices ). Correct minimum weight is 291.

I am giving below the results of the program execution that I had obtained while running 'PCHA_1'. The results consists of the dataset name, the minimum weight obtained by 'PCHA_1' and the time taken for 'PCHA_1' to execute. I executed 'PCHA_1' on a Toshiba Satellite C640 Notebook computer. The results are as given below.
1) DANTZIG42 ( 42 vertices ). Minumum weight obtained is 819. Time taken is 1 minute and 27 seconds.
2) FRI26 ( 26 vertices ). Minimum weight is 1010. Time taken is 5 seconds.
3) GR17 ( 17 vertices ). Minimum weight is 2183. Time taken is 3 seconds.
4) PO1 ( 15 vertices ). Minimum weight is 291. Time taken is 1 second.


Important details about database program

In this program , a 'Mysql' database is used , so that input need not always be typed in when executing the program. There are four php files which contain the php code for executing the program with a database. 'tsp_1_db_PCHA_1.php' , 'tsp_2_db_PCHA_1.php' , 'tsp_3_db_PCHA_1.php' and 'tsp_4_db_PCHA_1.php' are the four php files. The order of execution of the php files is 'tsp_1_db_PCHA_1.php' , 'tsp_2_db_PCHA_1.php' , 'tsp_3_db_PCHA_1.php' and then 'tsp_4_db_PCHA_1.php'. The execution need only to be started from 'tsp_1_db_PCHA_1.php'.

The 'XAMPP' Web Server is used for executing the php files and for processing the table data present in the database. All the four 'php' files ( ie:- 'tsp_1_db_PCHA_1.php' , 'tsp_2_db_PCHA_1.php' , 'tsp_3_db_PCHA_1.php' and ' tsp_4_db_PCHA_1.php' ) can be put in 'C:\xampp\htdocs\tsp_programs' folder. The execution need only to be started from 'tsp_1_db_PCHA_1.php'.

The database file is 'tsp_tables.sql'. This file contains a 15 vertex, 17 vertex, 26 vertex and 42 vertex graph data. All the 4 graphs data is put in one file because in the forum only 5 files maximum is allowed to be submitted.

If any of the example tables is imported into the database , it should always be imported into the database named " tsp_data_for_program_database". The 'phpmyadmin' database interface can be used for importing the table sql files.

An example of a table is as follows. A table 'vertex_15' is present as an example of data of a fifteen vertex graph in the "tsp_tables.sql" table. For running the example of a 'fifteen' vertex graph, the 'vertex_15' can be selected from the drop down list of the tables , when the file 'tsp_1_db_PCHA_1.php' is executed.

Also the format of the example tables in the database should be followed exactly for creating new example tables , otherwise the program will not work. An example of what is meant by format of the table, is that in the example table, there is no primary key column. So addition , deletion etc.. of data , while in phpmyadmin , cannot be done quickly on the tables, if changes need to be made on the data in the tables. So when creating a new table, create a temporary primary key column in order to quickly insert data into the example tables. After all the data has been entered into the example table, then the primary key column can be removed. ( Please note that a creation of a primary key column is not necessary and need only be created if data needs to be entered faster while working in phpmyadmin. )


Important properties of the PHP Program

The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

The program is an iteration type program and will give 1 or more hamilton circuits which may have the minimum weights. If more that one hamilton circuit is output, take the hamilton circuit with the least weight as the hamilton circuit with the most minimum weight.

The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

When a 33 vertex graph or a graph containing more than 33 vertices are given for processing to the program, errors showing 'undefined weights' and 'input values of 1000 exceeded' are given as output if the default value of the constant 'max_input_vars' in php is 1000.

In a 33 vertex graph, there are 1056 edges ( ie:- 33*32 = 1056 , since there are 33 vertices in the graph and there are 32 edges attached to each vertex ) or 1056 input values. 1056 is greater than 1000 and so the program will output an error since the number of input values exceed 1000.

For eg:- if a 50 vertex graph is to be processed, then there are 2450 edges ( ie:- 50*49 = 2450 , since there are 50 vertices in the graph and there are 49 edges attached to each vertex ) or 2450 input values. So 'max_input_vars' can be given a value higher than 2450 for eg:- 3000. So the 'max_input_vars' constant in php can be changed by uncommenting the line 'max_input_vars=1000' and giving a value of 'max_input_vars=3000' to the 'max_input_vars' constant.

The 'max_input_vars' constant can be found in 'php.ini' file which is present in 'C:/xampp/php' folder.

To verify if 'max_input_vars' has the required value, the function 'phpinfo()' can be typed in any empty php file and the file executed. This information displayed after execution of the 'phpinfo()' function will contain the value of 'max_input_vars' along with other information that the function will display.

Vertex names which are input into the program should begin with an english alphabet. The rest of the name should contain a combination of english alphabets or positive integer numbers or a combination of both english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

Each vertex name should be different from every other vertex name. No two or more vertices should have the same name.

Only positive numbers should be used for the weight values of the edges.

No edge should have a weight with a value of 0.

In "tsp_4_db_PCHA_1.php" , in line no 3 and line no 4, the following code is given. The code is as follows :-

Code Begin
ini_set('memory_limit', '1024M');
ini_set('max_execution_time', 10800);
Code End

( Note:- 'Code Begin' and 'Code End' are just markers to show the beginning and the ending of the code. )

The above code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default value given in php. To prevent this, the code 'ini_set('max_execution_time', 10800);' is given.

Also for the code given below as
Code Begin
'<?php
session_start();
?>'
Code End
( which is present at the very beginning of a php file ) please note that there should not be a space or even an empty line above this code if any code modification is made in the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code (ie:- the code included between the single apostrophies ) is present at the very beginning of the code file, without even a single space preceeding this line of code.

[varghese]

Hello to All,

This is the post about the second program.


A Quick General Guidline for executing the PHP Program

( IMPORTANT. PLEASE NOTE. First copy the code exactly as it is from the Word files and paste them into an editor ( for eg:- Notepad++ ) and save them as '.php' files or as '.sql' files as the case may be. For eg:- 'tsp_1_db_PCHA_2.docx' should be converted into 'tsp_1_db_PCHA_2.php' file. 'tsp_tables.docx' should be converted into 'tsp_tables.sql' file. )

The list of files to converted is given below.
1) 'tsp_1_db_PCHA_2.docx' should be converted into 'tsp_1_db_PCHA_2.php'.
2) 'tsp_2_db_PCHA_2.docx' should be converted into 'tsp_2_db_PCHA_2.php'.
3) 'tsp_3_db_PCHA_2.docx' should be converted into 'tsp_3_db_PCHA_2.php'.
4) 'tsp_4_db_PCHA_2.docx' should be converted into 'tsp_4_db_PCHA_2.php'.
5) 'tsp_tables.docx' should be converted into 'tsp_tables.sql'.

The algorithm in this posting is called 'Partial Circuit Heuristic Algorithm_2' or 'PCHA_2'. This posting gives an explanation about 'PCHA_2'. The algorithm in the preceeding posting is called 'Partial Circuit Heuristic Algorithm_1' or 'PCHA_1'.

The general guideline is given below in 9 steps. These steps may vary according to the different type of computers and the different versions of XAMPP Webservers , PHP etc.. that are used in each type of computer.

1) Download 'XAMPP' for Windows from the internet and install 'XAMPP' Web server.
2) Create a folder for eg:- 'tsp_programs' in "C:\xampp\htdocs" folder.
3) Copy the php files ( ie :- 'tsp_1_db_PCHA_2.php' , 'tsp_2_db_PCHA_2.php' , 'tsp_3_db_PCHA_2.php' and 'tsp_4_db_PCHA_2.php' ) and paste the php files into ' C:\xampp\htdocs\tsp_programs' folder.
4) Open 'XAMPP' Control Panel and start Apache first and then start MySql.
5) Open Google Chrome browser and in the URL address, type 'localhost/phpmyadmin' and press enter.
The phpmyadmin page will be shown.
6) From phpmyadmin , create a database named 'tsp_data_for_program_database'.
( VERY IMPORTANT. PLEASE NOTE. When creating the new database, the database name should be exactly 'tsp_data_for_program_database'. If the name is different, the php files will not work. )
7) Import the example tables into "tsp_data_for_program_database" database.
8) Open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs' and press enter.
9) A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_db_PCHA_2.php'. From 'tsp_1_db_PCHA_2.php', the execution of the program can start, by clicking on 'tsp_1_db_PCHA_2.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )


A General Note about the PHP Program.

The main advantage of this heuristic program, is that the program takes a very small amount of time to get the result.

Some results which are not got in PCHA_2 may be got in PCHA_1. Also some results which are not got in PCHA_1 may be got in PCHA_2. So both algorithms are useful. But the main difference is that PCHA_2 takes much less time for getting a result than PCHA_1.

"https://en.wikipedia.org/wiki/Christofides_algorithm" is the website address for an article about Christofides Algorithm. Also in the article it mentions that the results are got within 3/2 of the optimal value. Also Triangle inequality condition needs to be satisfied for Christofides Algorithm to work.

A short form for 'Partial Circuit Heuristic Algorithm_2' can be written as 'PCHA_2'. In PCHA_2 , the Triangle inequality condition need not be satisfied and the results that are got are better than 3/2 of the optimum solution length.

This PHP program finds the 'polynomial time' heuristic solution to the Travelling Salesman Problem for a 'Complete' graph using a database, so that data does not have to be typed in always.

This is a general heuristic program in 'PHP' for solving the Travelling Salesman Problem for any number of vertices.

The input data during the execution of the program is only the name of each vertex and the weight of each edge present in the graph.

( PLEASE NOTE :- If for an example graph, if there is no edge between two vertices, then assign a weight to the imaginary edge connecting the two vertices. The weight can be equal to the sum of the weights of all the real edges present in the example graph. This imaginary edge with a weight is necessary because of the condition that this program works on 'Complete' graphs only. A 'Complete' graph is the exactly the same mathematical object used in Graph Theory. Also please note that no edge in the example graph should have a weight of 0. )

To work with PHP files , 'XAMPP' Web Server has to be installed in the Computer. 'XAMPP' Web Server is available on the internet.

After installing XAMPP and when XAMPP Web Server is running , it is better not to connect to the internet , because of 'XAMPP' itself being a Web Server and so when XAMPP is running and if the computer is connected to the internet, other insecure connections can become connected to the computer. So as far as possible, once XAMPP is fully installed , and before starting to run XAMPP, it is better to disconnect the computer from the internet. After php program has finished executing, and Apache and Mysql has been stopped from the XAMPP control panel , and when XAMPP has been quit completely, then the computer can be connected to the internet.

The site from where data for the example tables is taken is 'https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html'. The website contains bigger data problems which can be used as input data when running this program.

Name of datasets and their correct minimum weights according to website are as given below.
1) DANTZIG42 ( Dataset of 42 vertices ). Correct minimum weight according to website equals 699.
2) FRI26 ( 26 vertices ). Correct minimum weight is 937.
3) GR17 ( 17 vertices ). Correct minimum weight is 2085.
4) PO1 ( 15 vertices ). Correct minimum weight is 291.

I am giving below the results of the program execution that I had obtained while running 'PCHA_2'. The results consists of the dataset name, the minimum weight obtained by 'PCHA_2' and the time taken for 'PCHA_2' to execute. I executed 'PCHA_2' on a Toshiba Satellite C640 Notebook computer. The results are as given below.
1) DANTZIG42 ( 42 vertices ). Minumum weight obtained is 846. Time taken is 1 second.
2) FRI26 ( 26 vertices ). Minimum weight is 974. Time taken is 1 second.
3) GR17 ( 17 vertices ). Minimum weight is 2155. Time taken is 1 second.
4) PO1 ( 15 vertices ). Minimum weight is 291. Time taken is 1 second.


Important details about database program

In this program , a 'Mysql' database is used , so that input need not always be typed in when executing the program. There are four php files which contain the php code for executing the program with a database. 'tsp_1_db_PCHA_2.php' , 'tsp_2_db_PCHA_2.php' , 'tsp_3_db_PCHA_2.php' and 'tsp_4_db_PCHA_2.php' are the four php files. The order of execution of the php files is 'tsp_1_db_PCHA_2.php' , 'tsp_2_db_PCHA_2.php' , 'tsp_3_db_PCHA_2.php' and then 'tsp_4_db_PCHA_2.php'. The execution need only to be started from 'tsp_1_db_PCHA_2.php'.

The 'XAMPP' Web Server is used for executing the php files and for processing the table data present in the database. All the four 'php' files ( ie:- 'tsp_1_db_PCHA_2.php' , 'tsp_2_db_PCHA_2.php' , 'tsp_3_db_PCHA_2.php' and ' tsp_4_db_PCHA_2.php' ) can be put in 'C:\xampp\htdocs\tsp_programs' folder. The execution need only to be started from 'tsp_1_db_PCHA_2.php'.

The database file is 'tsp_tables.sql'. This file contains a 15 vertex, 17 vertex, 26 vertex and 42 vertex graph data. All the 4 graphs data is put in one file because in the forum only 5 files maximum is allowed to be submitted.

If any of the example tables is imported into the database , it should always be imported into the database named " tsp_data_for_program_database". The 'phpmyadmin' database interface can be used for importing the table sql files.

An example of a table is as follows. A table 'vertex_15' is present as an example of data of a fifteen vertex graph in the "tsp_vertex_15_table.sql" table. For running the example of a 'fifteen' vertex graph, the 'vertex_15' can be selected from the drop down list of the tables , when the file 'tsp_1_db_PCHA_2.php' is executed.

Also the format of the example tables in the database should be followed exactly for creating new example tables , otherwise the program will not work. An example of what is meant by format of the table, is that in the example table, there is no primary key column. So addition , deletion etc.. of data , while in phpmyadmin , cannot be done quickly on the tables, if changes need to be made on the data in the tables. So when creating a new table, create a temporary primary key column in order to quickly insert data into the example tables. After all the data has been entered into the example table, then the primary key column can be removed. ( Please note that a creation of a primary key column is not necessary and need only be created if data needs to be entered faster while working in phpmyadmin. )


Important properties of the PHP Program

The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

When a 33 vertex graph or a graph containing more than 33 vertices are given for processing to the program, errors showing 'undefined weights' and 'input values of 1000 exceeded' are given as output if the default value of the constant 'max_input_vars' in php is 1000.

In a 33 vertex graph, there are 1056 edges ( ie:- 33*32 = 1056 , since there are 33 vertices in the graph and there are 32 edges attached to each vertex ) or 1056 input values. 1056 is greater than 1000 and so the program will output an error since the number of input values exceed 1000.

For eg:- if a 50 vertex graph is to be processed, then there are 2450 edges ( ie:- 50*49 = 2450 , since there are 50 vertices in the graph and there are 49 edges attached to each vertex ) or 2450 input values. So 'max_input_vars' can be given a value higher than 2450 for eg:- 3000. So the 'max_input_vars' constant in php can be changed by uncommenting the line 'max_input_vars=1000' and giving a value of 'max_input_vars=3000' to the 'max_input_vars' constant.

The 'max_input_vars' constant can be found in 'php.ini' file which is present in 'C:/xampp/php' folder.

To verify if 'max_input_vars' has the required value, the function 'phpinfo()' can be typed in any empty php file and the file executed. This information displayed after execution of the 'phpinfo()' function will contain the value of 'max_input_vars' along with other information that the function will display.

Vertex names which are input into the program should begin with an english alphabet. The rest of the name should contain a combination of english alphabets or positive integer numbers or a combination of both english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

Each vertex name should be different from every other vertex name. No two or more vertices should have the same name.

Only positive numbers should be used for the weight values of the edges.

No edge should have a weight with a value of 0.

In "tsp_4_db_PCHA_2.php" , in line no 3 and line no 4, the following code is given. The code is as follows :-

Code Begin
ini_set('memory_limit', '1024M');
ini_set('max_execution_time', 10800);
Code End

( Note:- 'Code Begin' and 'Code End' are just markers to show the beginning and the ending of the code. )

The above code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default value given in php. To prevent this, the code 'ini_set('max_execution_time', 10800);' is given.

Also for the code given below as
Code Begin
'<?php
session_start();
?>'
Code End
( which is present at the very beginning of a php file ) please note that there should not be a space or even an empty line above this code if any code modification is made in the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code (ie:- the code included between the single apostrophies ) is present at the very beginning of the code file, without even a single space preceeding this line of code.

[varghese]

Hello to All,

In the following posts, some notes may be repeated because it is given just in order to avoid confusion. Also I am splitting the notes as various posts, because the notes will not fit into one post and also only 5 files maximum are allowed to uploaded in each post.

[varghese]

This note is about a new general case polynomial time PHP program for finding the exact optimum minimum weight solution of the "Travelling Salesman Problem".

The new algorithm was developed in 'October 2017'. The new program was designed and constructed during the period of 'November 2017' to 'December 2017'. For short form, the name of this new program developed in the year 2017 as 'TSP_MWHC'. 'TSP_MWHC' means 'Travelling Salesman Problem Minimum Weight Hamilton Circuit'.

'TSP_MWHC' is 'not' supposed to be a heuristic algorithm. 'TSP_MWHC' is 'estimated' to be an O(n^{5}) algorithm ( The notation 'n^{m}' means 'n' raised to the power of 'm' ). 'TSP_MWHC' works for any number of cities.

A few quotes from the websites , which gives a reason as to how important this program is , even for 30 vertices graphs.

1) For the website address of 'http://www.math.uwaterloo.ca/tsp/methods/progress/progress.htm' , the quotation is given in 'QUOTE-1' in the 'QUOTATION SECTION'.

2) For the website address of 'https://wordplay.blogs.nytimes.com/2012/01/16/open-science-numberplay-style/' , the quotation is given in 'QUOTE-2' in the 'QUOTATION SECTION'.

The examples were tried on a 'TOSHIBA Satellite C640' laptop computer for the program.

The results of running the program on the examples , as given in 3 different websites , is given below.

In the website 'https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html' , the example of 'P01' for 15 vertices , the minimum weight of 291 as given in the website is also obtained by running the PHP Program. The time took was less than 1 second.

For the website of 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html' , the minimum weights are also given in the related website 'https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html'. The results of the program are as given below.

For the 'GEO' type coordinates, out of the 3 examples, 2 examples are giving lower value weights than the minimum weights given in the websites, but the minimum tours of the 2 examples are the same minimum tours as given in the website. So the rounding functions of PHP are giving different weight values for the 'GEO' type coordinates.

The 3 examples of 'GEO' coordinates are given below.

1) burma14 - The minimum weight of 3323 is obtained which is the same minimum weight as given in the website. The result was got using 'floor' function in php and 'burma14' has 'GEO' coordinates.

2) ulysses16 - The minimum weight as given in the website is 6859( I used the 'floor' function of PHP. I used the 'round' and the 'ceil' functions of PHP, but here also the result is of lower weight than the minimum weight given in the website and the tours of the program and the website are not the same. Using the 'floor' function gives the lowest weight of all the 3 rounding functions of PHP and it gives the same minimum tour as given in the website ). I am getting 6747 as the minimum weight using the 'floor' function. So it has something do with rounding functions that are used in PHP. Due to the rounding function's difference, the distances between the cities might be different than the original distances between cities as required by TSPLIB. But I have used the same formulas exactly as given in the TSPLIB documentation for calculating the distances between cities when 'GEO' type coordinates are given as input data.

3) ulysses22 - The minimum weight as given in the webiste is 7013. This example has the same problem as that of ulysses16 due to 'GEO' coordinates. The minimum weight given by the program is 6902 using the 'floor' function. But the minimum tour given by the program is the same as the minimum tour given in the website.


Below are the examples which have distances between the cities is already given in the website.

1) gr17 - The program got the same minimum weight as given in the website ie:- 2085. Time taken was 18 seconds.
2) gr21 - The program got the same minimum weight as given in the website ie:- 2707. Time taken was 1 minute and 20 seconds.
3) gr24 - The program got the same minimum weight as given in the website ie:- 1272. Time taken was 4 minutes and 20 seconds.
4) fri26 - The program got the same minimum weight as given in the website ie:- 937. Time taken was 4 minutes and 5 seconds.
5) bayg29 - The program got the same minimum weight as given in the website ie:- 1610. Time taken was 18 minutes and 27 seconds.
6) bays29 - The program got the same minimum weight as given in the website ie:- 2020. Time taken was 12 minutes and 3 seconds

In the website 'http://www.math.uwaterloo.ca/tsp/world/countries.html' , the example of 29 cities in Western Sahara , the minimum weight of 27603 as given in the website is also obtained while running the PHP Program. The time taken was 9 minutes and 25 seconds.

In TSPLIB , after 29 vertices, the next largest number of vertices is 42 vertices ( ie:- the graph of 'DANTZIG42' ). In the case of 42 vertices, during checking the intermediate output during testing, the result of 699 was shown as the minimum weight in less than an hour , but then the program continues to check if 699 is indeed the minimum weight. This checking took more than 45 minutes after the result of 699 was shown , so the execution of the program was cancelled. The testing of the 42 vertices example was done at the almost final stages of designing and constructing the program. So that is why I don't have accurate details of how much time it took to get the weight of 699. Because in the completed latest program , the program only shows the output after the program has completely stopped. A more powerful workstation computer is needed to check for vertices greater than 35 atleast , so that graphs with 50 or 100 vertices could be got within an hour or lesser time , since it takes a fairly longer amount of time if graphs of more than 35 vertices are executed on a laptop computer.

3) For the website address of 'https://en.wikipedia.org/wiki/Travelling_salesman_problem' , the quotation is given in 'QUOTE-3' in the 'QUOTATION SECTION'.

The above quote is for the comparison between other exact methods and 'TSP_MWHC' , in which 'TSP_MWHC' can be used for any number of cities and 'TSP_MWHC' does not use different methods for different number of cities.

Also a quote from the book 'Elements of Discrete Mathematics' by C.L.Liu. The ISBN of the book is '0-07-100544-7'. In the book in 'Chapter 5' titled 'Graphs and Planar Graphs' , in 'Section 5.8' titled 'The Travelling Salesman Problem' , in the footnote on page 160 , the quotation of the footnote is given as 'QUOTE-4' in the 'QUOTATION SECTION'.

The above quote is for the purpose of giving an idea of the benefit of using a more powerful workstation computer that will solve as an example , a 100 city problem within less than an hour, using the 'TSP_MWHC'.

A quote from the website of 'http://mathworld.wolfram.com/TravelingSalesmanProblem.html' is given in 'QUOTE-5' in the 'QUOTATION SECTION'. The quote says , that at the present time , there is 'no' 'general method' of solution for solving the Travelling Salesman Problem.


BEGINNING OF QUOTATION SECTION


QUOTE-1 :-
BEGINNING OF QUOTE-1.
" For anyone interested in solving large TSP instances, it is bitter news that in the forty years since Held and Karp no better guarantee has been found for the problem. (See the nice survey paper by Gerhard Woeginger.) This is disappointing since for n=30 the Held-Karp guarantee is already quite a large number, and for n=100 it is an impossibly large number to handle with today's computing platforms.

This lack of improvement in TSP guarantees may be something we cannot avoid; with current models of computing it may well be that there simply is no solution method for the TSP that comes with an attractive performance guarantee, say one of the form n^c for some fixed number c, that is, n x n x n ... x n, where n appears c times in the product. "
END OF QUOTE-1.


QUOTE-2 :-
BEGINNING OF QUOTE-2.
" Readers who do not have experience with the phenomenal numerical complexity of these problems may wonder why we can’t just use computer “brute-force” algorithms to examine all possible cases. That’s because there are far too many of them! Numerical combinations can quickly outpace Moore’s Law — or any kind of growth law in the physical world, giving numbers that are hyper-astronomical. Dr. Cook estimates that the world’s fastest computer would take about 28 trillion years to find the best solution on just a 33-city problem, and adds, “(this is) an uncomfortable amount of time, given that the universe is estimated to be only 14 billion years old.” "
END OF QUOTE-2.


QUOTE-3 :-
BEGINNING OF QUOTE-3.
"Exact algorithms

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute force search). The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities.

One of the earliest applications of dynamic programming is the Held–Karp algorithm that solves the problem in time O(n^{2}*2^{n}).

Improving these time bounds seems to be difficult. For example, it has not been determined whether an exact algorithm for TSP that runs in time O(1.9999^{n}) exists.

Other approaches include:

1) Various branch-and-bound algorithms, which can be used to process TSPs containing 40–60 cities.
2) Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 200 cities.
3) Implementations of branch-and-bound and problem-specific cut generation (branch-and-cut); this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see Applegate et al. (2006). "
END OF QUOTE-3.


QUOTE-4 :-
BEGINNING OF QUOTE-4.
" As the reader would immediately respond, it entirely depends on what we mean by an 'efficient procedure'. The efficiency of computation procedures is an important subject in theory of computation, which we shall study in Chap. 8. At this moment, let us just say that there is no known procedure that can solve the traveling salesman problem with more than several hundred cities with the use of a large-scale digital computer for a reasonable amount of time. "
END OF QUOTE-4.


QUOTE-5 :-
BEGINNING OF QUOTE-5.
"No general method of solution is known".
END OF QUOTE-5.


END OF QUOTATION SECTION