Lecture 4. Graphs

4.1.Graphs. Definition, types of graphs

4.2. Properties of graphs

Program provisions

There are several reasons for the growing interest in graph theory. It is an undeniable fact that graph theory is used in fields such as physics, chemistry, communication theory, computer design, electrical engineering, mechanical engineering, architecture, operations research, genetics, psychology, sociology, economics, anthropology and linguistics. This theory is also closely related to many branches of mathematics, including group theory, matrix theory, numerical analysis, probability theory, topology and combinatorial analysis. It is also certain that graph theory serves as a mathematical model for any system containing a binary relation. Graphs are engaging and aesthetically pleasing due to their presentation as diagrams. Although graph theory contains many results that are elementary in nature, it also contains a tremendous abundance of very subtle combinatorial problems worthy of the attention of the most sophisticated mathematicians. (F. Harari “Graph Theory”)

Pay attention to the convenience and possibility of widespread use of graphs in applied problems

Literature

Security questions

1. What is a graph?
2. What are called a vertex and an edge of a graph?

3. Is it possible to trace this diagram without lifting the pencil and without going through any edges twice?

1. Can the sum of the degrees of the vertices of a graph be an odd number?
2. Is it possible to organize a tournament between 11 teams, so that each team plays exactly 5 matches?

6. Show the equivalence of the definitions from paragraph 4.1.(6) (that they describe the same object)

7.Show that the graphs are isomorphic

8. Show that isomorphism is an equivalence relation on graphs.

9. What is the minimum number of parts that a piece of wire needs to be divided into so that it can be used to make a cube frame?

10. Show that the graph is planar

Graphs. Definition, types of graphs

The father of graph theory is L. Euler A707-1782), who in 1736 solved a problem that was widely known at that time, called the problem of the Königsberg bridges.

In the city of Koenigsberg there were two islands connected by seven bridges to the banks of the Pregolya River and to each other as shown in Fig. 4.1.(1) (A,D – islands, B,C – river banks). The task was as follows: to find a route through all four parts of the land, which would start from any of them, end on the same part and pass over each bridge exactly once. It is easy, of course, to try to solve this problem empirically, searching through all the routes, but all attempts will end in failure. L. Euler managed to find a solution to this problem by proving the impossibility of such a route.

To prove that the problem had no solution, Euler designated each part of the land with a point (vertex), and each bridge with a line (edge) connecting the corresponding points. The result is a “graph”. This graph is shown in Fig. 4.1.(2), where points

are marked with the same letters as the four pieces of sushi in Fig. 4.1(1). The statement about the non-existence of a “positive” solution to this problem is equivalent to the statement about the impossibility of traversing the graph presented in Fig. 1 in a special way. 4.1(2).

In this case, the problem takes on the following formulation: starting from any vertex, passing along each edge only once, return to the original vertex.

An example of another problem that can be modeled using graph theory is the problem of supplying three houses with three types of utilities. According to the problem, each of the three houses needs to be connected to three types of utilities, for example, water, gas and electricity, through underground pipe lines and cables. The question is whether it is possible to provide utilities to these three houses without crossing supply lines. The graph modeling this problem is shown in Fig. 4.1(3) (This well-known model problem is sometimes formulated as the problem about houses and wells)

A similar problem of a more practical nature arises when creating microcircuits. In them, crossing wires at each level is undesirable.

Definition 4.1(1)

A graph is a finite set V, called the set of vertices, and a set E of two-element subsets of the set V. The set E is called the set of edges. An element of the set E is called an edge. The graph is denoted by G(V, E). Elements a and b of a set V are called connected, or connected by an edge (a, b), if .

In other words, a graph is a diagram consisting of points, some of which are connected by segments.

Examples of graphs are a metro map, a family tree, a road map, etc.

Definitions 4.1(2)

If (a, b) is an edge, then the vertices a and b are called the ends of the edge (a, b). Edge (a, b) is also called incidental to vertices a and b. Conversely, we say that vertices a and b are incident to the edge (a, b). The two peaks are called adjacent (neighboring), if they are the ends of an edge, or, what is the same, if they are incident to the same edge. Two edges are said to be adjacent if they are incident to a common vertex.

If multiple edges are allowed between two points, the graph is called multigraph.

If all vertices in a graph are adjacent, the graph is called complete.

A graph with one vertex and no edges (consisting of 1 point - a vertex) is called trivial.

Definition 4.1(3)

The degree of a vertex v is denoted by deg(v), which is the number of edges incident to this vertex (emanating from it).

A vertex of degree 0 (that is, no edge emanates from the vertex, it is a “lonely” point) is called isolated.

A vertex of degree 1 is called a hanging vertex.

The vertices can be even or odd.

Definitions 4.1.(4)

Path (between vertices) – a sequence of edges and intermediate vertices connecting them

Path length – the number of edges included in the path

A simple path is a path in which all edges and vertices are distinct

A cycle (loop) is a closed path of non-zero length in which all vertices are different except the beginning, which coincides with the end

Examples 4.1(1).

