Some basic concepts and definitions of graph theory

Аннотация

The development of graph theory and networks has led to the formation of junctions between mathematics and economics. In two established different areas of research in this field: algebraic and optimization. Taking into account the requirements of logistics research applications, we will continue to adhere mainly to the second of these areas. For this purpose, we decided to devote this work to the study of the basic elements of graph theory. In it, we have given the basic concepts such as arc, loop, path, cycle, contour, simple chain and others. Keywords. Arc, loop, path, cycle, contour, simple chain. The development of graph and network theory has led to the formation of two distinct areas of research in this field: algebraic and optimization. Considering the requirements of logistics research applications, we will mainly adhere to the latter of these directions. Below, we will briefly present the basic concepts and definitions related to this subject area [1]-[3]. Let: - V be a certain set V {v,v ,...,v }, whose elements 𝑣 are called vertices (for 1 2 n 𝑖 convenience, we will sometimes denote vertices by numbers 1, 2, … or letters a,b, ...,x,y, etc.); - U be the set of ordered pairs of vertices v ,v (from the set V), whose i j elements are called arcs, where v is the start and v is the end of such an arc. i j Regarding the arc v ,v , it is also said that it "originates" from vertex v and i j i "enters" vertex v . For convenience, we will sometimes denote arcs by Greek j letters ,,, etc. The set of the aforementioned sets V and U is called a graph (of order naccording to the number of vertices) and is denoted by G(V,U). If a graph of order nhas m arcs, such a graph is usually called an (n;m)-graph. In the schematic representation of a graph, its vertices are represented by points (often circles), and arcs are depicted as arrows connecting specific vertices (generally indicating the direction). The lengths of these arrows and their type (straight lines or not) do not matter. 20 Acumen: International Journal of Multidisciplinary Research Acumen: International Journal of Multidisciplinary Research Volume 1, Issue 1 The requirement of ordering pairs of vertices for the set of arcs U in the definition above corresponds to the concept of so-called directed graphs. For certain problems in graph theory and their corresponding logistical applications, it is not necessary to distinguish the start and end of an arc (i.e., it is not necessary to assign specific directions to the arcs). In this case, the graph is called undirected. In undirected graphs, the arcs are referred to as edges. A loop is an arc for which the starting and ending vertices are the same. Two vertices are called adjacent if there is an arc connecting them (its direction does not matter). A vertex and an arc are said to be incident (to each other) if the arc "enters" or "originates" from this vertex. Two arcs are called incident (to each other) if they are incident to the same vertex. To represent the following concepts, we will use some "conditional" arbitrary sequence of vertices: {x ,x ,...,x }, where any member of the sequence is an element of the set 1 2 n of vertices, i.e., x V,i 1,2,...,n1 i A chain is any sequence of arcs of the form {,,...,}such that the endpoints (i.e., 1 2 n the starting point and the ending point) of arc  are vertices x andx (in any order). i i i1 In other words, for all i 1,2,...,nwe have: - either  (x;x ); i i i1 - or  (x ;x ). i i1 i Vertex x is called the initial vertex of the chain, and vertex x is the terminal 1 n1 vertex of the corresponding chain. It is also said that the chain connects the initial x vertex ( 1) with the terminal vertex (x ). n1 The length of a chain is the number equal to the number of arcs it contains. A path is a chain for which, for all i 1,2,...,n, the arcs  have only the i following form:  (x ;x ), i.e., it is a chain that includes only direct arcs (the i i j direction of such arcs coincides with the direction of the sequence of vertices). A cycle is a chain for which the initial vertex (x ) and the terminal vertex 1 (x ) are the same. n1 A contour is a path for which the initial vertex (x ) and the terminal vertex ( 1 x ) are the same (i.e., a contour is a cycle that is also a path). n1 A simple chain is a chain for which no vertex in the corresponding sequence {x ,x ,...,x ,x } is incident to more than two arcs contained in this chain. 1 2 n n1 21 Acumen: International Journal of Multidisciplinary Research Acumen: International Journal of Multidisciplinary Research Volume 1, Issue 1 Similarly, the concepts of a simple path, a simple cycle, and a simple contour are introduced. The term "simple" emphasizes that the corresponding chain (path, cycle, contour) does not contain any cycles within itself. Two vertices are called connected if there is a chain connecting them (note that the direction of arcs in such a chain does not matter for this definition). A graph