Math Words and Their Dendrograms

Abstract

A hierarchical clustering algorithm based on graph theory is presented, which, from generation of a path from a given vertex, builds a math word and calculates clusterization under an index. This is possible due to modification of Tarry’s algorithm, through exchange of path elements. The unidimensional clustering index applied to σ gives us what I have called Tarry’s hierarchy. From the definition of net word, cycle, tree, tree word, and vertex, a theorem on the relationship between vertices, lines, and letters of a labyrinth is shown, which allows the generation of words and their dendrograms with the application of the Euclidean distance. Practical use of these concepts provides possibilities of connections in arrangements for telephone centrals and robotic arms’ paths.

1. Introduction

The first person to study the combinatory properties of schemes was Leonard Euler in 1736, who studied the network of the seven bridges in Königsberg, and he wrote in Berlin 1739 “in Königsberg Pomeranie, they have a little island named Kneiphof, the river is divided by two and around the island seven bridges. You can arrange a network where you walk only one over in one time”. And Euler continues, “this is possible for every one and impossible for others, but anyone has the certitude” [1].

The modern theorem enunciated by Euler demonstrated that the necessity of the parity of the valence in every vertex is a theorem: A connexe graphic is eulerienne if all vertex has degree pair. Till date, the graphic theory has developed slowly but steadily. The principal contributors of this theory are Tarry [2, 3], Konig [4], Berge [5], Tutte [6], Bollobas [7], and Rosenstielh [8, 9, 10]. Recent works on graph theory are those of Bourdin et al. [11] and Gondran and Minoux [12]. The randomized Tarry algorithm is used in searching a graph of Urretabizkaya and Rodríguez 2004 [13] as they implement the Tarry algorithm for solving mazes of known structure. The graph theory is used in branches of mathematics like theory of groups, topology, theory of numbers, data analysis, and clusters. Among those who have contributed the most to the development of theory and models in telephone connections are Erlang, who implemented the well‐known Erlang Probability Density Function, and his published works of 1917 and 1918 [14], and Elldin [15]. More recent contributors to this theorem are Ahuja et al. [16] and Mateus et al. [17].

As a starting point, let us see some graph theory definitions and concepts used in the generation of modification made to Tarry’s algorithm, as well as the definition of applied distance, called minimum ultrametric distance in the application of Tarry’s modified algorithm on telephone centrals arrangements. In the development of application, a theorem on the relationship between the maximum number of lines in a geometrical arrangement with n vertices and k letters is shown and demonstrated, which is made with the method known as mathematical induction.

2. Definitions and algorithms

Definition. One graphic is a couple G = (X, U), where X is a finite set, of edges of G, each element of which is incident to two elements of another finite set V, named the set of vertices [5].

Definition. A labyrinth $\mathcal{L}$ is a finite set A non‐empty and of pair cardinality, named set of words of $\mathcal{L}$ or alphabet, supplied of one involution l without an indeterminate point (i.e., without a tendency change) called by the prime operator:

$$l\in \text{A then }l’\in \text{A, }l’\ne l\text{and (}l’\text{)}’=l$$E1

And one equivalence relation (named “with the same right than” where the classes are “the points” of labyrinth, the letters of same class have the same right as the point) indicated by the application of the letters which belongs to the letters in the set X of class:

$$\text{d: A }\to \text{ X : d(}l\text{) = d(}k\text{)}$$E2

By < the right of l is equal to right of k >, where < l has the same right as that of k > [9].

It is possible to speak of the left of letter too, making: g: A —→ X with g(l) = d(l’) ∀ l∈A, as far as the labyrinth expressed by triad (A, i, d).

Definition. One labyrinth (A, i, d) is said to be orientated, if it exists one part A⁺ of A such that:

$$l\in {\text{A}}^{\text{+}}\iff l’\notin {\text{A}}^{\text{+}}\forall l\in \text{A}$$E3

Definition. Given a labyrinth (A⁺, i, d), σ is called a word of this labyrinth if it belongs to some of following classes:

• Δ_α ∀ α ∈ X is called empty words of $\mathcal{L}$

• l with l ∈ A is called word letter of the $\mathcal{L}$, and