1. A graph with a set of vertices V = (a,b,c) and a set of edges E ((a, b), (b, c)) can be depicted as shown in Figure 4.1(4) (Simple) path between vertices a and c includes edges (a,b), (b,c) and vertex c

Note: both pictures reflect the same situation. From the point of view of graphs, what matters first is the existence of a connection between points, and not its geometry.

2. A graph with V = (a,b,c,d,e) and E = ((a, b), (a, e), (b, e), (b, d), (b, c), (c, d)),

can be depicted by the diagram shown in Fig. 4.1.(5). The graph contains two cycles (b, e, a), (b, c, d).

3. In Fig. 4.1.(6) vertices a and c are adjacent and e 1, e 2 and e 3 are adjacent edges, vertices a and f are not adjacent, and e 2 and e 5 are not adjacent edges. Vertices b, c and d have degree 2, while vertices a and f have degree 3.

Let us now return to Euler's problem. When traversing a graph, 2 situations are possible: the beginning and end of the path coincide, the input and output are different. In order to go through the graph accordingly (circle the drawing without lifting the pencil, without skipping or tracing any edges twice):

In the first case, all vertices must have even degrees, in the second, all vertices must be even, except for the entrance and exit.

Example 4.1.(2)

Is it possible to go through the graph in Fig. 4.1(4), without skipping or going through any edges twice?

The degrees of all vertices are even, except for vertices c and j with degree 3. Accordingly, the only traversal path is one with vertices c and j as the beginning and end (or vice versa)

In many cases, you need graphs whose edges are essentially a one-way street. This means that if an edge is considered going from vertex a to vertex b, then it cannot be considered going from vertex b to vertex a. For example, if the graph models the flow of oil in a pipeline, and if oil flows from point a to point b, we would not want it to flow in the opposite direction, from point b to point a.

Definition 4.1(5)

Directed graph or digraph G, which is denoted by G(V, E) consists of a set V of vertices and a set E of ordered pairs of elements from Y, called the set of oriented edges or simply edges, if it is clear that the graph is oriented. An element of the set E is called an oriented edge. If , then a is called the initial vertex of the edge (a, b), b is called the final vertex.

Example 4.1(3)

A digraph for which V = (a, b, c, d] and E = ((a, b), (b, c), (c, c), (c, d), (d,b),( c,d),(d,a)) is shown in Fig.

Definition 4.1.(6)

Let's consider several equivalent definitions of a tree graph.

1) This is a connected graph that has no cycles (about the connectedness property, see 4.2.)

2) A graph in which any 2 vertices are connected by a simple path

3) A connected graph that loses connectivity when any edge is removed

4) A graph in which there are 1 fewer edges than vertices

Examples of trees:

A sufficiently developed family tree forms a tree. If you start with a specific (well-known) individual and draw edges between each parent and each son or daughter, this will form a tree. When constructing a family tree, however, great care must be taken to ensure that marriages between distant relatives do not form cycles.

Properties of graphs

Theorem 4.2(1).

The sum of the degrees of the vertices of a graph is always even.

Proof

Since each edge of the graph has two ends, the degree of each end increases by 1 at the expense of one edge. Thus, each edge contributes 2 units to the sum of the degrees of all vertices, so the sum must be twice the number of edges. Therefore, the sum is an even number.

Theorem 4.2.(2)

In any graph the number of vertices of odd degree is even.

Proof

We will carry out the proof by contradiction: assuming that the theorem is not true, we will find a contradiction from which it will follow that the theorem is true. If the theorem is not true, then there is an odd number of vertices whose degrees are odd. But the sum of the degrees of vertices with even degrees is even. The sum of the degrees of all vertices is the sum of the degrees of vertices with odd degrees plus the sum of the degrees of vertices with even degrees. Since the sum of an odd number and an even number is an odd number, the sum of the degrees of all vertices is odd. But this contradicts Theorem 4.1(1), so we have arrived at a contradiction. Therefore, we conclude that the theorem is true.

Example 4.2.(1)

Is it possible to organize a football tournament between 7 teams so that each team plays exactly 3 matches?

No, because if we make a graph with 7 vertices, and try to derive 3 edges from each vertex. According to Theorem 4.2(2), it is impossible to construct such a graph.

Definition 4.2(1).

Graphs with the same structure are called isomorphic. Two graphs G and H are isomorphic (or sometimes written G=H) if there is a one-to-one correspondence between their sets of vertices that preserves adjacency. For example, G and H in Fig. 4. 2(2) are isomorphic under the correspondence .

In other words, the vertices of each of such graphs can be numbered in such a way that the vertices can be numbered in such a way that its vertices are neighboring if and only if they are neighboring in the second one.

Note that isomorphism is an equivalence relation on graphs.

Definitions 4.2(2)

The graph is called coherent, if there is a path between any two vertices.

Connectivity Component– part of a graph that is itself connected, but cannot be extended so that it remains connected

