**World Journal of Engineering and Technology**

Vol.03 No.03(2015), Article ID:61134,4 pages

10.4236/wjet.2015.33C052

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

Otabek Kasimov

Tashkent Institute of Textile and Light Industry, Tashkent, Uzbekistan

Email: otabekkasimov@gmail.com

Received 3 October 2015; accepted 23 October 2015; published 30 October 2015

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:**

Textile, Weaving, Structure, Plain Weave, Twill Weave, Rapport, Topology, Graph Theory, Vertex, Valency, Edge, Warp, Weft

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-e_{1}, e_{2}, e_{3}, …. Vertices υ_{i} and υ_{j}, identifying edge e_{l}, called end vertices of edge e_{l}. Edge e_{l} is denoted by e_{l} = (υ_{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 = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}} so, that e_{1} = (υ_{1}, υ_{2}), e_{2} = (υ_{1}, υ_{4}), e_{3} = (υ_{5}, υ_{6}), e_{4} = (υ_{1}, υ_{2}), e_{5} = (υ_{5}, υ_{5}), then G = (V, E) is the same as in Figure 1. In this graph, e_{1} and e_{4} are parallel edges, and e_{5} 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 e_{1} of the graph, which is shown in Figure 1, is incident to vertices υ_{1} and υ_{2}; υ_{1} and υ_{4} are adjacent vertices, and e_{1} and e_{2} 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, e_{2}―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 R_{o}, R_{y} ≥ 2, at optional R_{o} = R_{y}, in categories of graph theory represents a simple and undirected graph with order n = R_{o} × R_{y}. 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 = R_{o} × R_{y} = 2 × 2 = 4 with V = {υ_{1}, υ_{2}, υ_{3}, υ_{4}} and E = {e_{1}, e_{2}, e_{3}, e_{4}}, where e_{1} = (υ_{1}, υ_{2}), e_{2} = (υ_{1}, υ_{3}), e_{3} = (υ_{2}, υ_{4}) and e_{4} = (υ_{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: e_{1} and e_{2}; e_{1} and e_{3}; e_{2} and e_{4}; e_{3} and e_{4}. Edges e_{1}, e_{2}, e_{3} and e_{4} 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 e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7}, e_{8}, e_{9}, e_{10}, e_{11}, e_{12}. 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 e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7}, e_{8}, e_{9}, e_{10}, e_{11}, e_{12} respectively, and following pairs of adjacent edges: e_{1} and e_{2}; e_{1} and e_{3}; e_{1} and e_{4}; e_{2} and e_{5}; e_{3} and e_{6}; e_{4} and e_{6}; e_{4} and e_{7}; e_{5} and e_{7}; e_{6} and e_{8}; e_{6} and e_{9}; e_{7} and e_{9}; e_{7} and e_{10}; e_{8} and e_{11}; e_{9} and e_{11}; e_{9} and e_{12}; e_{10} and e_{12}. 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 = R_{o} × R_{y} = 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 R_{o} and R_{y}, 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].

Cite this paper

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

References

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