• σ = l₁,.., l_r, l_r+1,…, l_p with l_r ∈ A ∪ (Δ_α) ∀ α ∈ X, we have d(l_r) = g(l_r+1) ∀ r = 1,.., p‐1

Therefore, let X be the set of vertex, you can have lefts and rights applications in all words of the labyrinth $\mathcal{L}$ defined as d, g: A ∪ (Δ_x)_x∈X → X or d, g: $\mathcal{L}$ → X with g(Δ_x) = g(l₁) and d(Δ_x) = d(l_p), i.e., g(Δ_x) = d(Δ_x) = x. And remember, σ is cyclical if g(σ) = d(σ). To continue the definitions of tree, pure word, and neutral word, see Refs. [7, 18].

Definition. One tree A is a graph G = (X, U) connected and noncyclical.

Let us see below how to materialize the above definitions. Given is the structure of a labyrinth oriented L: A⁺ ${{\displaystyle \cup }}^{\text{}}$A⁻, Figure 1, where sets of letters A⁺ and A⁻ are defined as $A^{+}= {\displaystyle \left\{a b e f i j cd g h k l\right\}}$ and $A^{-}= {\displaystyle \left\{a´ b´ e´ f´ i´ j´ c´ d´ g´ h´ k´ l´\right\}}$. In addition, the vertex set of L is $X= {\displaystyle \left\{\alpha \beta ϵ \gamma \lambda \delta \zeta \eta \xi \right\}}$. It must be taken into account that L is the application of labyrinth and L is the labyrinth which, in this case, is the union of a finite set A⁺ ≠ ɸ, with direction toward the right, and a finite set A⁻ ≠ ɸ, with direction toward the left, and X is the vertex set of the labyrinth.

Figure 1.

Oriented labyrinth.

A line of $\mathcal{L}$ would be ${\displaystyle \left\{a a´\right\}}$ ⊂ U_{$\mathcal{L}$}, with U_{$\mathcal{L}$} being the set of lines of $\mathcal{L}$. Some words of $\mathcal{L}$ with ${\Delta }_{\alpha }$ being the empty word are ${\displaystyle \left\{e f j i\right\}}, {\displaystyle \left\{a´ b´ f g\right\}}, {\displaystyle \left\{g d f´ i´ j´\right\}}, \text{and }{\displaystyle \left\{{\Delta }_{\alpha }e\right\}}$. Cardinality of $\mathcal{L}$ is as follows:

$${\text{Card L = Card A = Card(A}}^{\text{+}}\cup {\text{A}}^{-}{\text{) = Card A}}^{\text{+}}+{\text{Card A}}^{-}=12+12=24$$E4

A net word would be $\sigma = {\displaystyle \left\{e f j i b a a´ b´ i´ j´ g h l k d c c´ d´ k´ l´ h´ g´ f´ e´\right\}}$, and right and left applications of σ are, respectively, as follows:

$$d{\displaystyle \left(\sigma \right)}= {\displaystyle \left\{e f g h l k d c j i b a\right\}} and d´{\displaystyle \left(\sigma \right)}= {\displaystyle \left\{a´ b´ i´ j´ c´ d´ k´ l´ h´ g´ f´ e´\right\}}$$E5

It must be noticed that σ is cyclic: d(σ) = g(σ) with g(σ) = g(a) = a’ and d(σ) = d(e) = e. We may also build a tree A₀, Figure 2, a tree net word and its dendrogramatic relationship. The hierarchical relationships that shall be seen are classifications with an aggregation criterion in accordance with the oriented path of the labyrinth under analysis.

Figure 2.

Tree A₀ of labyrinth oriented $\mathcal{L}$.

It must be noticed that the word created based on the tree built is cyclic and its hierarchy does not exist, since it is nested (Figure 3a). Such nesting means that there is no aggregation criterion among the letters of the labyrinth alphabet (Figure 3b).

Figure 3.

(a) Word created after tree A₀ (Figure 2), and (b) free aggregation criteria.

From labyrinth of Figure 1, we may build another tree and another tree net word, as shown in Figures 4a, b. The net word of tree A₁, Figure 5a, and his free aggregation criteria, Figure 5b, is as follows:

Figure 4.

(a) Tree and (b) tree net word.

Figure 5.

(a) The net word created after tree A₀ (Figure 4a) and (b) free aggregation criteria.