The connectivity x=x(G) of a graph G is the smallest number of vertices whose removal leads to a disconnected or trivial graph. From the definition it follows that the connectivity of a disconnected graph is equal to 0, and the connectivity of a connected graph that has a junction point is equal to 1. A complete graph cannot be made disconnected, no matter how many vertices are removed from it.

GRAPHS

Graphs originated in the eighteenth century when the famous mathematician, Leonhard Euler, tried to solve the now classic problem of the Königsberg bridges. At that time in the city of Konigsberg there were two islands connected by seven bridges to the banks of the Pregol River and to each other as shown in Fig. 7.1. The task is the following: to carry out a walk around the city in such a way that, having walked exactly once over each bridge, you return to the same place where the walk began. Solving this problem, Euler depicted Koenigsberg as a graph, identifying its vertices with parts of the city, and its edges with the bridges that connect these parts. As we will show in § 7.1, Euler was able to prove that the desired route around the city does not exist.

Figure 7.1. Scheme of old Koenigsberg

In this chapter, we introduce the standard terminology used in graph theory and examine several specific problems that can be solved using graphs. In particular, we'll be introduced to a class of graphs called trees. Trees are a natural model that represents data organized in a hierarchical system. Tree searching to isolate individual items and sorting data in a tree are important points of effort in computer science. In the appendix to this chapter, we'll look at sorting and searching data organized into trees.

Graphs and terminology

In Fig. 7.1 shows the seven bridges of Königsberg like this. how they were located in the eighteenth century. The problem that Euler addressed asks: is it possible to find a walking route that passes exactly once over each of the bridges and starts and ends in the same place in the city?

The task model is graph, consisting of many peaks and many ribs connecting the vertices. Vertices A, B, C and D symbolize the banks of the river and islands, and the ribs a,c, c,d,f And g represent seven bridges (see Fig. 7.2). The required route (if it exists) corresponds to traversing the edges of the graph in such a way that each of them is traversed only once. The passage of the rib obviously corresponds to the crossing of the river by bridge.

Figure 7.2. Model of the Königsberg bridge problem

A graph in which there is a route, there is a route that starts and ends at the same vertex, and passes along all the edges of the graph exactly once, is called Seiler graph. The sequence of vertices (maybe with repetitions) through which the desired route passes, like the route itself, is called Eulerian cycle. Euler noticed that if there is an Eulerian cycle in a graph, then for every edge leading to some vertex there must be another edge leaving this vertex 1, and from this simple observation he derived the following conclusion: if there is an Eulerian cycle in a given graph , then each vertex must have an even number of edges.

In addition, Euler was able to prove the opposite statement, so that a graph in which any pair of vertices is connected by some sequence of edges is Eulerian if and only if all its vertices have even degree. Degree vertices v is called the number δ(v) ribs, her incident 2 .

Now it is quite obvious that in the graph modeling the Königsberg bridge problem, an Euler cycle cannot be found. Indeed, the degrees of all its vertices are odd: δ(B) = δ(С)= δ(D) = 3 and δ(A) = 5. With the help of Euler, graphs similar to the one we studied when solving the problem of bridges began to be used in solving many practical problems, and their study grew into a significant area of ​​mathematics.

Simple graph is defined as the pair G = (V, E), where V is a finite set of vertices, and E- a finite set of edges, and cannot contain loops(edges starting and ending at the same vertex) and multiple edges(multiple edges are multiple edges connecting the same pair of vertices). The graph shown in Fig. 7.2. is not simple, since, for example, the vertices A And IN are connected by two edges (it is these edges that are called multiple).

Two peaks u And v in a simple graph are called adjacent, if they are connected by some edge e, about which they say that it is incidental vertex u (and v ). Thus we can imagine many E edges as a set of pairs of adjacent vertices, thereby defining a non-reflexive, symmetric relation on the set V. The lack of reflexivity is due to the fact that a simple graph does not have loops, i.e., edges, both ends of which are at the same vertex. The symmetry of the relationship follows from the fact that the edge e, connecting the vertex And With v, connects and v With And(in other words, the edges are not oriented, that is, they have no direction). A single edge in a simple graph connecting a pair of vertices u And v, we will denote it as andv(or vi).

The logical matrix of a relationship on the set of vertices of a graph, which is defined by its edges, is called ,adjacency matrix. The symmetry of a relation in terms of the adjacency matrix M means that M symmetrical about the main diagonal. And due to the non-reflexivity of this relationship on the main diagonal of the matrix M there is a symbol "L".

Example 7.1. Draw a graph G(V, E) with set of vertices V = (a, b, c, d, e) and a set of edges E = (ab, ae, bc, bd, ce, de). Write down its adjacency matrix.

Solution. Graph G is shown in Fig. 7.3.

Figure 7.3.

Its adjacency matrix has the form:

To restore the graph, we only need those elements of the adjacency matrix that are above the main diagonal.

Subgraph graph G = (V, E) is called a graph G’ = (V’, E’), in which E’ C E and V’ C V.

Example 7.2 Find among the graphs H, K and L shown in Fig. 7.4, subgraphs of graph G.

