ON THE APPLICATION OF GRAPH THEORY METHODS TO THE ANALYSIS OF GEOMETRIC STRUCTURES IN MECHANICAL ENGINEERING

B. K. Zhigalov

(Presented by Professor, Doctor A. N. Eremin)

The geometric structure of a product of machine-building production may be regarded as a certain set consisting of elementary surfaces connected with one another in a definite way. Each elementary surface of the structure is connected with the datum surfaces by linear and angular coordinates. Thus, in a geometric structure there exist linear and angular connections and, consequently, linear and angular datums.

Depending on the stages of machine-building production, geometric structures may be divided into design, technological (assembly and part-by-part), and inspection structures. For a given product these structures consist of the same surfaces, but connected with one another by different connections. In addition to the structures listed, in the manufacture of parts production geometric structures are formed, the elements of which belong to the tools of production (they enter into the SPID system).

All the indicated structures are interrelated: the design structure is the initial one for the formation of the subsequent technological structure, and the technological structure—for the production structure. A certain “hierarchy” of structures interrelated with one another is formed [1]. In addition to direct (“directive”) connections between structures, there also exist feedback connections, which are executive.

The identification of connections in geometric structures is a complex and labor-intensive process that must be carried out in design and technological developments. For the study of geometric structures it has been proposed to apply the methods of a new mathematical discipline—graph theory, the subject of which is the study of sets [1, 2]. Graph theory makes it possible to produce a mathematical description of the geometric structure of a product by constructing graphs in which the elementary surfaces are vertices and the connections between them are edges. The application of new methods makes it possible to formalize and simplify complex and labor-intensive calculations of design and technological dimensions and their tolerances. Since the processes of formation of surfaces in a product are acyclic processes, they may be described by “trees,” which are a type of connected graphs that have no cycles, i.e., in which-

any two vertices of which are connected by only one unique route [3].

The construction of the tree of the technological structure is shown using the example of a rack-and-pinion mechanism (Fig. 1), which is an assembly structure. All surfaces of the structure are denoted by serial numbers and are plotted on the structure tree as its vertices (Fig. 2, a). One of the vertices is taken as the root (surface 2), from which the construction of the tree begins. The edges of the tree are linear technological links, which include dimensions between surfaces or between the axes of surfaces of parts included in the structure, produced in the process of manufacturing the product, i.e., in the process of machining the parts and assembling them. The edges have an orientation, indicated by arrows, in the direction from the datum surface to the surface obtained in the manufacturing process.

Fig. 1. Rack-and-pinion mechanism: 1 — rack, 2 — housing, 3 — gear, 4 — pinion, 5 — double gear

With the correct construction of the tree, no cycles, i.e., closed routes, should be formed in it, and there should be no breaks, since a tree is a connected graph. If this condition is fulfilled, the number of links in the structure must be one less than the number of surfaces in it.

Fig. 2. Graphs of geometric structures: a — tree of the technological assembly structure; b — tree of the design structure; c — graph of the technological assembly structure. Notation: \(T\) — technological links; \(S\) — design links

In addition to the tree of linear links, a tree can analogously be constructed whose edges are angular technological links.

Construction of a tree of the design structure.
On the surfaces of the product under consideration a tree may be constructed whose edges are the design connections created in the course of designing the product (Fig. 2, б). Some of the design connections will coincide with technological connections. The number of design connections must likewise be one less than the number of surfaces in the structure. The trees of the technological and design structures constructed for one and the same product have the same number of vertices and edges. Such trees are called equipotent.

Closure of the tree of the technological structure.
Any two vertices of the tree of the technological structure are connected with one another by a noncyclic (open) route in which edges and vertices are not repeated. In graph theory such routes are called simple chains [3]. Open simple chains may be closed by connections that are not part of the technological structure. In this case cyclic routes are formed, called simple cycles. Such simple cycles are dimensional chains in which the component links are technological connections. The closure of the technological tree may be carried out by connections of another structure, for example the design structure, by superposing the technological and design trees. In this case the shortest simple cycles, consisting of two edges, may also be formed. Such cycles correspond to two-link dimensional chains that arise when design and technological connections coincide.

Since the design and technological trees are equipotent, the number of dimensional chains formed upon closure will be equal to the number of edges of the tree, i.e., it will be equal to the number of design connections or to the number of technological connections.

When the technological tree is closed, a new graph is formed that has cycles (Fig. 2, в). In this graph all dimensional chains included in the structure are clearly and visibly apparent. The interrelation between the dimensional chains of the structure is also easily seen.

Finding the equations of dimensional chains and determining the sign of links.
With the aid of the graph of the technological structure one can find the equations of dimensional chains. To do this, it is necessary to find that unique route between two vertices which in the tree is a simple chain. The edges included in this route will be the component links of the dimensional chain, and the distance between the vertices will be the closing link. The links of dimensional chains are indexed by the numbers of the surfaces being connected.

The signs of the links can be determined by means of simple rules. If the surfaces of the structure are numbered consecutively with ordinal numbers, then the positive direction of a connection may be taken from the surface with the smaller number to the surface with the larger one. Then, if in traversing the graph of links of a closed chain in one direction or another we move from the smaller number to the larger, the sign of the link will be positive.

