ABSTRACT

We single out the polygonal paths of order that solve each of the different longest non-cyclic Euclidean Hamiltonian path problems in networks by an arithmetic algorithm. As by product, the procedure determines the winding index of cyclic Hamiltonian polygonals on the vertices of a regular polygon.

1. Introduction

Our aim implies to determine the overall lengths of every Longest Euclidean Hamiltonian Path Problems and the composition and the orderings of the directed segments that accomplish these longest Hamiltonian travels. The identification regardless of planar rotation and orientation is done with the proposed algorithm [1-3].

This paper apart from the Introduction, Conclusion and References contains §2 Algorithm and Hamiltonian Paths in N_odd-Gons and §3 Maximum Hamiltonian Path Problems in N_odd-Gons. §2 formulates specific Max. Hamiltonian Problems and postulates the algorithm for their resolutions. §3 devoted to the solution of the

different Max. Traveling Salesman Path Problems in N_odd-Gons [4,5].

2. Algorithm and Hamiltonian Paths in N_odd-Gons

This work is focused in the resolution of the

different Maximum Traveling Salesman Path Problems of order with inicial point at and final point at for (see Figure 1) in the

networks. These structures are built by the complete graph on the odd regular polygon vertices, i.e., and weighted with the Euclidean distances between nodes [6].

2.1. Intrinsic Geometry and Arithmetic

Let be the points of the set and let them be clockwise enumerated by the integers modulo, , from the vertex. For each in

and each, let denote the segment that joins with, while denotes the one that joins to. From now onwards, and denote to and, respectively. Let be the diameter, it joins the vertex with its opposite, only if is even. and respectively designate the quasi-diameters if is odd (see Figure 1), [7].

If symbolizes a regular n-gon inscribed in the unitary circle and with vertices in, can be considered as the polygonal of sides [8]. From the vectorial interpretation of the segments, can be interpreted as the resultant of the polygonal of sides of, that joins clockwise to, while is the resultant of the polygonal of sides that joins clockwise to.

The segments and are the respective chords (or resultants) of the polygonals and consecutive sides of, whichever are the integers and. Therefore, it is natural to associate with the integer, and likewise with the integer.

Definition 2.1.1 For any integer, is a segment if for any, , and for any,

is equal to or.

Definition 2.1.2 If is an segment, the integer associated to, noted as, is given by:

Definition 2.1.3 If is a sequence of segments, the integer associated to the path evolved by, is given by.

It should be taken into account the following facts:

• The consecutive collocation of two segments from any vertex determines the vertex that corresponds to collocate, from and in clockwise, as many sides of as correspond to the sum of the integers associated to each one of the two segments. In other words, the resultant of a polygonal built by two segments, is other segment and its associated integer is the sum (modulo) of the integers associated to the components of the polygonal.

• The segment is by considering any fixed value of, when. Otherwise, if, is.

The concept of the associated integer and its addition modulo, deploy the following geometric correlate over the set of vertices: For each, , the geometric place that corresponds to the vertex coincides with the place that corresponds to, for each integer. Since the segments and respectively connect the

vertices to and to, it is clear that for any integer between 0 and, the vertices

and are symmetric with respect to the horizontal axis. Given a sequence of segments, henceforward the polygonal that they determine is in a oneto-one relationship with the sum of each one of these directed segments that belong to the sequence.  

Since, whichever and are, without loss of generality in the sequences of segments, the second subindices of these directed segments are rooted out.

2.2. Resuming the Algorithm

Lemma 2.6 and Theorem 2.7 in [1] detail the proofs of the following algorithmic statements.

Theorem 2.2.1 The pathway determined by a sequence of segments starts and ends at the same vertex if and only if.

Theorem 2.2.2 A sequence of segments determines a Euclidean Hamiltonian cycle of order if and only if any proper subsequence of order has associated integer neither nor a multiple of and.

Corollary 2.2.1 A sequence of segments of order, , building a Euclidean closed polygonal in networks, passing once through certain or all vertices, has.

Since, is a multiple of exists less than or equal to which counts the times that cw.

winds around the geometric centre of. We named this specific integer as the “winding index”.