Solution. Let us denote the vertices of the graphs G, H and K as shown in Fig. 7.5. The graphs H and K are subgraphs of G, as can be seen from our notation. The graph L is not a subgraph of G because it has a vertex with index 4, while G does not.

Route length k in a graph G such a sequence of vertices is called v 0 , v 1 , …, v k , that for each i = 1, …, k pair v i – 1 v i forms an edge of the graph. We will denote such a route by v 0 v 1 … v k . For example, 1 4 3 2 5 is a route of length 4 in graph G from Example 7.2.

G H

K L

Figure 7.4.

Cycle in a graph it is customary to call the sequence of vertices v 0 , v 1 , … , v k , each pair of which is the ends of one edge, and v 0 = v 1 , and the remaining vertices (and edges) are not repeated. In other words, a cycle is a closed route that passes through each of its vertices and edges only once

1 2 1 2 3

Figure 7.5

Example 7.3. Find cycles in graph G from Example 7.2.

Solution. This graph has two different cycles of length 5:

1 3 2 5 4 1 and 1 2 5 4 3 1

We can go through these cycles in one direction or the other, starting from an arbitrary top of the cycle. In addition, the graph has three different cycles of length 4:

1 2 5 4 1, 1 2 3 4 1 and 2 5 4 3 2,

and two loops of length 3:

1 2 3 1 and 1 3 4 1.

A graph that has no cycles is called acyclic. Tree structures that arise in computation are a special case of acyclic graphs. We'll deal with them later in this chapter.

Count, called coherent, if any pair of its vertices is connected by some route. Any general graph can be divided into subgraphs, each of which turns out to be connected. The minimum number of such connected components is called connection number graph and is denoted by c(G) . Connectivity issues are important in applications of graph theory to computer networks. The following algorithm is used to determine the connectivity number of a graph.

Connectivity algorithm.

Let G = (V, E) be a graph. The algorithm is designed to calculate the value c = c(G), those. the number of connected components of a given graph G.

V' :=V;

whileV’≠ ødo

Select y Є V’

Find the vertices connecting the route to y;

Remove vertex fromV' And

corresponding edges from E;

c:= c+1;

Example 7.4. Observe the operation of the connectivity algorithm on the graph shown in Fig. 7.6.

Figure 7.6.

Solution. See table. 7.1.

Table 7.1.

Initial values	{1,2,3,4,5,6,7,8}
Choice y = 1
Choice y = 2
Choice y = 7

So, c(G) = 3. The corresponding connected components are shown in Fig. 7.7.

5

Key questions:

Information from the history of graphs. Count and
its elements.
Paths and routes in graphs
Connected graphs. Trees
Operations on graphs.

Graph theory is
branch of mathematics that has
wide practical applications.
Graph theory - field
discrete mathematics,
which feature is
geometric approach to study
objects.

History of graphs

For the first time the basics of graph theory
appeared in Leonard's works
Euler (1707-1783;
Swiss, German and
Russian mathematician)
which he described the solution
puzzles and math
entertainment tasks.
Graph theory started with
Euler's solution to the problem of
seven bridges
Koenigsberg.

The following riddle has long been common among the residents of Königsberg:
how to cross all the bridges (across the Pregolya River) without crossing any
of them twice? Many have tried to solve this problem both theoretically and
practically, while walking. But no one succeeded, but not
It was possible to prove that this is even theoretically impossible.
In a simplified diagram of the parts
city ​​(county) bridges
correspond to lines (arcs
count), and parts of the city -
line connection points
(vertices of the graph).
In the course of his reasoning, Euler came to
following conclusions: Unable to pass
across all bridges without passing on any of them
them twice.

History of graphs

The term "graph" first appeared in the book
Hungarian mathematician D. Koenig in 1936, although
initial most important theorems about graphs
go back to L. Euler.

The theory is based on the concept of a graph.

- a set of finite numbers
points called vertices of the graph, and
pairwise connecting some of these
vertices of lines called edges or
arcs of the graph. Sometimes the graph as a whole
can be denoted by one capital letter
letter.
G V , X is called a pair of two
finite sets: the set of points V and
set of lines X (edges, arcs),
connecting some pairs of points.

Composition of the graph

The graph consists of vertices connected by lines. Peaks
the column is designated by Latin letters A, B, C, D or
in numbers.
A directed line (with an arrow) is called an arc.
A non-directional line (without an arrow) is called an edge.
A line leaving a certain vertex and entering a
it is called a loop.
arc
A
edge
IN
loop
WITH

Directed graph -

a graph whose vertices are connected by arcs. WITH
using such graphs can be represented
one-way relationship schemes.
Yura
Anya
Masha
Kolya
Vitya

Weighted graph

This is a graph whose edges or arcs are assigned
correspond to numerical values ​​(they can
indicate, for example, the distance between cities
or transportation cost).
The weight of a graph is equal to the sum of the weights of its edges.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
E
A B C D E
3 1
4
2
3 4
2
1
2 2
Table (it is called weight
matrix) corresponds to the graph.

