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. 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
Address :-
Haripad,
Alleppey District,
Kerala,
India.
Degree :- B.Tech ( Computer Science and Engineering )
Email :- purplesky1111@yahoo.com