2.3. Applications of the Algorithm: Winding Index in Special Cyclic Paths in N_odd-Gons

Let symbolize a cyclic polygonal in

network, which does not repeat vertices, with the exception of the first and the last one, and which passes through certain nodes,. Specially, stands for Euclidean Hamiltonian cycles in network.

Exampe 2.1. Let . If does not divide they are s of winding index

[9].: is the Max TSP [10].

Exampe 2.2. Let

.

The angular cw. avance is proportional to:

then is the winding index. Algorithmic computations render that these cycles are and for networks built on. For

the algorithm prompts

as winding index and singled out them as and

if. In,

, the algorithm characterizes these cycles as in with winding index.

Exampe 2.3. Table 1 deploys cycles living in

.

Exampe 2.4. Table 2 shows Euclidean Hamiltonian cycles in special networks.

3. Maximum Hamiltonian Path Problems in N_odd-Gons

In network forwe study the trajectories built by a single segmentTable 1. in.

Table 2. in.

directed segments, and

directed segments, that is (1).

3.1. Lengths of Relevant Pathways

Our present concern is to study the Euclidean lengths and the composition of the directed segments that build the trajectories given by (1). 

(1)

Since for the lengths of the segments

, verify the following relationships:

Therefore, the overall traveled Euclidean lengths of the pathways (1) are given by: 

(2)

Therein, precisely we focusing on the Euclidean Hamiltonian cycles, s, which accomplish the lengths

(2) in network.

Next Theorem establishes the composition of the directed segments that give birth to the sequences with overall traveled lengths (2).

Theorem 3.1.1 The overall traveled lengths (2) in

are accomplished for any sequence built by a single,

, , and directed segments if and if the conditions in (3) are satisfied.

(3)

Proof

From the constraints and

follows

should be and hence

. Therefore, the admissible couples for the lengths (2) should verified (3). □

Backward recurrence over the traveled length in steepest descent steps from the max to constraint and the lack of Hamiltonian cycles for

state that (4) is the Euclidean Hamiltonian Maximum Path length when is rooted out. 

(4)

3.2. Specific Directed Segments for the Max. Traveling Salesman Path Problems in N_odd-Gons

We confirm in Theorem (3.3.1), Theorem (3.3.2) and Theorem (3.3.3) the existence of Euclidean Hamiltonian cycles that attain the overall Euclidean lengths given by the sequences (1) and the assignments (3).  

1) For if and in

(3) exists s with overall traveled length (2). See Theorem (3.3.1) at pg. 4.

2) For

a) in (3) exists s with whole traveled length (2). See Theorem (3.3.2) at pg. 5b) and in (3) exists s with whole traveled length (2). See Theorem (3.3.3) at pg. 5.

3.3. Orderings of the Directed Segments for the Max. Traveling Salesman Paths in N_odd-Gons

symbolizes any Euclidean Hamiltonian path that resolves the Max Traveling Salesman Path Problems with initial vertex and final vertex, that is whichever be the bridge, forbetween the starting and ending points.

Observation 3.1 Proofs of Theorem 3.3.1, Theorem 3.3.2 and Theorem 3.3.3 result from direct application of Theorem 2.2.2 of the proposed algorithm.

Theorem 3.3.1 Let an odd integer for. The pathways (5) and (6) build

s in networks if

.

(5)

(6)

for. □

Let and denote, respectively, the forward and backward readings of any sequence of segments.

Corollary 3.3.1 In

networks if, forward and backward readings of the sequences (5) and (6) are.

Consequently, and of the sequence (5) and

(6) account for 2 plus to distinct sequencesrespectively. Furthermore, and of the pathway (5) and paths (6) build s if the directed segment is initially appended to these sequences. □

Theorem 3.3.2 Let an even integer for. The pathways (7) and (8) build s in networks if, with is the number of and, respectively.

(7)

(8)

for □

Corollary 3.3.2 In networks if, forward and backward readings of the sequences (7) and (8) are. Particularly, the enumeration of the distinct s given birth from the forward and backward readings of the sequences (8) depend on the evenness. Specifically1) If is odd, since