If
an edge of the graph G connects its two
vertices V and W, (i.e. V ,W X), then they say
that this edge is incidental to them.
Two vertices of a graph are called adjacent,
if there is an edge incident to it: on
in the figure, vertices A and B are adjacent,
A and S.
A
WITH
IN

If a graph G has an edge whose origin
and the end coincide, then this edge is called
loop. In the figure, edge q(C, C) is a loop.
q
E
WITH
A
D
B

Two edges are said to be adjacent if they
have a common vertex.
In the figure, adjacent are, for example,
edges x1 and x2 with a common vertex C.
D
x5
x1
F
WITH
x4
x2
G
x7
x3
E
x6
B
H
A

Ribs that start in one and
the same peak, end the same way
at the same vertex are called
multiple or parallel.
Number of identical pairs of the type
(V , W) is called the multiplicity of the edge (V , W)
The number of edges incident to vertex A is
is called the degree of this vertex and
is denoted by deg(A) (from the English degree –
degree).

In the figure, the multiples are, for example,
edges x1(A, B), x2(A, B). Vertices A and C
edges x3, x4, x5 are incident. Hence,
edge AC has a multiplicity of 3, and edge
AB – multiplicity equal to 2.
A
x4
x1
x3
WITH
x2
x5
IN

In the figure, vertex A has degree
equal to 1, vertex C – 4, vertex D – 2.
This is written in the form: deg(A)=1, deg(C)=4,
deg(D)=2.
D
x5
x1
F
WITH
x4
x2
G
x7
x3
E
x6
B
H
A

A vertex of a graph that has degree zero is
called isolated.
A graph consisting of isolated vertices
called a null graph.
A graph vertex that has degree 1
called hanging.
A graph that has no edges (arcs) is called
empty.
E
C
A
D
B
In the picture the top
E – isolated:
deg(E)=0.

In the figure, vertices A, B, E, G, H are pendant.
D
x5
x1
F
WITH
x4
x2
G
x7
x3
E
x6
B
H
A

Theorem 1. In the graph G V , X the sum
the degrees of all its vertices are an even number,
equal to twice the number of edges of the graph:
n
deg(V) 2m
i 1
i
The number of edges in any graph is equal to
half the sum of the degrees of its vertices.
where n V
- number of vertices;
m X is the number of edges of the graph.

The vertex is called even (odd),
if its degree is an even (odd) number.
In the figure, deg(D)=2, deg(F)=3, which means
graph vertex D is even, and F is
odd.
x5
D
x1
F
WITH
x4
x2
G
x7
x3
E
x6
B
H
A

Task. There are 15 telephones in the town of Malenky. Is it possible to connect them with wires so that each phone is connected to exactly five

others?

Theorem 2. Any (non-oriented)
the graph contains an even number of odd
peaks
Consequence. It is impossible to draw a graph with
an odd number of odd vertices.
The graph G is called complete,
if any two of it are different
the vertices are connected by one and
only one edge.

Task. There are 30 people in the class. Could it be that 9 people have 3 friends, 11 have 4 friends, and 10 have 5 friends?

The complement of a graph G V , X is called
graph G V , X with the same vertices V as
graph G, and having those and only those edges X,
which must be added to graph G so that it
became full. In the figure, by adding graph G1 to
graph G is a graph
G1
G
G1
G1

Pattern 1.
Pattern 2.
Vertex degrees
Sum of degrees
complete graph
are the same, and
each of them is 1
less number
the tops of this
graph
graph vertices number
even, equal
double the number
edges of the graph. This
pattern
not fair
only for complete
but also for anyone
graph.

Pattern 3.
Pattern 4.
Number of odd
Impossible
vertices of any
the column is even.
draw a graph with
odd number
odd vertices.

Pattern 5.
Pattern 6.
If all vertices
The graph with everything
the column is even, then
possible without tearing it off
paper pencil
(“with one stroke”),
swiping through each
rib only once,
draw this graph.
Movement is possible
start with any
tops and finish
him at the same peak.
two odd
peaks, you can
draw, not
tearing off a pencil
from paper, while
movement is needed
start with one of
these odd
tops and finish
in the second of them.

Pattern 7.
A graph having more
two odd
peaks, impossible
draw "one
with a flourish." Figure
(graph), which can be
draw without lifting
paper pencil,
called
unicursal.

Paths and routes in graphs

A path in a directed graph is called
sequence of arcs in which the final
the vertex of any arc other than the last one,
is the starting vertex of the next arc.
The peak from which the route is laid,
called the beginning of the path, the top is at the end
route - the end of the path.
Path in which each vertex is used
no more than once, called simple
way.
The length of a path in a graph is the number of arcs
(edges) that make up this path.

As an example, consider the digraph
presented in the figure. One of the existing
paths connecting vertices 1 and 3 is
sequence of vertices 1, 2, 1, 4, 3. The only one
a simple path for the same pair of vertices is
sequence 1, 4, 3. Paths from vertex 1 to
vertex 5 does not exist for the same graph.

