So when the nearest neighbour method is done, the process is O(1)
varghese wrote: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.
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 ).
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 ).
Users browsing this forum: No registered users and 4 guests