The new σ word is not completely cyclic, but even then, a hierarchy for such may not be built, since it is, mostly, nested.

Definition. If σ of $\mathcal{L}$ = (A, i, d), it is a pure word if inside σ exists an occurrence of each letter of A.

Definition. If σ ∈ $\mathcal{L}$ and σ ≈ Δ_α ∀ α ∈ X, σ is called neutral word in α if the neutral element Δ_α is a neutral word in some α‐particular.

2.1. Algorithm of Tarry

Definition. Let $\mathcal{L}$ labyrinth be connected, we say Tarry’s word of $\mathcal{L}$ all pure word Θ ∈ $\mathcal{L}$ such that the entry tree V of Θ and the out tree W of Θ are opposites, i.e., W = V’.

Let L be the lexical of connected labyrinth $\mathcal{L}$ = (A, i, g), with l₁ ∈ A. Let V(σ) be the entry tree of σ with σ a left factor of Tarry’s word Θ to apply the following algorithm (Figure 6) [3]:

Figure 6.

Graphic labyrinth of Tarry.

Note: The contrary of all entry letter is an out letter in Θ = σ, cause Θ is a cyclical word, and all letter of A has the same right than the same left of Θ [19].

2.2. Attachment index

With the classification level of ways connected or paths of labyrinth $\mathcal{L}$, they begin with the first cycle or pleat of the Tarry’s word. In this case, the index level is unit. When the Tarry’s word σ is formed, you have to replace σ, writing always in first place the first obtained cycle.

Definition. Let two paths l₁ and l₂ ∈ $\mathcal{L}$ and let α all letters with the same left g(Θ) and β all letter with the same right d(Θ), the minimal distance d_M or the inferior ultra‐metric minimal distance over a point x₀ ∈ l₁ and x₁ ∈ l₂ is d_M(l₁, l₂) = min {d(x₀, x₁) | x₀∈ l₁ & x₁∈ l₂}

Remember, the algorithm is applied after finding the Tarry’s word and his cluster by couples or pleats. To finish the last pleat, begin the letter’s arrangement in σ. You must begin with the first pleat.

2.3. Tarry’s algorithm in pseudocode

In order to describe briefly the operative principle of modified Tarry’s algorithm, its procedure is shown below in pseudocode, where, based on which, one may develop it in a programming language under conventional programming.

//In Tarry’s algorithm, there is the eventuality to go beyond this point to the first step if, by $L$’s own nature, there is no other way to construction of Tarry’s word, thus making a truncated Tarry’s word//

End of Procedure

2.4. Application in basic telephone centrals arrangements

One of the great problems in telephony is to calculate telephone traffic increase, which allows designing telephone centrals and calculating the number of lines which shall satisfy the demand. Let us take the real case of Figure 7 and apply the theory referred to above in order to obtain Tarry’s trees, words, dendrograms, or clustering for optimal connection paths. If we take only the lowest part of Figure 7 (telephone centrals and area centrals, Figure 8), the $\mathcal{L}$ labyrinth may be built:

Figure 7.

Basic arrangement diagrams between telephone centrals.

$$\mathcal{L}\text{=}\{a,b,d,e,a’,c\text{,}b’,c’,d’,e’\}$$E6