An undirected graph is called
connected if there is at least one path
between each pair of vertices.
A digraph is called connected if it is connected
an undirected graph that
is obtained from the original oriented
replacing all arcs with edges.

A path is called closed if
the start and end vertices are the same.
A closed path is called a cycle if all
its vertices (except for the initial and final ones)
are different.
Consider the graph. For him the path is 2, 1, 6, 5, 4, 1,
2 is closed; and the path is 1, 6, 5, 4, 1
is a cycle.

Sequence of pairwise adjacent
vertices of an undirected graph, i.e.
sequence of edges
undirected graph in which the second
the vertex of the previous edge coincides with
the first vertex of the next one is called
route.
The number of edges in a route is called the length
route.
If the starting vertex of the route matches
with the final one, then such a route is called
closed or loop.

In the figure, HCDFD is a route of length 4.
Designation: |HCDFD|=4. Route accepted
ask
How
subsequence
ribs,
since this is convenient when there are multiples
ribs
X
D
x1
5
F
WITH
x4
x2
G
x7
x3
E
x6
B
H
A

In the graph in the figure (t, s, p, r), (u, s, t, r) are cycles
length 4, (r, t, q, s, u) – cycle length 5, (t, s, u, r, t, s, p, r)
– 8-cycle, (p, u) – 2-cycle, loop (q) – 1-cycle.
E
q
C
s
A
p
t
D
r
B
u

Operations on graphs

Single operations
1. Removing an edge of the graph - in this case, all the vertices of the graph
are saved
2. Adding a graph edge between two
existing peaks.
3. Deleting a vertex (together with incident
ribs).
4. Adding a vertex (which can be connected to
some vertices of the graph).
5. Contraction of an edge - identification of a pair of vertices, i.e.
removing a pair of adjacent vertices and adding a new one
vertices adjacent to those vertices that were
adjacent to at least one of the remote vertices)
6. Subdividing an edge with - removing an edge and adding
a new vertex that is connected by an edge to each of
vertices of a remote edge.

Operations on graphs

Double operations
By combining graphs G1 (V1, X 1) and G2 (V2, X 2)
called the graph G G1 G2 , the set of vertices
which V V1 V2 , and the set of edges is X X 1 X 2 .
The intersection of graphs G1 and G2 is called
graph G G1 G2 for which X X 1 X 2 is the set of edges, and V V1 V2 is the set of vertices.
The ring sum of two graphs is called a graph
G G1 G2 generated by a set of vertices
those.
V V1 V2 and a set of edges (X1 X 2) \ (X1 X 2) ,
set of edges contained either in G1 or in
G2, but not in G1 G2.

V4
V2
x3
x2
V3
x4
V1
x1
V5
x2
x7
x3
x4
x4
V1
x7
V1
G=G1UG2
V3
x4
V5
x2
V1
x3
G=G1∩G2
V2
x1
G2
V4
V2
x5 x6
x6
V3
V1
V4
V3
V4
x5
x3
x1
G1
V2
V5
V2
V4
x5 x6V
3
x7
G=G1 G2

Application of graphs

WITH
with help
graphs
simplified
math problems, puzzles,
ingenuity.
solution
tasks for
further

Application of graphs

A labyrinth is a graph. And to explore it is to find it
path in this graph.
further

Uses graphs and
nobility.
The figure shows
part of genealogy
tree
famous
noble family L.N.
Tolstoy. Here it is
vertices are members of this
kind, and those connecting them
segments - relationships
kinship,
leading from parents to
children.
further

Application of graphs

Graphs are block diagrams of programs for
COMPUTER.
further

Application of graphs

Typical graphs on
geographical maps are
railroad images.
further

Application of graphs

Typical graphs on city maps
are urban traffic patterns
transport.
further

Conclusions

Graphs are wonderful mathematical
objects with which you can solve
mathematical, economic and logical
tasks. You can also solve various
puzzles and simplify the conditions of tasks according to
physics, chemistry, electronics, automation. Graphs
are used
at
drawing up
kart
And
genealogical trees.
There is even a special section in mathematics
which is called: “Graph Theory”.
content

Completely disconnected graphs . A graph whose many edges are empty is called quite incoherent(or empty) graph. We will denote a completely disconnected graph with n vertices by N n ; N 4 is shown in Fig. 1. Note that at of a completely disconnected graph, all vertices are isolated. Completely disconnected graphs are not of particular interest.

Complete graphs . A simple graph in which any two vertices are adjacent is called complete graph. A complete graph with n vertices is usually denoted by. Graphs and are shown in Fig. 2 and 3. has exactly n (n - 1)/2 edges.

Regular graphs . A graph in which all vertices have the same degree is called regular graph. If the degree of each vertex is r, then the graph is called regular degree r. Regular graphs of degree 3, also called cubic(or trivalent) graphs (see, for example, Fig. 2 and 4). Another famous example of a cubic graph is the so-called Count Petersen, shown in fig. 5. Note that every completely disconnected graph is regular of degree 0, and every complete graph K n is regular of degree n - 1.

