Acumen:
International Journal of
Multidisciplinary Research
Volume 1, Issue 1
20
Acumen: International Journal of Multidisciplinary Research
Some basic concepts and definitions of graph theory
Eshmamatova D. B. Tashkent State Transport University
Bagaev E. I. Tashkent State Transport University
Abstract.
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
1
2
{ , ,..., }
n
V
v v
v
, whose elements
𝑣
𝑖
are called
vertices
(for
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
,
i
j
v v
(from the set
V
), whose
elements are called
arcs
, where
i
v
is the start and
j
v
is the end of such an arc.
Regarding the arc
,
i
j
v v
, it is also said that it "originates" from vertex
i
v
and
"enters" vertex
j
v
. For convenience, we will sometimes denote arcs by Greek
letters
, ,
, etc.
The set of the aforementioned sets
V
and
U
is called a graph (of order
n
according to
the number of vertices) and is denoted by
( , )
G V U
. If a graph of order
n
has
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.
Acumen:
International Journal of
Multidisciplinary Research
Volume 1, Issue 1
21
Acumen: International Journal of Multidisciplinary Research
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:
1
2
{ ,
,..., }
n
x x
x
, where any member of the sequence is an element of the set
of vertices, i.e.,
,
1,2,...,
1
i
x V i
n
A chain
is any sequence of arcs of the form
1
2
{ ,
,...,
}
n
such that the endpoints (i.e.,
the starting point and the ending point) of arc
i
are vertices
i
x
and
1
i
x
(in any order).
In other words, for all
1,2,...,
i
n
we have:
-
either
1
( ;
)
i
i
i
x x
;
-
or
1
(
; )
i
i
i
x
x
.
Vertex
1
x
is called
the initial vertex
of the chain, and vertex
1
n
x
is the terminal
vertex of the corresponding chain. It is also said that the chain connects the initial
vertex (
1
x
) with the terminal vertex (
1
n
x
).
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
1,2,...,
i
n
, the arcs
i
have only the
following form:
( ;
)
i
i
j
x x
, i.e., it is a chain that includes only
direct arcs
(the
direction of such arcs coincides with the direction of the sequence of vertices).
A cycle
is a chain for which the initial vertex (
1
x
) and the terminal vertex
(
1
n
x
) are the same.
A contour
is a path for which the initial vertex (
1
x
) and the terminal vertex (
1
n
x
) are the same (i.e., a contour is a cycle that is also a path).
A simple chain
is a chain for which no vertex in the corresponding sequence
1
2
1
{ ,
,...,
,
}
n
n
x x
x x
is incident to more than two arcs contained in this chain.
Acumen:
International Journal of
Multidisciplinary Research
Volume 1, Issue 1
22
Acumen: International Journal of Multidisciplinary Research
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 is called
connected
if any two of its vertices are connected.
The relation introduced above (a binary relation defined on pairs of vertices) of being
connected is reflexive, symmetric, and transitive. Therefore, it is an equivalence
relation. It partitions the entire set of vertices of the graph into disjoint subsets called
the
connected components
of the graph.
Note that in the classical approach to the theory of directed graphs, the concept of
connectivity is introduced differently. Let's illustrate this. First, the concept of a
related
graph
(or the concept of a
base
) for the corresponding directed graph is introduced.
This is the graph that results if the orientation is removed from the corresponding
directed graph. For the related graph (i.e., for the base of the corresponding directed
graph), concepts similar to those presented above are introduced, but with the prefix
"semi-". For example, the concept of a
semi-chain
: this is a chain for the resulting
related graph. Similarly, the concepts of a
semi-cycle
, a
semi-path
, etc., are introduced.
To define connectivity (in the classical theory of directed graphs), the concept of
"reachability" is also introduced. A vertex
j
v
is said to be reachable from a vertex
i
v
if
there is a simple path starting at
i
v
and ending at
j
v
(we denote this situation as
i
v
j
v
). It is easy to see that such a relation ("reachability") in a directed graph is transitive
but not symmetric and not reflexive. Therefore, it is not an equivalence relation.
Consequently, in the theory of directed graphs, the following different concepts of
connectivity are introduced: strong connectivity, one-way connectivity, weak
connectivity, and disconnection.
A directed graph is called
strongly connected
if for any pair of its vertices
i
v
and
j
v
,
both of the following conditions are met: 1)
i
v
j
v
; 2)
j
v
i
v
.
A directed graph is called
one-way connected
if for any pair of its vertices
i
v
and
j
v
,
at least one of the following conditions is met: 1)
i
v
j
v
; 2)
j
v
i
v
.
A directed graph is called
weakly connected
if for any pair of its vertices
i
v
and
j
v
,
there exists a semi-chain connecting them, i.e., the corresponding related graph is
connected.
Examples of such graphs are shown in Figure 1 [4].
Acumen:
International Journal of
Multidisciplinary Research
Volume 1, Issue 1
23
Acumen: International Journal of Multidisciplinary Research
Figure 1 [2].
Illustration of types of connectivity for directed graphs: a) strongly
connected b) one-way connected c) weakly connected.
To identify the specified types of connectivity in a directed graph, the following
propositions may be useful.
PROPOSITION 1.
A directed graph is strongly connected if and only if it contains a
spanning contour (i.e., a cyclic path that passes through all vertices of the graph).
PROPOSITION 2.
A directed graph is one-way connected if it contains a spanning
path.
PROPOSITION 3.
A directed graph is weakly connected if it contains a spanning
semi-chain.
LITERATURE
1.
Chartrand, G., H.Jordon, Vatter, V., & Zhang, P. (2024). Graphs and digraphs. In
(p. 364). CRC Press.
2.
Harary, F., & Palmer, E. (1973). Graphical enumeration. In (p. 326). Academic
Press.
3.
Koh, K., Dong, F., & Tay, E. (2023). Introduction to graph theory. In (p. 308).
World Scientific.
4.
Moon, J. (2013). Topics on tournaments. In Academic press. p (p. 132).
