Basic Concepts of Graph Theory as the Instruments of Mathematical Formalization of Woven Structures

Abstract

The paper presents the prerequisites of involving of topological elements and graph theory as an instrument of mathematical formalization of woven structures and technology of textile fabrics. Present research is based on analysis and comparison of the main concepts and conditions of textile technology and graph theory.

Keywords

Share and Cite:

Kasimov, O. (2015) Basic Concepts of Graph Theory as the Instruments of Mathematical Formalization of Woven Structures. World Journal of Engineering and Technology, 3, 344-347. doi: 10.4236/wjet.2015.33C052.

Topology as a chapter of geometry has a lot in common with one of the branches of mathematics―the graph theory, which starts from the solving of task about Seven Bridges of Koennigsberg by Leonhard Euler. Efforts to attract the arsenal of this theory to the technological challenges of weaving are applied to determine the possi- bility of developing a predetermined color pattern with single-layer weave. But the data of the task “... to the coloring of a vertex of given color pattern’s structure in two colors that denote zero and one, ...” does not allow to bring the solution of the technological problem to describe the topology of the warp and weft of the whole field of weaving rapport considering full spatial orientation, and moreover, to obtain a specific numerical characteristics of the factor of weave.

The closest familiarization with the elements of this theory convinces us that more productive methods of application of graph theory to the problem of structural analysis of the weave of fabrics are available. To this end, we present some basic concepts and definitions of graph theory needed to solve our problems.

Graph, denoted as G = (V, E), consists of two types of elements called vertices and edges, respectively. Each edge has two vertices, and they usually indicated as υ1, υ2, υ3, …, and edges-e1, e2, e3, …. Vertices υi and υj, identifying edge el, called end vertices of edge el. Edge el is denoted by el = (υi, υj).

Graph G is called directed or oriented, if its edges are defined as an ordered pair of end vertices. All edges with equal end vertices are parallel. An edge whose endpoints are the same vertex is called a loop.

A graph is a simple graph if it has no multiple edges and loops. An empty graph is a graph with no edges. A graph with no vertices and edges is called null graph.

Graphical presentation of a graph is a diagram, on which a vertex is displayed as a dot, and an edge as a piece of line connecting dots, which match end vertices of an edge. For example, if V = {υ1, υ2, υ3, υ4, υ5, υ6} and E = {e1, e2, e3, e4, e5} so, that e1 = (υ1, υ2), e2 = (υ1, υ4), e3 = (υ5, υ6), e4 = (υ1, υ2), e5 = (υ5, υ5), then G = (V, E) is the same as in Figure 1. In this graph, e1 and e4 are parallel edges, and e5 is a loop. Two vertices are called adjacent if an edge exists between them. Two edges are called adjacent if a vertex exists between them.

The edge e1 of the graph, which is shown in Figure 1, is incident to vertices υ1 and υ2; υ1 and υ4 are adjacent vertices, and e1 and e2 are adjacent edges. The number of incident edges to vertex υi is called the degree, or valency of the vertex, and is labeled d(υi). A vertex of degree 1 is a leaf. A vertex of degree 0 is an isolated vertex. The maximum degree Δ(G) of a graph G is the largest degree over all vertices, the minimum degree δ(G), the smallest. In Figure 1 for graph G:

υ3―an isolated vertex, υ4 и υ6―pendant vertices, e2―a pendant edge. The sum of the degrees of vertices is 10, quantity of edges―5. So, the sum of the degrees of vertices is equal to doubled number of edges, and therefore is an even integer. Moreover, the number of vertices of graph G in odd degree is also an even integer. This is right for any graphs.

Let’s describe the structure of a weave using a graph. As a minimal part of fabric we examine the rapport of weave. The rapport of a random weave for any Ro, Ry ≥ 2, at optional Ro = Ry, in categories of graph theory represents a simple and undirected graph with order n = Ro × Ry. Let’s call it a structural graph of fabric. In structural graph of fabric, the appearance of loops in categories of graph theory is not allowed, technologically it is a defect.

Weaving cover in a range of rapport matches vertices, and the lines of warp and weft match edges of a graph. But in general, during considering of woven structure as an unlimited field with sequentially located rapports in direction of warp and weft, the valency of random vertex of a graph d(υi) = 4, but at separate examination of weaving rapport, the valency has an integer value from 2 to 4.