The number of trunks or telephone lines is m = 5, and the number of letters is 2m = 10. If x₀∈X and {a, a'} ⊂ A, the net word of Figure 8 is obtained. Figure 9 is the net word of the $\mathcal{L}$ labyrinth:

Figure 8.

Tree diagrams of connections between telephone centrals and area centrals.

Figure 9.

Net word of labyrinth.

Thus, seven trees related to vertex x₀ are obtained. To every tree corresponds one or several words (net, neutral, or Tarry’s). Every tree thus built has 4 vertices, 5 lines and 10 letters. Figure 10 shows all the trees related to x₀ vertex. It must be remembered that the same trees may be found in every vertex different from x₀.

Figure 10.

Trees, words, letters, and dendrograms of vertex x₀ in our basic arrangement between telephone centrals.

Definition. A graphic G = (X, U), such that (x, y) ∈ U ⇒ (y, x) ∈ U is said to be symmetrical.

Based on the above definition, a telephone communications network is a symmetrical graphic, since every pair of terminals or adjacent vertices is linked in two directions.

Theorem. Let n be the number of vertices; m the maximum number of lines; and k the number of letters. If loops are not considered and we only study triangular geometrical arrangements, the relationship on the maximum number of m lines in a set of n vertices and k letters is:

$$n\le m=\frac{(n-1)n}{2}\le 2m=k\forall n>2$$E7

Demonstration. This algorithm shall be demonstrated through the induction mathematical concept (tested for one, supposed for n, and tested for n+1).

If n = 1, there is no labyrinth. If n = 2, then $m=\frac{{\displaystyle \left(n-1\right)}n}{2}=1$ and k = 2. In this case, there is only one line in two directions (⇆). Let us suppose that n = n, then:

$$n\le m=\frac{(n-1)n}{2}\le 2m=k\forall n>2$$E8

If we ask if this is valid for n = n+1. Then

$$\begin{array}{l}n+1\le m=\frac{(n+1-1)(n+1)}{2}\le 2m=k\\ n+1\le m=\frac{n(n+1)}{2}=\frac{(n^2+n)}{2}\le 2m=\frac{2(n^2+n)}{2}=n^2+n=k\\ n+1\le m=\frac{(n^2+n)}{2}\le 2m=n^2+n=k\\ n\le {\displaystyle \left[\frac{(n^2+n)}{2}\right]}-1\le m=n^2+n-1=k\end{array}$$E9

that is, the number of vertices ≤ maximum number of lines ≤ number of letters, which complies with the theorem.

From our example:

$$\begin{array}{l}\text{if }n=2\text{then }n=2\le m=\frac{n(n-1)}{2}=\frac{2(2-1)}{2}=\frac{2}{2}=1\le 2m=2\ast 1=2=k\\ \text{if }n=3\text{then }n=3\le m=\frac{n(n-1)}{2}=\frac{3(3-1)}{2}=\frac{6}{2}=3\le 2m=2\ast 3=6=k\\ \text{if }n=4\text{then }n=4\le m=\frac{n(n-1)}{2}=\frac{4(4-1)}{2}=\frac{12}{2}=6\le 2m=2\ast 6=12=k\end{array}$$E10

When we apply the hierarchical distances geometrical theory [20] to build the tree or dendrogram of the labyrinth net word, Figure 11, hierarchical geometry shown is a starting sequence of isosceles triangles crowned by a sequence of scalene triangles. Partial hierarchies show a monotonous series, and in the following selection of classes to be added, there are always partial hierarchies corresponding to a primary telephonic connection. As for dendrograms of every word built based on vertex x₀, Figure 12, it may be seen that the hierarchy does not change for each tree. Their geometry is identical for each different mathematical word obtained from the labyrinth.

Figure 11.

Dendrogram of the labyrinth’s net word.

Figure 12.

Hierarchical structure of tree, words, and dendrograms of vertex x₀.

Based on construction of dendrograms, the values of fractal dimension, its standard deviation, and que regression line equation have been obtained (Table 1). In the last column, the table shows to graphs: that of the fractal of the peak of the dendrogram and the geometrical structure of the hierarchy. Obtained values have been corroborated using Software Benoit 1.3 [21]. It must be considered that σ measures probability that an observation is at a certain distance from average observation, and it is valid if system under analysis is random.

Table 1.

Fractals of dendrogramatic labyrinth’s math words.

Let us now talk about the polygonal case of the labyrinth’s net word, as well as that representing all the trees, words, and dendrograms of vertex x₀, showing the sequence of variables incorporations into the hierarchical analysis developed. It must be considered that figures in Table 1 are not at the same hierarchical scale. In the first one, case in which the dendrogram built is only for the labyrinth’s net word, the polygonal sketches the trend of the final structure of each basic arrangement between telephone centrals, which is, in this case, the generator of fractal curves characterizing the dendrograms for each communication path between telephone centrals.

The segments of the generator are built linearly from the base of the class to the terminal point of a higher class, so that the sequence of such set of classes is conceptually defining part of the behavior of the net word’s letters. The fractal’s generator defines the characteristic of data under study, which in fact gives value to the construction of the hierarchical dendrograms [22].

The first four columns of Table 1 register the names of the fractal dimension’s estimation methods, with the value obtained for standard deviation and the regression equation obtained by such method. Since it is a well‐known theory, the description of such is not described in detail [23, 24, 25]. The last column, as described above, shows the fractal and its geometrical structure.

2.5. Application to industrial robots’ paths

From the point of view of robotics, a robot is the technique applying informatics to design and use of equipment which, instead of people, carries out operations or tasks, generally, in industrial facilities. There is the problem of controlling kinematic and dynamic models. To define the movement of a robot implies controlling such in order that it may follow a pre‐planned path. Therefore, the objective is to establish which are the paths to be followed by every articulation of the robot in time in order to achieve the objectives established, as well as it is required to comply with a series of physical restrictions imposed by actuators and the quality of the path, such as smoothness and precision.

In order to make an animation of a rotational robot with x‐degrees of freedom, a simple planning of the path to be followed by the robot must be made, taking into account the actuators, so that the movement of the robot may be smooth and coordinated. The types of paths of industrial robots currently are as follows: point‐to‐point path, coordinated or isochrone path, and continuous paths. For 3D paths, related to 2D paths, the versatility of inverse kinematics and dimensions of existing algorithms are different.

Let us consider now an industrial robot making a complex set of paths in three dimensions to assemble a device, as shown in Figure 13. Here, the oriented path set for the mechanic arm and the points, in our case vertices, where such shall implant an element or component of the system being assembled are shown. Treatment of the path under the theory shown is as follows:

Figure 13.

Robot with ellipsoidal‐oriented paths.

It must be said that through desired paths generated by a specific function, it must be segmented into enough points to describe follow‐up on the path made by the robot manipulator. Thus, high accuracy may be achieved; however, the search process extends the convergence time of algorithms. This is also true for traditional numerical solutions, such as Newton‐Raphson’s, since it has a small differential step.

The sets of letters are: direction toward the right A⁺ = {a b c d e f g}, direction toward the left A^‐ = {a’ b’ c’ d’ e’ f’ g’}, and that of vertices of $\mathcal{L}$ is $X= {\displaystyle \left\{x_0, x_1, x_2, x_3, x_4\right\}}$. Figure 14 shows the non‐neural Tarry’s labyrinth word diagram. Therefore, a Tarry’s word to see the circular permutations of letters and vertices is:

Figure 14.

Non‐neutral Tarry’s labyrinth word diagram.

Word Θ built is, evidently, nonneural (Figure 15). Its diagram is shown in Figure 16a, but almost always another word may be built, Figure 16b, which is hierarchical:

Figure 15.

Word Θ non‐neural.

Figure 16.

(a) Non‐neural word of labyrinth $\mathcal{L}$ (Figure 13) and (b) neural non‐Tarry’s word.

Word Θ built is neutral but not Tarry’s, since its folding into e does not allow it to be so. Its diagram is shown in Figure 17.

Figure 17.

Neutral non‐Tarry’s Θ word diagram.

In this example, the informatics algorithms defining the paths of a robotic arm are related to the work cycles and co‐cycles of their industrial task or partial graphics of the paths. This duality between cycles and co‐cycles is extended to the concept of tree. Figure 18 shows the graphic representation of entrance‐exit or right‐left trees. Based on labyrinth oriented $\mathcal{L}$, Figure 13, let us build a new μ Tarry’s word, as well as its hierarchical relationship (Figure 19). Figure 20 shows its diagram.

Definition of cocycle. A cocycle of vertex x ∈ G is the addition of every w(x) edge where an end is vertex x.

Figure 18.

Θ’s entrance and exit trees.

Figure 19.

(a) μ Tarry’s word form (Figure 17) and (b) its hierarchical relationship.

Figure 20.

μ Tarry’s word diagram.

Based on labyrinth‐oriented $\mathcal{L}$ described in Figure 13, a new ξ Tarry’s word and its hierarchical relationship are built, which diagram is shown in Figure 21.

Figure 21.

ξ Tarry’s word diagram.

Inside an $\mathcal{L}$ labyrinth, it is possible to make permutations of letters (it had already been done here, but it had not been explained), as well as of lines, and vertices, respectively. If the labyrinth is connected, it is possible to make permutations of elements already mentioned, but in a circular manner.

Definition. A circular transformation in a connected labyrinth is a substitution of the order of letters, lines, or points with another order, without negatively affecting the nature of such labyrinth.

Let k ≥ 0 and Φ: A → U the application that relates every letter to the corresponding line or arch in labyrinth $\mathcal{L}$, where U is the family of arcs. Therefore, it is said that (i) two letters m₁ and m₂ are k‐adjacent if there is a word of $\mathcal{L}$ with less than k + 2 occurrences of letters, where the first word is m₁ and the second word is m₂. (ii) The sets of words A₁ and A₂ are k‐adjacent if there are two letters k‐adjacent m₁ and m₂, such that Φ(m₁) = A₁ and Φ(m₂) = A₂ and (iii) two vertices x₁ and x₂ are k‐adjacent if there are two letters, also k‐adjacent, m₁ and m₂, such that x₁ = g(m₁) and x₂ = g(m₂).

Based on the above, let us now keep only the odd rank letters of word ξ

$$\xi =\{\text{d}\text{e}\text{a}\text{'}\text{b}\text{c}\text{'}\text{f}\text{'}\text{g}\text{'}\}={\text{p}}_{\text{1}}$$E11

Word ξ or p₀ is a circular permutation of letters with 0‐adjacenty, that is, k = 0. ξ in p₁ is a circular permutation of lines with 1‐adjacency (Figure 22). Using the entrance tree, Figure 18, the ξ word of the corresponding entrance tree is shown in Figure 23a and its hierarchical relationship in Figure 23b.

Figure 22.

(a) New ξ Tarry’s word form (Figure 21) and (b) its hierarchical relationship.

Figure 23.

(a) The =ξ word of the corresponding entrance tree and (b) its hierarchical relationship.

Keeping from ξ the odd rank letters and relating each of them to a vertex, in accordance with the rule, we obtain:

$${\text{p}}_{\text{2}}=\{\begin{array}{cccccccc}& \text{f}& & \text{b}& & \text{c}& & \text{d}\text{'}\\ {\text{x}}_{\text{4}}& & {\text{x}}_3& & {\text{x}}_0& & {\text{x}}_2& & {\text{x}}_3\end{array}$$E12

which makes p₂ a circular permutation of dots with 2‐adjacency.

3. Conclusions

It is known that all expositions need a complete solution, with links’ help, which suggests the path, as horizontally as and vertically, from algorithm’s solution that insides in a formal language able to analyze the system to rebuild the principal structure. The modification in the algorithm of Tarry through exchange of elements allows a better arrangement or letters couple assembly to permit the mathematical word building. The unidimensional attachment index is applied to σ giving the Tarry’s hierarchical.

There is no published clustering algorithm (whether hierarchical or not), based on graph theory, which, from generation of a path starting on a given vertex, builds a math word and calculates clustering under an index. This has been possible by modification to Tarry’s algorithm, through exchange of elements, which has allowed a better arrangement of letters coupling and the construction of a math word. The unidimensional clustering index applied to σ gives what I call Tarry’s hierarchy. The path planning problem may be approached with classical approaches, such as the potential fields, or more modern approaches, such as Fuzzy techniques [26], or the one shown here, through Tarry’s modified algorithm, which takes into account the work cycles and co‐cycles in the orientation of the labyrinth of paths defined to carry out a particular task. In addition, the set of defined paths has an order and hierarchy, for which reason, it is revealing the building of dendrogramatic trees based on net words built, which allows to analyze if work paths defined for the robotic arm are optimal.

Methodology for fractal analysis of geometric discontinuity or polygon created by unions of midpoints of vertices, nodes, or peaks of dendrograms’ terminal classes is based on the following: (i) the outline of the dendrogram under study is drawn, linking the midpoints of the vertices, nodes, or peaks of the terminal classes, verifying the sectioned behavior of the polygon; (ii) any mirror behavior in any section of the curve is identified; (iii) the curve showing the direction of its fractal propagation is isolated and a straight line is drawn from the starting point to the ending point, calculating, regarding the ordinates axis, its propagation angle; (iv) the scale factor of the fractal curve is calculated; (v) the curve generator is reproduced to scale; (vi) meshing is created for calculation of the fractal dimension of the polygon; (vii) the fractal dimension for every different meshing and rotation is calculated, graphing the results in accordance with each estimation methods theoretically accepted; and (viii) the self‐similarity property of the polygon is verified.