Platonic graphs . Among regular graphs, the so-called Platonic graphs are especially interesting - graphs formed by the vertices and edges of five regular polyhedra - Platonic solids: tetrahedron, cube, octahedron, dodecahedron and icosahedron. The graph corresponds to a tetrahedron (Fig. 2); the graphs corresponding to the cube and octahedron are shown in Fig. 5 and 6;

Bipartite graphs . Let us assume that the set of vertices of the graph can be divided into two disjoint subsets V 1 and V 2 so that each edge in G connects some vertex from V 1 with some vertex from V 2 (Fig. 7);

then G is called a bipartite graph. Such graphs are sometimes denoted G(V 1, V 2) if one wants to distinguish the two specified subsets. A bipartite graph can also be defined in another way - in terms of coloring its vertices with two colors, say red and blue. A graph is called bipartite if each of its vertices can be colored red or blue so that any edge has one end red and the other blue. It should be emphasized that in a bipartite graph it is not necessary that every vertex in V 1 is connected to every vertex in V 2 ; if this is so and if the graph G is simple, then it is called complete bipartite graph and is usually denoted by where m, n is the number of vertices in V 1 and V 2, respectively. For example, in Fig. 8 shows the graph K 4, 3. Note that the graph has exactly m + n vertices and mn edges. A complete bipartite graph of the form is called a star graph; in Fig. 9 shows a star graph.

Connected graphs . Graph connected, if it cannot be represented as a union of two graphs, and incoherent otherwise. Obviously, every disconnected graph G can be represented as a union of a finite number of connected graphs - each of such connected graphs is called component (connectivity) graph G. (Figure 10 shows a graph with three components.) It is often convenient to prove certain statements for arbitrary graphs first for connected graphs and then apply them to each component separately.

A graph diagram consisting of "isolated" vertices is called zero graph. (Fig.2)

Graphs in which all possible edges are not constructed are called incomplete graphs. (Fig.3)

Graphs in which all possible edges are constructed are called complete graphs. (Fig.4)


If there are arrows on the edges of a graph indicating the direction of the edges, then such a graph is called directed.

The arrow from one job to another in the graph shown in the figure means the sequence of jobs.

You can’t start installing walls without finishing building the foundation; in order to start finishing, you need to have water on the floors, etc.

Degrees of vertices and counting the number of edges.

The number of edges leaving a vertex of the graph is called the degree of the vertex. A vertex of a graph that has an odd degree is called odd, and a vertex that has an even degree is called even.

If the degrees of all vertices of a graph are equal, then the graph is called homogeneous. Thus, any complete graph is homogeneous.

Figure 5 shows a graph with five vertices.

The degree of vertex A will be denoted by St.A.

In the picture:
St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Let us formulate some regularities inherent in certain graphs.

Pattern 1. The degrees of the vertices of a complete graph are the same, and each of them is 1 less than the number of vertices of this graph.

Pattern 2. The sum of the degrees of the vertices of a graph is an even number equal to twice the number of edges of the graph.

This pattern is true not only for a complete graph, but also for any graph.

The number of odd vertices in any graph is even.

Note that if a complete graph has n vertices, then the number of edges will be equal to n(n-1)/2.

A graph that is not complete can be completed to be complete with the same vertices by adding the missing edges. For example, Figure 3 shows an incomplete graph with five vertices. In Figure 4, the edges that transform the graph into a complete graph are depicted in a different color; the collection of vertices of the graph with these edges is called the complement of the graph.

Euler graphs.

A graph that can be drawn without lifting the pencil from the paper is called Eulerian. (Fig.6)

These graphs are named after the scientist Leonhard Euler.


Pattern 3.(follows from the theorem we considered).
It is impossible to draw a graph with an odd number of odd vertices.

Pattern 4. If all the vertices of the graph are even, then you can draw this graph without lifting your pencil from the paper (“with one stroke”), moving along each edge only once. The movement can start from any vertex and end at the same vertex.

Pattern 5. A graph with only two odd vertices can be drawn without lifting the pencil from the paper, and the movement must begin at one of these odd vertices and end at the second of them.

Pattern 6. A graph with more than two odd vertices cannot be drawn " with one stroke».

A figure (graph) that can be drawn without lifting the pencil from the paper is called unicursal.

The graph is called coherent, if any two of its vertices can be connected by a path, that is, a sequence of edges, each of which begins at the end of the previous one.

Figure 7 obviously shows a disconnected graph.

The graph is called incoherent, if this condition is not met.

If, for example, in the figure you draw an edge between vertices D and E, then the graph will become connected.( Fig.8)

In graph theory, such an edge (after removing which the graph from a connected one turns into a disconnected one) is called bridge.

Examples of bridges on Figure 7 edges DE, A3, VZh, etc. could serve, each of which would connect the vertices of “isolated” parts of the graph. ( Fig.8)

A disconnected graph consists of several " pieces" These “pieces” are called the connected components of the graph. Each connected component is, of course, a connected graph. Note that a connected graph has one connected component.