In the case when the order of numbering is violated and a surface farther from the origin of measurement has a smaller number, the orientation of the connection will be negative. Then the sign of the link obtained when traversing the dimensional chain on the graph must be changed to the opposite. For example, the sign of the connection between the axis of the tribka (surface 8, Fig. 1) and the axis of the hole of the gear (surface 9) will be negative if the clearance between the hole and the shaft is chosen in the direction of the arrow \(Q\), since axis 8 has the smaller number but is located farther from the origin of measurement. On the gra-

In the graph of the technological structure, negative edges are marked with a minus sign. For links with vector errors, which include eccentricities, the sign of the link is variable. In the graph these links are marked with the sign \(\pm\).

As an example, the equation of the dimension chain is given for the closing link \(S_{3.4}\) between the center line of the rack (surface 3, Fig. 1) and the axis of the pitch circle of the gear (surface 4).

\[ - S_{3.4} - T_{1.3} + T_{1.2} + T_{2.5} \pm T_{5.6} \pm T_{6.7} \pm T_{7.8} - T_{8.9} \pm T_{4.9} = 0. \]

If equations are found for all closing links of the structure, then we obtain a system of equations of dimension chains, whose solution is carried out by known methods and is quite definite, since the number of unknowns in the system of equations is equal to the number of equations.

The technological part structure consists of elementary surfaces obtained in the process of manufacturing the blank and machining the part, connected with one another in a definite manner by technological links. The technological links are those linear or angular coordinates that determine the position of the machined surface relative to the technological bases. A distinctive feature of technological bases is their direct connection with the production structure. The technological structure is also described by two trees: a tree of linear links and a tree of angular links.

The tree of the part technological structure is closed by design dimensions and tolerances. Below is an example of constructing the graph of the technological part structure. Figure 3 shows a diagram of the technological process for manufacturing the part. In the diagram, linear technological links are denoted by lines with one-sided arrows directed from the bases to the machined surfaces.

Fig. 3. Diagram of the technological process: a — operation sketches; b — dimension diagram

Angular bases that do not coincide with the linear ones are denoted by the letters \(У\). In the technological sketches the base surfaces are highlighted with brackets. Construction of the tree of linear links begins from the root (surface 10, Fig. 4a). When the tree is closed by design dimensions and tolerances, a graph of the linear links of the part technological structure is formed (Fig. 4a). The tree of angular links is shown in Fig. 4b.

Using the graph of the part technological structure, dimension chains and their equations are found for each closing link. In all, there should be 9 dimension chains, according to the number of edges in the tree.

\[ \begin{aligned} S_{3.4}&=T_{3.9}-T_{5.9}-T_{2.5}+T_{2.4},\\ S_{3.9}&=T_{3.9},\\ S_{6.7}^{\prime}&=-T_{3.6}+T_{3.9}-T_{7.9},\\ S_{7.9}&=T_{7.9},\\ Z_{1.2}&=T_{1.10}-T_{2.10},\\ Z_{2.3}&=T_{2.5}+T_{5.9}-T_{3.9},\\ Z_{5.6}&=T_{5.9}-T_{3.9}+T_{3.6},\\ Z_{7.8}&=T_{7.9}-T_{5.9}-T_{2.5}+T_{2.10}-T_{8.10},\\ Z_{9.10}&=-T_{5.9}-T_{2.5}+T_{2.10}. \end{aligned} \]

From the dimensional-chain equations that have been found, the technological dimensions and the tolerances on them can be calculated. The known quantities in the system of equations will be the design dimensions and allowances. In this case, as the nominal values of the allowances one takes the thickness of that defective layer of material which is subject to mandatory removal from the surface of the part.

Fig. 4. Graphs of the detailed technological structure: a—graph of linear relations; b—tree of angular relations. Designations: \(T\)—technological linear relations; \(T_y\)—technological angular relations; \(S\)—design relations; \(Z\)—allowances.

Construction of the tree of angular relations makes it possible to determine the errors of rotations between any surfaces of the part. For example, the nonparallelism of axis 4 to surface 2 is determined from the equation

\[ \varepsilon_{\varphi\,2.4} = \varepsilon_{\varphi\,4.10} + \varepsilon_{\varphi\,8.10} + \varepsilon_{\varphi\,2.8}, \]

where \(\varepsilon_{\varphi i}\) is the angular error.

The application of graph theory to the analysis of geometric structures gives the following advantages:

1. It becomes possible, from the tree, to identify easily and quickly all dimensional chains in technological and design structures and to carry out calculations of dimensions and tolerances.

2. The most rational schemes for assigning dimensions can be found, taking into account the principle of the “shortest path.”

3. Construction of the tree makes it possible to avoid errors in the assignment of dimensions, since missing and superfluous dimensions will be detected immediately.

1. The construction of a unified system of linked dimensional chains makes it possible to avoid errors in calculations, since every error will inevitably be detected.

2. The labor intensity of the calculations is reduced, and dependence on the experience and qualifications of the performer is eliminated.

3. The identification of angular connections by means of graphs makes it possible to determine rotation errors and to correctly define and coordinate the technical conditions.

4. The possibility is created of using computers for dimensional calculations.

REFERENCES

1. B. S. Mordvinov. A new method for calculating operational dimensions and tolerances. Author’s abstract of dissertation. Moscow, 1966.

2. B. S. Mordvinov. Investigation of geometric structures using methods of graph theory. Izvestiya VUZov SSSR. Mashinostroenie, No. 3, 1965.

3. O. Ore. Theory of Graphs. Moscow, “Nauka,” 1968.