Open access peer-reviewed chapter

Math Words and Their Dendrograms

By Francisco Casanova‐del‐Angel

Submitted: November 8th 2016Reviewed: March 14th 2017Published: December 20th 2017

DOI: 10.5772/intechopen.68531

Downloaded: 436

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.

Keywords

  • dendrograms
  • Tarry
  • math words
  • connexe labyrinth
  • telephone central
  • robotics

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 Lis a finite set A non‐empty and of pair cardinality, named set of words of Lor alphabet, supplied of one involution l without an indeterminate point (i.e., without a tendency change) called by the prime operator:

lA then lA, lland (l)=lE1

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:

d: A  X : d(l) = d(k)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’) ∀ lA, 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:

lA+lA+lAE3

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 L

  • l with lA is called word letter of the L, and

  • σ = l1,.., lr, lr+1,…, lp with lrA ∪ (Δα) ∀ αX, we have d(lr) = g(lr+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 Ldefined as d, g: A ∪ (Δx)xXX or d, g: LX with gx) = g(l1) and dx) = d(lp), i.e., gx) = dx) = 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+ A, Figure 1, where sets of letters A+ and A are defined as A+= {a b e f i j cd g h k l}and A= {a´ b´ e´ f´ i´ j´ c´ d´ g´ h´ k´ l´}. In addition, the vertex set of L is X= {α β ϵ γ λ δ ζ η ξ}. 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 Lwould be {a a´}UL, with ULbeing the set of lines of L. Some words of Lwith Δαbeing the empty word are {e f j i}, {a´ b´ f g}, {g d f´ i´ j´}, and {Δαe}. Cardinality of Lis as follows:

Card L = Card A = Card(A+A) = Card A++Card A=12+12=24E4

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

d(σ)= {e f g h l k d c j i b a} and d´(σ)= {a´ b´ i´ j´ c´ d´ k´ l´ h´ g´ f´ e´}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 A0, 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 A0 of labyrinth oriented 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 A0 (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 A1, 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 A0 (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 L= (A, i, d), it is a pure word if inside σ exists an occurrence of each letter of A.

Definition. If σLand σ ≈ ΔααX, σ is called neutral word in α if the neutral element Δα is a neutral word in some α‐particular.

2.1. Algorithm of Tarry

Definition. Let Llabyrinth be connected, we say Tarry’s word of Lall pure word Θ ∈ Lsuch 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 L= (A, i, g), with l1A. 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 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 l1 and l2Land let α all letters with the same left g(Θ) and β all letter with the same right d(Θ), the minimal distance dM or the inferior ultra‐metric minimal distance over a point x0l1 and x1l2 is dM(l1, l2) = min {d(x0, x1) | x0l1 & x1l2}

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 Llabyrinth may be built:

Figure 7.

Basic arrangement diagrams between telephone centrals.

L={a,b,d,e,a,c,b,c,d,e}E6

The number of trunks or telephone lines is m = 5, and the number of letters is 2m = 10. If x0X and {a, a'} ⊂ A, the net word of Figure 8 is obtained. Figure 9 is the net word of the Llabyrinth:

Figure 8.

Tree diagrams of connections between telephone centrals and area centrals.

Figure 9.

Net word of labyrinth.

Thus, seven trees related to vertex x0 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 x0 vertex. It must be remembered that the same trees may be found in every vertex different from x0.

Figure 10.

Trees, words, letters, and dendrograms of vertex x0 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:

nm=(n1)n22m=kn>2E7

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 =(n1)n2=1and k = 2. In this case, there is only one line in two directions (⇆). Let us suppose that n = n, then:

nm=(n1)n22m=kn>2E8

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

n+1m=(n+11)(n+1)22m=kn+1m=n(n+1)2=(n2+n)22m=2(n2+n)2=n2+n=kn+1m=(n2+n)22m=n2+n=kn[(n2+n)2]1m=n2+n1=kE9

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

From our example:

if n=2then n=2m=n(n1)2=2(21)2=22=12m=21=2=kif n=3then n=3m=n(n1)2=3(31)2=62=32m=23=6=kif n=4then n=4m=n(n1)2=4(41)2=122=62m=26=12=kE10

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 x0, 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 x0.

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 x0, 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 = {abcdefg’}, and that of vertices of Lis X= {x0, x1, x2, x3, x4}. 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 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 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 xG 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 Ldescribed 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 Llabyrinth, 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 Φ: AU the application that relates every letter to the corresponding line or arch in labyrinth L, where U is the family of arcs. Therefore, it is said that (i) two letters m1 and m2 are k‐adjacent if there is a word of Lwith less than k + 2 occurrences of letters, where the first word is m1 and the second word is m2. (ii) The sets of words A1 and A2 are k‐adjacent if there are two letters k‐adjacent m1 and m2, such that Φ(m1) = A1 and Φ(m2) = A2 and (iii) two vertices x1 and x2 are k‐adjacent if there are two letters, also k‐adjacent, m1 and m2, such that x1 = g(m1) and x2 = g(m2).

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

ξ={dea'bc'f'g'}=p1E11

Word ξ or p0 is a circular permutation of letters with 0‐adjacenty, that is, k = 0. ξ in p1 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:

p2={fbcd'x4x3x0x2x3E12

which makes p2 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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Francisco Casanova‐del‐Angel (December 20th 2017). Math Words and Their Dendrograms, Graph Theory - Advanced Algorithms and Applications, Beril Sirmacek, IntechOpen, DOI: 10.5772/intechopen.68531. Available from:

chapter statistics

436total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Spreading Information in Complex Networks: An Overview and Some Modified Methods

By Reji Kumar Karunakaran, Shibu Manuel and Edamana Narayanan Satheesh

Related Book

Frontiers in Guided Wave Optics and Optoelectronics

Edited by Bishnu Pal

First chapter

Frontiers in Guided Wave Optics and Optoelectronics

By Bishnu Pal

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us