A graph is Eulerian if and only if it is connected and has at most two odd vertices.

Trees.

tree Any connected graph that has no cycles is called.

Cycle is a path in which the beginning and the end coincide.

If all the vertices of a cycle are different, then such a cycle is called elementary(or simple) cycle.

If a cycle includes all the edges of the graph once, then such a cycle is called Euler line (Fig.9a).

In the column on Fig.9b two cycles: 1-2-3-4-1 and 5-6-7-5.

By in a graph from one vertex to another there is a sequence of edges along which a route can be laid between these vertices.

In this case, no edge of the route should appear more than once. The peak from which the route is laid is called the beginning of the journey, the peak at the end of the route - end of the road.

hanging top is a vertex from which exactly one edge emerges ( Fig.10).
(hanging peaks are circled).


For each pair of tree vertices there is a unique path connecting them.

This property is used when finding all the ancestors in a family tree, for example, in the male line, of any person whose pedigree is represented in the form of a family tree, which is “ tree"and in the sense of graph theory.

Every edge in a tree is a bridge.

Indeed, after removing any edge of the tree, it " disintegrates"on two trees.

A graph in which any two vertices are connected by exactly one simple path is tree.

(about the hanging top). Every tree has a hanging top.

. In a tree, the number of vertices is one more than the number of edges.

Isomorphism. Planar graphs and Euler's theorem.

The two graphs are called isomorphic, if they have equal numbers of vertices, and the vertices of each graph can be numbered from 1 to n, so that the vertices of the first graph are connected by an edge if and only if the corresponding vertices of the second graph are connected by an edge.

Let us prove that the graphs shown in Figure 11 are isomorphic.


Let us number the vertices of the first and second graphs from 1 to 4 ( Fig.12).


The first graph connects vertices 1 and 2, 2 and 3, 3 and 4, 1 and 4, 1 and 3, 2 and 4; Note that in the second graph vertices 1 and 2, 2 and 3, 3 and 4, 1 and 4, 1 and 3, 2 and 4 are also connected, therefore, these graphs are isomorphic.

In order to find out whether two graphs are isomorphic, you need to make sure that they have:

• same number of vertices
• If the vertices of one graph are connected by an edge, then the corresponding vertices of another graph are also connected by an edge.

A graph that can be drawn so that its edges do not intersect anywhere except at its vertices is called flat or planar.

Euler. For a correctly drawn connected planar graph, it has the equality: V-E+F=2, where V is the number of vertices, E is the number of edges, F is the number of pieces. (The equality V -E+F=2 is usually called Euler’s formula).

A graph in which every vertex is connected to an edge of every other vertex is called complete.

Pontryagin – Kuratovsky. A graph is flat if and only if it does not contain (in the topological sense) a graph with six vertices of the “house-well” type and a complete graph with five vertices.

(Mainly used in ancient problems about houses and wells, the essence of which boils down to clarifying the question - whether the graph in question is flat or not, Fig.13)

Directed graphs.

There are significant classes of practical problems that cannot be solved using the previously discussed types of graphs.

For example, the map of roads and squares of a city is depicted using a flat graph. But what if you need to use this scheme to travel around the city by car, and the traffic on some (or all) streets is one-way?

Then arrows, located, for example, directly on the edges - streets of the city diagram (graph) in question, can help to navigate this situation.

A graph with arrows on its edges is called oriented.

Yield rate vertex of a directed graph is the number of edges for which this vertex is the beginning (number of edges, " coming out"from the top).

Degree of entry of a vertex in a directed graph is the number of edges for which this vertex is the end (the number of edges, " incoming"to the top).

Yes, on Figure 15 shows a directed graph ABCD. The entry and exit degrees of some of its vertices are as follows:
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.

A path in a directed graph from vertex A1 to vertex An is a sequence of oriented edges A1A2, A2A3, ..., Аn-1Аn, in which the end of each previous edge coincides with the beginning of the next and each edge occurs in this sequence only once.

On figure.15 examples of paths in a directed graph are shown. Moreover, the first two paths are simple - none of the vertices is contained in it more than once. The third way is not simple, i.e. to. through the vertex G the path " passed"twice.

Directed cycle is called a closed path in a directed graph.

On Figure 15 Examples of oriented cycles are given in the last two graphs. A cycle, like any other path in a graph, has a length that is determined by the number of edges in this path.

So, in Figure 16, the paths from A to D can be different and have different lengths.
The first path has length 2, the second - 3,
and the third one is 4.

The length of the “shortest path” between two vertices is called the distance between them. So the distance between vertices A and D in the graph of Figure 16 is 2; written like this: S(BP)=2.

If in a directed graph it is impossible to “pass” from one vertex to another, then the distance between them is called infinite (indicated by the infinity symbol). Thus, the distance between vertices B and D of the graph presented in Figure 17 is infinite: S(DB) = ∞

Directed graphs in economics are actively used in network planning, in mathematics - in game theory, set theory; when solving many problems, in particular combinatorial ones.