Figure 2 presents the simplest example of the graph of plain weave. It represents a simple undirected graph G = (V, E) of an order: n = Ro × Ry = 2 × 2 = 4 with V = {υ1, υ2, υ3, υ4} and E = {e1, e2, e3, e4}, where e1 = (υ1, υ2), e2 = (υ1, υ3), e3 = (υ2, υ4) and e4 = (υ3, υ4). The graph has following pairs of adjacent vertices: υ1 and υ2; υ1 and υ3; υ2 and υ4; υ3 and υ4, and following pairs of adjacent edges: e1 and e2; e1 and e3; e2 and e4; e3 and e4. Edges e1, e2, e3 and e4 are incident to their end vertices υ1 and υ2; υ1 and υ3; υ2 and υ4; υ3 and υ4 respectively.

The valency of all four vertices of graph, at separate examination of the rapport of weave irrelatively with separate rapports in direction of warp and weft in unlimited field of rapports in fabric structure equals:

The sum of degrees of vertices:

Therefore, the equality rule of the sum of degrees of vertices to doubled number of its edges is right for the graph, because the number of its edges is equal to 4 [1].

One more example is twill 1/2 weave (Figure 3). Graph G = (V, E) of this weave is a simple undirected graph

Figure 1. Graph G = (V, E).

Figure 2. Plain weave and its graph.

Figure 3. Twill weave 1/2 and its graph.

and consists of two multiplicities: vertices υ1, υ2, υ3, υ4, υ5, υ6, υ7, υ8, υ9 and edges e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12. It has following pairs of adjacent vertices υ1 and υ2; υ2 and υ3; υ1 and υ4; υ2 and υ5; υ3 and υ6; υ4 and υ5; υ5 and υ6; υ4 and υ7; υ5 and υ8; υ6 and υ9; υ7 and υ8; υ8 and υ9, which are the end points of edges e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12 respectively, and following pairs of adjacent edges: e1 and e2; e1 and e3; e1 and e4; e2 and e5; e3 and e6; e4 and e6; e4 and e7; e5 and e7; e6 and e8; e6 and e9; e7 and e9; e7 and e10; e8 and e11; e9 and e11; e9 and e12; e10 and e12. Comparing to the previous graph of plain weave, the valency of edges is different, and adopts values 2 and 4. Namely, d(υ1) = 2, d(υ2) = 3, d(υ3) = 2, d(υ4) = 3, d(υ5) = 4, d(υ6) = 3, d(υ7) = 2, d(υ8) = 3, d(υ9) = 2.

The sum of degrees of edges:

The number of egdes is 12. Therefore, in this case doubled number of edges gives the sum of valencies of edges, i.e.

And the order of graph equals: n = Ro × Ry = 3 × 3 = 9.

On the basis of two simple examples of graphs of plain and twill weaves, it is possible to make some abstractions. Particularly, for the sum of valencies of edges.

In any graph of weave, an existence of four vertices, whose valency equals two is inherent. In plain weave, these four vertices with degree of 2 is the set of vertices existing in a graph. But in general, with random Ro and Ry, the number of these vertices from a multiplicity of all vertices equals 4. In total sum of degrees of vertices, these 4 vertices give 4 × 2 = 8 valencies. There are also vertices with valency of 3 exist in the graph of weave, located “on the perimeter” of rapport, except angular as, for example, vertices υ2, υ4, υ6, and υ8 of twill weave 1/2. And finally, in general case of the graph of weave there are vertices with the valency of 4, located “inside” the rapport, such as vertex υ5 of the graph of twill 1/2 in Figure 3.

Therefore, the sum of valencies of all vertices of fabric’s structural graph of a random weave will be:

Required dependence to define the sum of valencies of vertices, comparable to any rapport of weave at random values Rо и Rу:

The number of the edges of weave equals: 2RоRу-Rо-Rу.

And it is obvious that the structural graph of fabric with random weave can be presented as a cycle. Specifically, in case of plain weave with Rо = Rу = 2, it presents a cycle as a sequence υ1, е1, υ2, е3, υ4, е4, υ3, е2, υ1. It is the simplest case with minimum number of cycles, 1. Then, as rapport increases, also the number of cycles increases. In case of twill 1/2 with Rо = Rу = 3, already four cycles are appearing: 1) υ1, е1, υ2, е4, υ5, е6, υ4, е3, υ1; 2) υ2, е2, υ3, е5, υ6, е7, υ5, е4, υ2; 3) υ4, е6, υ5, е9, υ8, е11, υ7, е8, υ4; 4) υ5, е7, υ6, е10, υ9, е12, υ8, е9, υ5 [1].

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] Даминов, А.Д. (2005) Основы прогнозирования структуры и проектирования текстильных полотен. D.Sc. Thesis (in Russian), Tashkent Institute of Textile and Light Industry, Tashkent, 93-100.