Step 2:-

Take se[b,e],sv{e}.

pc(se[b,e],sv{e}) = (b,e) = PC1(HC17)

pc(se[b,e],sv{e}) = (b,e,c) = PC2(HC17)

pc(se[b,e],sv{e}) = (b,e,c,d) = PC3(HC17)

pc(se[b,e],sv{e}) = (b,e,c,d,a) = PC4(HC17)

hc(se[b,e],sv{e}) = (b,e,c,d,a) = HC17

HC17 was formed by skipping the edges [a,e] and [a,c]

w(HC17)=5+8+6+7+14=40

Stage 4 :-

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

Taking all the hamilton circuits together, we get

HC1 = 40 ( ‘40’ is the weight of the hamilton circuit HC1 )

HC2 = 45

HC3 = 40

HC4 = 37 ( No edges were skipped for HC4 )

HC5 = 37

HC6 = 37 (No edges were skipped for HC6 )

HC7 = 37

HC8 = 37 ( No edges were skipped for HC8 )

HC9 = 44

HC10 = 46

HC11 = 37 ( No edges were skipped for HC11 )

HC12 = 40

HC14 = 45

HC15 = 51

HC16 = 37 ( No edges were skipped for HC16 )

HC17 = 40

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

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

End of First Example

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

This is the process in which the minimum weight starter edge fromCollection_1ofGraph1is taken.

Beginning of Second Example

Take se[b,e]

Step 1:-

Take se[b,e],sv{b}

pc(se[b,e],sv{b}) = (b,e) = PC1(HC18)

pc(se[b,e],sv{b}) = (c,b,e) = PC2(HC18)

pc(se[b,e],sv{b}) = (d,c,b,e) = PC3(HC18)

pc(se[b,e],sv{b}) = (a,d,c,b,e) = PC4(HC18)

hc(se[b,e],sv{b}) = (a,d,c,b,e) = HC18

No edges were skipped while forming HC18.

w(HC18)=5+9+6+7+10=37.

Since no lesser weight edges were skipped while forming HC18, the process is immediately stopped.

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

End of Second Example

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

Reference:-

1) " Elements of Discrete Mathematics " by C.L.Liu ( Second Edition )( ISBN of the book is 0-07-100544-7 ).

2) " A First Look at Graph Theory " by John Clark and Derek Allan Holton( ISBN of the book is 81-7023-463-8 ).

Samuel GhevergheseWritten by :-

Continued in "Travelling Salesman Problem - Part 6"