every sequence in (8) is not a palindrome [1]. Moreoverthe sequences defined in (8) are in couples and Specifically, the path

determined by coincides to path

determined by, path coincides with of the sequence defined by

and so on. That is the paths defined by (8) with coincide with the

paths determined by (8) with

.

Therefore, exists distinct s which correspond with each one of the determined by (8). Since of (7) is different to its, both

s should be added to the final enumeration. In conclusion, the distinct s are.

2) If is even, since, then this index in (8) builds a which is a palindrome [1]. In addition,

paths defined by (8) with coincide with the paths determined by (8) with

. Therefore, exists

distinct s which correspond with each one of paths determined by (8). Since

of (7) is different to its, both s should be added to the final enumeration. In conclusion, the distinct

s are. □

Theorem 3.3.3 Let an even integer for. The pathways (9) build s in networks if

, meanwhile is the number of and the amount of.

(9)

for. □

Corollary 3.3.3 In networks if, forward and backward readings of the sequences (9) are s. Particularly, the enumeration of the distinct s given birth from the forward and backward readings of the sequences (9)

depend on the evenness. Specifically, 

1) If is odd, i.e. is even, then, therefore the sequence in (9) build by this index is a palindrome [1]. Moreover, sequences defined in (9) are in couples and with the exception of that given birth by the index which its

and is exactly the same pathway at all.

Specifically, the path determined by

coincides to path determined by

, path coincides with

of the sequence defined by and so on, until the index at which

and beget only one path. That is the paths defined by (9) with the downgraded indexes

coincide with the

paths determined by (9) with

.

In conclusion, exists distinct s which correspond with each one of the path determined by (9).

2) If is even, i.e. is odd, since, then sequences (9) build s none of them are palindrome [1]. In addition,

paths of the indexes coincides with

paths of the downgraded indexes

, respectively. In conclusion, exists distinct s vis-à-vis with each one of the path determined by (9). □

Observation 3.2 Corollary 3.3.1, Corollary 3.3.2 and  Corollary 3.3.3 result from Theorem 3.3.1, Theorem 3.3.2 and Theorem 3.3.3, respectively.

In conclusion, the s which resolve the Max.

Euclidean Hamiltonian Path Problems with the

as the bridge between the endings of the Hamiltonian paths are evolved by the sequences (5) and (6) if. Otherwise by the orderings (7)-(9). Moreover, with the exception of the palindromes their backward readings also resolve these specific Max. Traveling Salesman Problems.

3.4. Bicoupled N_odd-Gons TSP Conjeture

We choose the geometric paths that start up at of the quasi-spherical mirror of unitary radius, touch times-including the last touchinganywhere on the hollowed mirror, and end up at, with In this geometry each array of angles, see Figure 2, denoted, determines a path with verticesincluding the initial and arrival pointsand linear branches, [8,11,12]. This path may have two or more coincident vertices and linear branches shrunk to a point. For each the angles are selected (see Figure 2) as independent variables of the overall traveled length function of the paths.

The length of the geometric path determined by, is given by (10) 

(10)

When, , for any polygonal cyclic trajectory, there is an -array which characterizes them. In particular, amongst these pathways are those that have as vertices the points, with See [10] Theorem 2.1.1. and Appendix A, from page 78 to 80 [8]. Let 

(11)

be a generalized length of (10), where are the analogous angular parameters with the restraints and, and in is the structural parameter for the locations of the coupled vertices of the inner -polygon,

networks [3].

Herein, see Figure 3, we pose the following conjeture: Are Max. TSPs in bilayer

networks baited for the regular shapes of the Max. TSP in networks?

4. Conclusion

This paper is an offspring of a series of previous works about Hamiltonian maximum overall traveled lengths in

networks. Herein are singled out all the Euclidean Hamiltonian pathways that resolve

the different maximum traveled Hamiltonian paths of order in

networks. As a by-product the proposed algorithm allow us to determine the winding index of specific cyclic polygonals. The approach is a step forward on the intrinsic geometry and inherent arithmetic of the vertex locus of the N_odd-Gons.

REFERENCES