Application of graph theory in various fields of activity. Application of graphs

The beginning of graph theory is unanimously attributed to 1736, when L. Euler solved the problem of Königsberg bridges, which was popular at that time. However, this result remained the only result of graph theory for more than a hundred years. Only in the middle of the 19th century, the electrical engineer G. Kirchhoff developed the theory of trees for the study of electrical circuits, and the mathematician A. Cayley, in connection with the description of the structure of hydrocarbons, solved enumeration problems for three types of trees.

Born from solving puzzles and entertaining games (problems about a chess knight, about queens, “travel around the world”, problems about weddings and harems, etc.), graph theory has now become a simple, accessible and powerful means of solving problems related to a wide range of problems. Graphs are literally omnipresent. In the form of graphs, you can, for example, interpret road maps and electrical circuits, geographical maps and molecules chemical compounds, connections between people and groups of people. Over the past four decades, graph theory has become one of the most rapidly developing branches of mathematics. This is driven by the demands of a rapidly expanding application field. It is used in the design of integrated circuits and control circuits, in the study of automata, logical circuits, program block diagrams, in economics and statistics, chemistry and biology, in scheduling theory. To a large extent, mathematical methods are now penetrating science and technology through graph theory.

This paper examines not the proper problems of graph theory, but how it is used in a school geometry course.

Therefore, the relevance of the research topic is due, on the one hand, to the popularity of graphs and related research methods, which organically permeate the different levels almost all modern mathematics, and on the other hand, a holistic system for its implementation in the geometry course has not been developed.

The purpose of the study is to study the use of graphs in a school geometry course.

The object is the process of teaching geometry.

Subject – class and extracurricular work

Objectives: 1) determine the essence and content of the use of graphs in a school geometry course;

2) develop a PMC for conducting geometry lessons in grades 7-9.

The leading topic is the construction of a graph model for proving geometric theorems.

Theoretical basis:

1. Graph theory, which arose in 1736 (Leonard Euler (1708-1783), received rapid development and remains relevant today, because in Everyday life Graphic illustrations, geometric representations and other techniques and methods of visualization are increasingly used.

1. Graph theory is used in various areas of modern mathematics and its numerous applications (Lipatov E. P.)

2. Graph theory is used in such areas of mathematics as mathematical logic, combinatorics, etc.

The theoretical significance of the work lies in:

Identification of areas of application of graph theory;

Using graph theory to study geometric theorems and problems;

The practical significance of the work lies in the use of graphs in proving geometric theorems and solving problems.

As a result of this work, the following was created:

Software and methodological complex for conducting geometry lessons in grades 7-9.

The most difficult thing in finding a solution to a problem is establishing a chain of logical consequences that leads to a proven statement. In order to reason logically competently, it is necessary to develop the skills of such thinking that would help to build disparate geometric facts into logical relationships.

To develop the skills of a culture of thinking, forms of written speech of students play a special role. Written forms of work are the most important type of activity that develops stable skills in logical reasoning when proving theorems and solving problems. The form of recording the conditions of the problem, reasonable abbreviations and notations in calculations and proofs of problems discipline thinking and promote geometric vision. As you know, vision gives birth to thinking. A problem arises: how to establish logical connections between disparate geometric facts and how to form them into a single whole. The method of graph diagrams allows you to see the progress of proving theorems and solving problems, which makes the proof more visual and allows you to briefly and accurately present the proofs of theorems and solving problems.

A tree graph is used for this.

The vertices of the “tree” (the conditions of the theorem or problem and the sequence of logical connectives) are depicted by rectangles with information placed in them, which are then connected by arrows. The end of the graph diagram contains the statement to be proved. The described form of proving theorems and solving problems is useful and convenient for students, since it makes it possible to easily identify the main stages of proving the theorems and solving the problem.

Research part.

Section 1. Study of the history of the emergence of graph theory.

The founder of graph theory is considered to be the mathematician Leonhard Euler (1707-1783). The history of this theory can be traced through the correspondence of the great scientist. Here is a translation of the Latin text, which is taken from Euler’s letter to the Italian mathematician and engineer Marinoni, sent from St. Petersburg on March 13, 1736.

“I was once asked a problem about an island located in the city of Königsberg and surrounded by a river across which seven bridges are thrown. The question is whether anyone can go around them continuously, passing only once through each bridge. And then I was informed that no one still could not do this, but no one has proven that it is impossible. This question, although trivial, seemed to me, however, worthy of attention in that neither geometry, nor algebra, nor combinatorial art are sufficient to solve it. After much thought, I found an easy rule, based on a completely convincing proof, with the help of which it is possible to immediately determine in all problems of this kind whether such a detour can be made through any number of bridges located in any way or not. so that they can be represented in the following figure, in which A denotes the island, and B, C and D the parts of the continent separated from each other by branches of the river.The seven bridges are designated by the letters a, b, c, d, e, f, g ".

Regarding the method he discovered to solve problems of this kind, Euler wrote

“This solution, by its nature, apparently has little to do with mathematics, and I do not understand why one should expect this solution from a mathematician rather than from any other person, for this decision is supported by reasoning alone, and there is no need to involve to find this solution, any laws inherent in mathematics. So, I do not know how it turns out that questions that have very little to do with mathematics are more likely to be solved by mathematicians than by others."

So is it possible to get around the Königsberg bridges by passing only once over each of these bridges? To find the answer, let's continue Euler's letter to Marinoni:

"The question is to determine whether it is possible to bypass all these seven bridges, passing through each only once, or not. My rule leads to the following solution to this question. First of all, you need to look at how many areas there are, separated by water - such , which have no other passage from one to another, except through a bridge.In this example, there are four such sections - A, B, C, D. Next, you need to distinguish whether the number of bridges leading to these individual sections is even or odd. So, in our case, five bridges lead to section A, and three bridges each to the rest, i.e. The number of bridges leading to individual sections is odd, and this alone is enough to solve the problem. Once this is determined, we apply the following rule : if the number of bridges leading to each separate section were even, then the detour in question would be possible, and at the same time it would be possible to start this detour from any section.If, however, two of these numbers were if they were odd, because only one cannot be odd, then even then the transition could be completed, as prescribed, but only the beginning of the detour must certainly be taken from one of those two sections to which an odd number of bridges leads. If, finally, there were more than two sections to which an odd number of bridges lead, then such a movement would be impossible at all; if other, more serious problems could be brought here, this method could be of even greater benefit and should not be neglected."

The rationale for the above rule can be found in a letter from L. Euler to his friend Ehler dated April 3 of the same year. We will retell below an excerpt from this letter.

The mathematician wrote that the transition is possible if there are no more than two areas in the fork of the river, to which an odd number of bridges lead. To make it easier to imagine this, we will erase the already traversed bridges in the figure. It’s easy to check that if we start moving in accordance with Euler’s rules, cross one bridge and erase it, then the figure will show a section where again there are no more than two areas to which an odd number of bridges leads, and if there are areas with an odd number bridges we will be located in one of them. Continuing to move on like this, we will cross all the bridges once.

The story of the bridges of the city of Königsberg has a modern continuation.

Problem There are seven islands on the lake, which are connected to each other as shown in Figure 2. To which island should a boat take travelers so that they can cross each bridge and only once? Why can't travelers be transported to Island A?

Solution. Since this problem is similar to the problem of the Königsberg bridges, when solving it we will also use Euler’s rule. As a result, we get the following answer: the boat must take travelers to island E or F so that they can cross each bridge once. From the same Euler rule it follows that the required detour is impossible if it starts from island A.

Subsequently, Koenig (1774-1833), Hamilton (1805-1865), and modern mathematicians C. Berge, O. Ore, A. Zykov worked on graphs.

Historically, graph theory originated more than two hundred years ago in the process of solving puzzles. For a very long time she was on the sidelines of the main directions of scientific research, in the kingdom of mathematics she was in the position of Cinderella, whose talents were fully revealed only when she found herself in the center of general attention.

The first work on graph theory, owned by the famous Swiss mathematician L. Euler, appeared in 1736. Graph theory received an impetus for development at the turn of the 19th and 20th centuries, when the number of works in the field of topology and combinatorics, with which it is closely connected, sharply increased kinship. Graphs began to be used in the construction of electrical circuit diagrams and molecular circuits. As a separate mathematical discipline, graph theory was first presented in the work of the Hungarian mathematician Koenig in the 30s of the twentieth century.

Recently, graphs and related research methods have organically permeated almost all modern mathematics at different levels. Graph theory is considered as one of the branches of topology; it is also directly related to algebra and number theory. Graphs are effectively used in planning and control theory, scheduling theory, sociology, mathematical linguistics, economics, biology, medicine, and geography. Graphs are widely used in areas such as programming, finite state machine theory, electronics, in solving probabilistic and combinatorial problems, shortest distance, etc. Mathematical entertainment and puzzles are also part of graph theory. Graph theory is developing rapidly and finding new applications.

Section 2. Basic types, concepts and structure of graphs.

Graph theory is a mathematical discipline created by the efforts of mathematicians, therefore its presentation includes the necessary strict definitions.

A graph is a collection of a finite number of points, called vertices of the graph, and lines connecting some of these vertices in pairs, called edges or arcs of the graph.

No. Name of graph Definition Figure Example of using this type of graph

1 Zero graph Vertices of the graph that do not belong Problem: Arkady, Boris. Vladimir, Grigory and Dmitry exchanged handshakes at the meeting; each shook hands with each other once. How many edges there are are called isolated. handshakes were done? The situation corresponding to the moment when handshakes have not yet been made is the dot pattern shown in the figure.

A graph consisting only of isolated vertices is called a null graph.

Notation: O" – a graph with vertices and no edges

2 Complete graphs A graph in which each pair of vertices Note that if a complete graph has n vertices, then the number of edges will be All handshakes have been completed.

Designation: U" – a graph consisting of n 10.

vertices and edges connecting all possible pairs of these vertices. Such a graph can be represented as an n-gon in which all diagonals are drawn

3 Incomplete graphs Graphs in which all handshakes have not yet been completed, handshakes A and B, A and D, D and possible edges have been shaken, are called incomplete G, C and D.

4 Path in the graph. Cycle. A path in the graph from one vertex to another. At point A there is a garage for a snowplow. The driver of the car was called to remove snow from the streets of the part of the city shown in the picture. Can he have a sequence of edges along which he can finish his work at the intersection where the garage is located, if the driver can pass along each street between these streets in his section of the city only once?

peaks.

In this case, no edge of the route should appear more than once. Vertex, from It is impossible, since a closed path passing along all edges of the graph, and along which the route is laid, is said to exist for each edge only once, if the degrees of all vertices of the graph are even.

the beginning of the path, the peak at the end of the route -

end of the road. A cycle is a path in which the figure shows, using a graph, a diagram of roads between populated areas whose beginning and end coincide. In simple points.

a cycle is a cycle that does not pass. For example, from point A (the vertex of the graph) to point H can be reached by various routes: ADGH, AEH, AEFCEH, ABCEH.

through one of the vertices of the graph more than one. How does the route AEH differ from the route AEFCEH?

times. Because on the second route we visited the “crossroads” at point E twice.

This route is longer than AEH. The AEH route can be obtained from the route

If the cycle includes all the edges AEFCEH, “crossing out” the FCE route from the last one.

graph once at a time, then such a cycle Route AEH is a path in the graph, but route AEFCEH is not a path.

called the Euler line.

Connected and disconnected graphs. Determination 1: Is it possible to make a frame of a cube with an edge length from a wire 12 dm long

Are two vertices of a graph called connected, 1 dm, without breaking the wire into pieces?

if there is a path in the graph with ends at these vertices. If such a path does not exist, the vertices are said to be not connected.

Since a path passing along all edges of the graph, and along each edge only once, exists only in the following cases:

1) when the degree of each vertex is even (the path is closed)

2) when there are only two vertices with an odd degree.

Definition 2:

A graph is called connected if any pair of its vertices is connected.

A graph is called disconnected if it has at least one disconnected pair of vertices.

6 Trees A tree is any connected graph, Appendix No. 1. Family tree of Zholmurzaeva Tomiris.

tops. A disconnected graph consisting entirely of trees is called a forest.

7 Isomorphic graphs. The graphs shown in the figure provide the same information. Such graphs are called isomorphic (identical).

8 The concept of a planar graph A graph that can be represented on the Problem. Three planes live in three different houses and neighbors have quarreled among themselves. Not far from their houses, where its ribs intersect, there are three wells. Is it possible from only at the tops, called each house to be laid flat to each of the wells. path so that no two of them intersect?

Solution: After drawing eight paths, you can make sure that it is not possible to draw a ninth one that does not intersect with any of the previously drawn paths.

Let's construct a graph whose vertices

A, B, C, 1, 2, 3

the conditions of the problem correspond to houses and wells, and we will try to prove that the ninth path - an edge of the graph that does not intersect the other edges - cannot be drawn.

The edges drawn in the graph in the figure

A1, A2, A3 and B1, B2, VZ (corresponding to the paths from houses A and B to all wells).

The constructed graph divided the plane into three regions: X, Y, Z. Vertex B, depending on its location on the plane, falls into one of these three regions. If you consider each of the three cases of "hitting" the vertex

B to one of the areas X, Y or Z, then make sure that each time one of the vertices of the graph is 1, 2 or 3

(one of the wells) will be “inaccessible” for vertex B (that is, it will not be possible to draw one of the edges B1, B2 or B3 that would not intersect the edges already existing in the graph).

The answer to the problem question will be: “No!”

Directed Graphs An edge of a graph is called a directed edge if one of its vertices is considered the beginning and the other the end of this edge.

A graph in which all edges are directed is called a directed graph.

So, I reviewed the basic concepts of graph theory, without which it would be impossible to prove theorems, and, consequently, solve problems.

Conclusion on the work done:

I learned to structure all information material into a table;

Arrangement theoretical material contribute to a visual understanding of the types of graphs and their application;

I worked on examples of using graph theory in drawing up my family tree.

Appendix No. 1.

GENEOLOGICAL TREE

Construct a family tree of Zholmurzaeva Tomiris.

Solution method.

Graphical way to solve the problem.

A graphical way to solve the problem is to draw a “tree of logical conditions”. “Tree” expresses in the form of a simple drawing the logical relationship between relatives. Each generation on the tree corresponds to one branch.

I took my family tree as an example.

Section 3. Application of graph theory.

We encounter graphs more often than is possible at first glance. Examples of graphs include any road map, electrical diagram, drawing of polygons, etc. For a long time, it was believed that graph theory is used mainly in solving logical problems. When solving logical problems, it is often difficult to remember the numerous conditions given in the problem and to establish connections between them. Graphs help to solve such problems, making it possible to visually represent the relationships between the data of the problem. Graph theory itself was considered a part of geometry. However, in the twentieth century, broad applications of graph theory were found in economics, biology, chemistry, electronics, network planning, combinatorics and other fields of science and technology. As a result, it began to develop rapidly and turned into an independent branched theory. The solution of many mathematical problems is simplified if it is possible to use graphs. Presenting data in the form of a graph makes it clearer. Many proofs are also simplified and become more convincing if you use graphs.

3. 1. Application of graphs in geometric problems and theorems.

Using graphs, you can easily establish chains of logical consequences that lead to the statement being proven. Briefly and accurately state the proof of the theorem and the solution to the problem.

Prove that for an isosceles triangle, the bisectors drawn from the vertices at the base are equal.

Methods of solutions.

Proof of the problem using reasoning.

Let ABC be an isosceles triangle with

B1 A1 base AB and bisectors AA1 and BB1.

Let's consider ∆АВВ1 and ∆ВАА1. They have ∟В1АВ=

∟A1BA as the angles at the base of the isosceles triangle ∆ABC. ∟АВВ1= ∟А1АВ

A B since AA1 and BB1 are the bisectors of the angles at the base of an isosceles triangle. AB is the common side. Means

∆АВВ1 = ∆ВАВ1 along the side and two adjacent angles. From the equality of triangles it follows that their sides AA1 and BB1 are equal.

Proof of the problem using a graph.

Prove: AA=BB

We use the graph for reasoning. The vertices of the graph are the conditions of the theorem or problem and the stages of the proof.

The edges of the graph are logical consequences. The end of the graph diagram is a provable statement.

Color is used to highlight the components. The theorem and problem conditions are blue. The statement being proved is red. Stages of proof - black.

The described form of proving theorems and solving problems is useful and convenient for students, since it makes it possible to highlight the main stages of proving the theorems and solving the problem.

3. 2. Software and methodological complex.

a) Teacher's manual.

The proposed manual is compiled in accordance with the textbook on geometry for grades 7-9 by A.V. Pogorelov. Its main purpose is to provide the process of studying geometry with the necessary visual aids, to assist the teacher in teaching geometry: to facilitate the process of proving theorems, mastering theoretical material in the process of solving problems. Graph diagrams are multifaceted in nature and, depending on the goals and forms of classes, can be used in different ways: as illustrative, aimed at enhancing clarity when explaining new theoretical material, when generalizing and systematizing new material (graph diagrams with theorems); as cards used when conducting individual and frontal surveys (graph diagrams with tasks). This manual comes with a student workbook. A workbook can be used to organize independent work students during and after school hours.

b) Workbook for students.

The manual is made in the form of a workbook. The manual includes 28 graph diagrams with theorems and 28 graph diagrams with tasks. Graph diagrams contain the main program material, which is presented with the necessary clarity and represents the framework of the solution. Students sequentially fill in the empty cells with information that makes up the solution to the problem.

Color is used to highlight the components. The conditions of the theorem and problem are blue, the statement to be proved is red, the stages of the proof are black.

The manual is useful for students in grades 7-9.

c) Electronic manual.

Results of the work and their discussion. The project is the result of a two-year study of the use of graphs in a school mathematics course.

Creation programmatically – methodological complex and its implementation was carried out during:

Conducting classes for the Aristotle club on the topic “Solving logical problems using graphs.”

Applications of graphs in proofs of geometric theorems and problems

In geometry lessons in grades 8 and 9.

Presentations with a project at school scientific and practical conferences.

CONCLUSION.

Summing up the results of the study of the use of graphs in a school geometry course, I came to the following conclusion:

1. The advantage of graph proof of theorems and problem solving over the traditional one is the illustration of the dynamics of proof of theorems and problems.

2. Introduction to the process of proving geometric theorems and problems of the graph-scheme method helps to strengthen students’ skills in constructing a proof.

3. Developed software and methodological complex for studying geometry in grades 7-9: a) teacher’s manual; b) workbook for students; c) the electronic manual is useful for students in grades 7-9.

Educational edition

Yuyukin Nikolay Alekseevich

LR no. Signed for seal

Uch. Ed. l.. , .

Voronezh State Technical University

394026 Voronezh, Moskovsky Ave. 14

DIRECTORY OF MAGNETIC DISK

Department of Higher Mathematics and Physical and Mathematical Modeling

ON THE. Yuyukin

DISCRETE MATHEMATICS Part 1. Elements of graph theory

Tutorial

ON THE. Yuyukin

DISCRETE MATHEMATICS Part 1. Elements of graph theory

Tutorial

Voronezh 2004

INTRODUCTION

This manual can be used in the course “Discrete Mathematics” by VSTU students studying in the following specialties:

090102 – Computer security;

090105 – Comprehensive provision of information security of automated systems;

090106 - Information security of telecommunication systems.

The discipline “Discrete Mathematics” ensures the acquisition of knowledge and skills in accordance with the state, general education standard, and at the same time contributes to the acquisition fundamental education, formation of worldview and development of logical thinking.

Graph theory is an effective tool for formalizing modern engineering problems associated with discrete objects. It is used in the design of integrated circuits and control circuits, the study of automatic machines and logic circuits, in system analysis, automated production control, in the development of computer and information networks, in circuit design and design-topological design, etc.

IN textbook outlines the fundamentals, basic methods and algorithms of graph theory. Here we present n-graphs and digraphs; isomorphisms; trees; Euler graphs; planar graphs; coverings and independent sets; strong connectivity

V digraphs; Markov chain graph analysis; algorithms for finding shortest paths in graphs; Hamiltonian cycle search problem

V graph; traveling salesman problem; enumeration of graphs and mappings; extreme tasks; optimization problems; universal tasks; branch and bound method; and also develop practical skills in using the above concepts.

The purpose of the course is to develop students’ theoretical knowledge, practical skills and abilities in the field of modeling processes and phenomena in natural science and technology.

ke, with the ability to use mathematical symbols to express the quantitative and qualitative relationships of objects necessary to perform official activities in the field of information security at a high professional level.

The following tasks serve to achieve this goal:

study the widest possible range of graph theory concepts;

gain skills in solving educational and practical problems;

master optimization methods;

develop skills in setting and solving information problems, modeling and analyzing information using graphs.

The discipline “Discrete Mathematics” is one of the applied mathematical disciplines. It is based on the knowledge acquired by students while studying the disciplines “Algebra” and “Mathematical Logic and Theory of Algorithms”. The knowledge and skills acquired in the study of the discipline “Discrete Mathematics” are used in the study general professional and special disciplines.

1. BASIC CONCEPTS OF GRAPH THEORY.

1.1. Problems of graph theory.

Graph theory is a branch of mathematics that studies systems of connections between different objects, just as is done with the concept of a relation. However, an independent definition of the graph simplifies the presentation of the theory and makes it more understandable and visual.

The first problems of graph theory were related to solving entertainment problems and puzzles.

First task. The problem of the Königsberg bridges was posed and solved by Euler in 1786. The city was located on the banks and two islands of the Pregolya River. The islands were connected between each other and the shores by seven bridges, as shown in the figure.

The question arose: is it possible to leave the house and return back, crossing each bridge exactly once?

Second task. The problem of three houses and three wells. There are three houses and three wells.

It is required to draw a path from each house to each well so that the paths do not intersect. The task was

solved by Pontryagin and independently of him by Kuratovsky in

Third task. About four colors. Color any map on a plane with four colors so that no two adjacent areas are painted with the same color.

Many results from graph theory are used to solve practical problems in science and technology. Thus, in the mid-19th century, Kirchhoff used graph theory to calculate complex electrical circuits. However, as a mathematical discipline, graph theory was formed only in the 30s of the 20th century. In this case, graphs are considered as some abstract mathematical objects. They are used in the analysis and synthesis of circuits and systems, in network planning and management, operations research, programming, modeling the life of an organism and other areas.

1.2. Basic definitions.

A graph G= (V,E) is a collection of two sets - a non-empty set of vertices V and a set of unordered and ordered pairs of vertices E. In what follows we will consider finite graphs, i.e. graphs with a finite set of vertices and a finite family of pairs. An unordered pair of vertices is called an edge, and an ordered pair is called an arc.

Typically, a graph is represented by a diagram: vertices are dots (or circles), edges are lines of arbitrary configuration. An arrow additionally indicates its direction on the arc. Note that when depicting a graph, the carrier

the geometric properties of the ribs (length, curvature), as well as mutual arrangement vertices on the plane.

Vertices that do not belong to any edge (arc) are called isolated. Vertices connected by an edge or arc are called adjacent. An edge (arc) and any of its two vertices are called incident.

They say that an edge (u,v) connects vertices u and v, and an arc (u,v) starts at vertex u and ends at vertex v, with u called the beginning and v the end of this arc.

A pair of vertices can be connected by two or more edges (arcs in the same direction). Such edges (arcs) are called multiple. An arc (or edge) can start or end at the same vertex. Such an arc (edge) is called a loop. A graph containing loops is called a pseudo graph. A graph that has multiple edges (arcs) is called a multigraph.

A graph without loops or multiple edges is called simple. A simple graph is called complete if for any pair of its vertices there is an edge (arc) connecting them. A complete graph with n vertices is denoted by K n. For example, these are graphs

A graph consisting of one isolated vertex (K 1) is called trivial.

The complement of a graph G is a graph G that has the same vertices as the graph G and contains those edges that need to be added to the graph G to obtain a complete graph.

To every non-digrapher canonically matches a directed graph with the same set of vertices, in which each edge is replaced by two arcs incident to the same vertices and having opposite directions.

1.3. Degrees of graph vertices.

The degree (valency) (notation d (v) or deg (v)) of a vertex v of a simple graph G is the number of edges or arcs incident to a given vertex v. When calculating the valency of the vertices of a pseudograph, each loop should be counted twice.

If the degrees of all vertices of an n-graph are equal to k, then the graph is called regular (uniform) degree k. If the degree of a vertex is 0, then it is isolated. If the degree of a vertex is 1, then the vertex is called a terminal vertex (hanging, dead-end).

For a digraph, the number of arcs emanating from vertex v is called

varies semi-degree of outcome				(v), and incoming ones – semi-step-

new call d			(v), In this case the relation d (v)=

	(v)+	(v).

Euler's theorem: The sum of the degrees of the vertices of a graph is

double the number of ribs, i.e.

d(vi)



			(v)

Where n is the number of vertices; m – number

ribs (arches). This statement is proven by the fact that when calculating the sum of degrees of vertices, each edge is taken into account twice - for one end of the edge and for the other.

1.4. Graph isomorphism.

A graph is called labeled (or renumbered) if its vertices differ from each other in some way.

labels (numbers). The count is considered completely given in the strict sense, if the numbering of its vertices and edges is fixed. In this case, graphs G 1 and G 2 are called equal (designation G 1 = G 2), if their sets of vertices and edges coincide. Two graphs or pseudographs G 1 = (V 1 ,E 1 ) and G 2 = (V 2 ,E 2 ) are called

	isomorphic (notation G	if they exist

	one-to-one mappings: 1)	: V 1 V 2
: E 1 E 2 such that for any two vertices u, v in the graph
	the relation ((u, v)) ((u), (v)) is valid.

	Two simple graphs (without loops and multiple edges) G 1		and G 2

turn out to be isomorphic if there are mutually identical

value mapping

: V 1 V 2

So what?

(u , v ) ((u ), (v )) .

Thus, graphs that differ only in the numbering of vertices and edges are isomorphic. Graph isomorphism is an equivalence relation because it has the properties:

Reflexivity -

G1,

and the bijection

is an identical function.

Symmetry.

with bijection

Transitivity.

G 1 G 2

bijection

1,a

with bijection

then G G

with bijection

2 (1 ) .

Graph theory finds application, for example, in geographic information systems (GIS). Existing or newly designed houses, structures, blocks, etc. are considered as vertices, and the roads, utility networks, power lines, etc. connecting them are considered as edges. The use of various calculations performed on such a graph allows, for example, to find the shortest detour route or the nearest grocery store, or to plan the optimal route.

Graph theory contains a large number of unsolved problems and as yet unproven hypotheses.

The main areas of application of graph theory:

In chemistry (to describe structures, paths of complex reactions, the phase rule can also be interpreted as a graph theory problem); Computational chemistry is a relatively young area of chemistry based on the application of graph theory. Graph theory is the mathematical basis of chemoinformatics. Graph theory makes it possible to accurately determine the number of theoretically possible isomers in hydrocarbons and other organic compounds;

In computer science and programming (graph diagram of the algorithm);

In communication and transport systems. In particular, for routing data on the Internet;

In economics;

In logistics;

In circuit design (the topology of interconnections of elements on a printed circuit board or microcircuit is a graph or hypergraph).

There is a special type of graph, tree.Tree is a connected acyclic graph. Connectedness means the presence of paths between any pair of vertices, acyclicity means the absence of cycles and the fact that there is only one path between pairs of vertices. On Fig 1.3 presented binary tree.

Binary tree- a tree data structure in which each node has no more than two descendants(children). Typically the first one is called parent node, and the children are called left And right heirs.

Matrix representation of graphs. Incident matrix.

The development of algorithmic approaches to the analysis of graph properties requires certain methods for describing graphs that are more suitable for practical calculations, including using a computer. Let's look at the three most common ways to represent graphs.

Suppose that all vertices and all edges of an undirected graph or all vertices and all arcs (including loops) of a directed graph are numbered starting from one. A graph (undirected or directed) can be represented as a matrix of type , where is the number of vertices, and is the number of edges (or arcs). For an undirected graph, the elements of this matrix are specified as follows:

For a directed graph, the matrix elements are specified as follows:

A matrix of type defined in this way is called incident matrix.

An example of obtaining an incident matrix. For the graph shown below ( Rice. 2.1 aFigure 2.1 b).

Fig. 2.1 a Fig. 2.1 b

Adjacency matrix.

Despite the fact that representing a graph in the form of an incidence matrix plays a very important role in theoretical research, in practice this method is very ineffective. First of all, the matrix has only two non-zero elements in each column, which makes this method of representing a graph uneconomical when there are a large number of vertices. In addition, solving practical problems using an incident matrix is very labor-intensive.

Let us estimate, for example, the time costs of solving such a simple problem in a directed graph using the incidence matrix: for a given vertex, find its “environment” - the set of successors and the set of predecessors of the vertex, i.e. the set of all vertices directly reachable from, and the set of all vertices from which it is directly reachable.

To solve this problem on the incidence matrix of a directed graph, you need to go along the row with the number until a non-zero element appears (+1 or –1). If +1 is detected, in the corresponding column you need to find the line in which the number –1 is written. The number of the line in which this number appears gives the number of the vertex directly reachable from this vertex. If -1 is detected, you need to find the row in the column that contains 1 and get the number of the vertex from which this vertex is directly accessible. To get the entire “environment” you need to do the specified search for all non-zero elements kth line. The most time-consuming procedure is to find a non-zero element in a column. The number of such search procedures is equal to the degree of the vertex. In this case, we will say that the complexity of the algorithm for analyzing the environment of a vertex is (order).

It can be seen that searching for the “environment” of all vertices will take time on the order of the product of the number of vertices of a directed graph by the sum of the degrees of all vertices, which, as can be shown, is proportional to the number of arcs of the directed graph. Thus, the complexity of the “environment” search algorithm is , i.e. the search takes time on the order of the product of the number of vertices and the number of arcs.

A more efficient matrix structure representing a graph is vertex adjacency matrix, or Boolean matrix graph. This is a square matrix of order B n, the elements of which are defined as follows:

for an undirected graph:

for a directed graph:

For the graph shown below ( Rice. 2.2 a) the incidence matrix will be the matrix presented on ( Figure 2.2 b).

The text of the work is posted without images and formulas.
Full version work is available in the "Work Files" tab in PDF format

INTRODUCTION

“In mathematics it is not the formulas that should be remembered, but the process of thinking...”

E. I. Ignatiev

Graph theory is currently an intensively developing branch of mathematics. This is explained by the fact that many objects and situations are described in the form of graph models, which is very important for the normal functioning of social life. It is this factor that determines the relevance of their more detailed study. Therefore, the topic of this work is quite relevant.

Target research work: find out the features of the application of graph theory in various fields of knowledge and in solving logical problems.

The goal identified the following tasks:

get acquainted with the history of graph theory;

study the basic concepts of graph theory and the main characteristics of graphs;

show the practical application of graph theory in various fields of knowledge;

Consider ways to solve problems using graphs and create your own problems.

An object research: the sphere of human activity for the application of the graph method.

Item Research: section of mathematics “Graph Theory”.

Hypothesis. We hypothesize that learning graph theory can help students solve logic problems in mathematics, which will shape their future interests.

Methods research work:

During our research, the following methods were used:

1) Working with various sources of information.

2) Description, collection, systematization of material.

3) Observation, analysis and comparison.

4) Preparation of tasks.

Theoretical and practical significance This work is determined by the fact that the results can be used in computer science, mathematics, geometry, drawing and classroom hours, as well as for a wide range of readers interested in this topic. The research work has a clear practical orientation, since in the work the author presents numerous examples of the use of graphs in many fields of knowledge, and has drawn up his own tasks. This material can be used in elective mathematics classes.

CHAPTER I. THEORETICAL REVIEW OF THE MATERIAL ON THE TOPIC OF RESEARCH

In mathematics, a “graph” can be depicted as a picture, which represents a number of points connected by lines. "Count" comes from the Latin word "graphio" - I write, like a well-known noble title.

In mathematics, the definition of a graph is given as follows:

The term "graph" in mathematics is defined as follows:

Graph - this is a finite set of points - peaks, which can be connected by lines - ribs .

Examples of graphs include drawings of polygons, electrical circuits, schematic representations of airlines, subways, roads, etc. A family tree is also a graph, where the vertices are members of the clan, and family ties act as the edges of the graph.

Rice. 1 Graph Examples

The number of edges that belong to one vertex is called graph vertex degree . If the degree of a vertex is an odd number, the vertex is called - odd . If the degree of a vertex is an even number, then the vertex is called even.

Rice. 2 vertex of the graph

Null graph is a graph consisting only of isolated vertices that are not connected by edges.

Complete graph is a graph in which each pair of vertices is connected by an edge. An N-gon, in which all diagonals are drawn, can serve as an example of a complete graph.

If you choose a path in a graph where the starting and ending points coincide, then such a path is called graph cycle . If each vertex of the graph is passed through at most once, then cycle called simple .

If every two vertices in a graph are connected by an edge, then this connected graph. The graph is called unrelated , if it contains at least one pair of unconnected vertices.

If a graph is connected but does not contain cycles, then such a graph is called tree .

The Count's Path is a sequence in which every two adjacent edges that share a common vertex occur only once.

Length of the shortest chain of vertices a and b is called distance between the peaks a and b.

Vertex A called center graph, if the distance between the vertices A and any other vertex is the smallest possible one. There is such a distance radius graph.

The maximum possible distance between any two vertices of a graph is called diameter graph.

Graph coloring and application.

If you look closely at a geographical map, you can see railways or highways, which are graphs. In addition, there is a graph on the map, which consists of borders between countries (districts, regions).

In 1852, English student Francis Guthrie was given the task of coloring a map of Great Britain, highlighting each county in a separate color. Due to the small selection of paints, Guthrie reused them. He selected the colors so that those counties that shared a common section of the border were necessarily painted in different colors. The question arose as to what is the minimum amount of paint needed to color various maps. Francis Guthrie suggested, although he could not prove, that four colors would be sufficient. This problem was heatedly discussed in student circles, but was later forgotten.

The "four color problem" aroused increasing interest, but was never solved, even by eminent mathematicians. In 1890 English mathematician Percy Heawood proved that five colors are enough to color any map. It was only in 1968 that they were able to prove that 4 colors would be enough to color a map that depicts less than forty countries.

In 1976, this problem was solved using a computer by two American mathematicians Kenneth Appel and Wolfgangt Haken. To solve it, all cards were divided into 2000 types. A computer program was created that examined all types in order to identify cards for which four colors would not be enough to color. The computer could not study only three types of maps, so mathematicians studied them on their own. As a result, it was found that 4 colors would be enough to color all 2000 types of cards. They announced a solution to the problem of four colors. On this day, the post office at the university where Appel and Haken worked put a stamp on all stamps with the words: “Four colors are enough.”

You can imagine the problem of four colors a little differently.

To do this, consider an arbitrary map, presenting it in the form of a graph: the capitals of states are the vertices of the graph, and the edges of the graph connect those vertices (capitals) whose states have a common border. To obtain such a graph, the following problem is formulated: it is necessary to color the graph using four colors so that the vertices that have a common edge are colored with different colors.

Euler and Hamiltonian graphs

In 1859, the English mathematician William Hamilton released a puzzle - a wooden dodecahedron (dodecahedron), the twenty vertices of which were marked with studs. Each peak had the name of one of the largest cities in the world - Canton, Delhi, Brussels, etc. The task was to find a closed path that goes along the edges of the polyhedron, visiting each vertex only once. To mark the path, a cord was used, which was hooked onto nails.

A Hamilton cycle is a graph whose path is a simple cycle that passes through all the vertices of the graph once.

The city of Kaliningrad (formerly Koenigsberg) is located on the Pregel River. The river washed two islands, which were connected to each other and to the banks by bridges. The old bridges are no longer there. The memory of them remains only on the map of the city.

One day, a city resident asked his friend if it was possible to walk across all the bridges, visit each one only once, and return to the place where the walk began. This problem interested many townspeople, but no one could solve it. This issue has aroused the interest of scientists from many countries. The solution to the problem was obtained by mathematician Leonhard Euler. In addition, he formulated a general approach to solving such problems. To do this, he turned the map into a graph. The vertices of this graph were the land, and the edges were the bridges connecting it.

While solving the Königsberg bridge problem, Euler managed to formulate the properties of graphs.

It is possible to draw a graph by starting from one vertex and ending at the same vertex with one stroke (without drawing along the same line twice and without lifting the pencil from the paper) if all the vertices of the graph are even.

If there is a graph with two odd vertices, then its vertices can also be connected with one stroke. To do this, you need to start from one and finish on the other, any odd vertex.

If there is a graph with more than two odd vertices, then the graph cannot be drawn with one stroke.

If we apply these properties to the problem of bridges, we can see that all the vertices of the graph under study are odd, which means that this graph cannot be connected with one stroke, i.e. It is impossible to cross all the bridges once and end the journey in the place where it began.

If a graph has a cycle (not necessarily simple) containing all the edges of the graph once, then such a cycle is called Euler cycle . Euler chain (path, cycle, contour) is a chain (path, cycle, contour) containing all the edges (arcs) of the graph once.

CHAPTER II. DESCRIPTION OF THE STUDY AND ITS RESULTS

2.1. Stages of the study

To test the hypothesis, the study included three stages (Table 1):

Research stages

Table 1.

		Methods used
Theoretical study of the problem	Study and analyze educational and scientific literature.	- independent thinking;  study of information sources; - search for necessary literature.
Case study Problems	Review and analyze areas practical application graphs;	- observation; - analysis; - comparison; - survey.
Stage 3. Practical use of the results	Summarize the information studied;	- systematization;  report (oral, written, with demonstration of materials)	September 2017

2.2. Areas of practical application of graphs

Graphs and information

Information theory makes extensive use of the properties of binary trees.

For example, if you need to encode a certain number of messages in the form of certain sequences of zeros and ones of various lengths. A code is considered best for a given probability of codewords if the average word length is the smallest in comparison with other probability distributions. To solve this problem, Huffman proposed an algorithm in which the code is represented as a tree-graph within the framework of search theory. For each vertex, a question is proposed, the answer to which can be either “yes” or “no” - which corresponds to the two edges coming out of the vertex. The construction of such a tree is completed after establishing what was required. This can be used in interviewing several people, when the answer to the previous question is unknown in advance, the interview plan is represented as a binary tree.

Graphs and chemistry

A. Cayley also considered the problem of possible structures of saturated (or saturated) hydrocarbons, the molecules of which are given by the formula:

CnH 2n+2

All hydrocarbon atoms are 4-valent, all hydrogen atoms are 1-valent. Structural formulas The simplest hydrocarbons are shown in the figure.

Each saturated hydrocarbon molecule can be represented as a tree. When all the hydrogen atoms are removed, the hydrocarbon atoms that remain form a tree with vertices whose degree is no higher than four. This means that the number of possible desired structures (homologues of a given substance) is equal to the number of trees whose vertex degrees are no more than 4. This problem reduces to the problem of enumerating trees of a particular type. D. Polya considered this problem and its generalizations.

Graphs and biology

The process of bacterial reproduction is one of the types of branching processes found in biological theory. Let each bacterium, after a certain time, either die or divide into two. Therefore, for one bacterium we get a binary tree of the reproduction of its offspring. The question of the problem is the following: how many cases does it contain? k descendants in nth generation one bacterium? This relationship in biology is called the Galton-Watson process, which denotes the required number of required cases.

Graphs and Physics

A difficult and tedious task for any radio amateur is creating printed circuits (a plate of dielectric - insulating material and etched tracks in the form of metal strips). The intersection of tracks occurs only at certain points (locations of triodes, resistors, diodes, etc.) according to certain rules. As a result, the scientist is faced with the task of drawing a flat graph with vertices in

So, all of the above confirms the practical value of graphs.

Internet mathematics

The Internet is a worldwide system of interconnected computer networks for storing and transmitting information.

The Internet can be represented as a graph, where the vertices of the graph are Internet sites, and the edges are links (hyperlinks) going from one site to another.

The web graph (Internet), which has billions of vertices and edges, is constantly changing - sites are spontaneously added and disappeared, links disappear and are added. However, the Internet has a mathematical structure, obeys graph theory, and has several “stable” properties.

The web graph is sparse. It contains only a few times more edges than vertices.

Despite its sparseness, the Internet is very crowded. You can go from one site to another using links in 5 - 6 clicks (the famous theory of “six handshakes”).

As we know, the degree of a graph is the number of edges to which a vertex belongs. The degrees of the vertices of a web graph are distributed according to a certain law: the proportion of sites (vertices) with a large number of links (edges) is small, and the share of sites with a small number of links is large. Mathematically it can be written like this:

where is the proportion of vertices of a certain degree, is the degree of a vertex, is a constant independent of the number of vertices in the web graph, i.e. does not change during the process of adding or removing sites (vertices).

This power law is universal for complex networks - from biological to interbank.

The Internet as a whole is resistant to random attacks on sites.

Since the destruction and creation of sites occurs independently and with the same probability, the web graph, with a probability close to 1, maintains its integrity and is not destroyed.

To study the Internet, it is necessary to build a random graph model. This model should have the properties of the real Internet and should not be too complex.

This problem has not yet been completely solved! Solving this problem - building a high-quality model of the Internet - will allow us to develop new tools to improve information search, identify spam, and disseminate information.

The construction of biological and economic models began much earlier than the task of constructing a mathematical model of the Internet arose. However, advances in the development and study of the Internet have made it possible to answer many questions regarding all these models.

Internet mathematics is in demand by many specialists: biologists (predicting the growth of bacterial populations), financiers (risks of crises), etc. The study of such systems is one of the central branches of applied mathematics and computer science.

Murmansk using the graph.

When a person arrives in a new city, as a rule, the first desire is to visit the main attractions. But at the same time, the amount of time is often limited, and in the case of a business trip, very small. Therefore, it is necessary to plan your sightseeing in advance. And graphs will be a great help in building your route!

As an example, consider a typical case of arriving in Murmansk from the airport for the first time. We plan to visit the following attractions:

1. Marine Orthodox Church of the Savior on Water;

2. St. Nicholas Cathedral;

3. Oceanarium;

4. Monument to the cat Semyon;

5. Nuclear icebreaker Lenin;

6. Park Lights of Murmansk;

7. Park Valley of Comfort;

8. Kola Bridge;

9. Museum of the History of the Murmansk Shipping Company;

10. Five Corners Square;

11. Sea trade port

First, let's locate these places on the map and get a visual representation of the location and distance between the attractions. The road network is quite developed, and traveling by car will not be difficult.

Attractions on the map (on the left) and the resulting graph (on the right) are shown in the corresponding figure in APPENDIX No. 1. Thus, the newcomer will first pass near the Kola Bridge (and, if desired, can cross it back and forth); then he will relax in the Lights of Murmansk Park and the Valley of Comfort and move on. As a result, the optimal route will be:

Using the graph, you can also visualize the scheme for conducting opinion polls. Examples are presented in APPENDIX No. 2. Depending on the answers given, the respondent is asked different questions. For example, if in sociological survey No. 1 the respondent considers mathematics the most important of the sciences, he will be asked whether he feels confident in physics lessons; if he thinks otherwise, the second question will concern demand humanities. The vertices of such a graph are questions, and the edges are answer options.

2.3. Application of graph theory to problem solving

Graph theory is used to solve problems from many subject areas: mathematics, biology, computer science. We studied the principle of solving problems using graph theory and created our own problems on the topic of research.

Task No. 1.

Five classmates shook hands at a high school reunion. How many handshakes were done?

Solution: Let's denote classmates by the vertices of the graph. Let's connect each vertex with lines to four other vertices. We get 10 lines, these are handshakes.

Answer: 10 handshakes (each line means one handshake).

Task No. 2.

In my grandmother’s village, near her house, 8 trees grow: poplar, oak, maple, apple tree, larch, birch, rowan and pine. Rowan is higher than larch, apple tree is higher than maple, oak is lower than birch, but higher than pine, pine is higher than rowan, birch is lower than poplar, and larch is higher than apple tree. In what order will the trees be arranged in height from tallest to shortest?

Solution:

Trees are the vertices of the graph. Let's denote them by the first letter in the circle. Let's draw arrows from a low tree to a higher one. It is said that the rowan is higher than the larch, then we put the arrow from the larch to the rowan, the birch is lower than the poplar, then we put the arrow from the poplar to the birch, etc. We get a graph where we can see that the shortest tree is maple, then apple, larch, rowan, pine, oak, birch and poplar.

Answer: maple, apple, larch, rowan, pine, oak, birch and poplar.

Task No. 3.

Mom has 2 envelopes: regular and air, and 3 stamps: square, rectangular and triangular. In how many ways can Mom choose an envelope and stamp to send a letter to Dad?

Answer: 6 ways

Task No. 4.

Between settlements A, B, C, D, E roads are built. Need to determine the length shortest path between points A and E. You can only travel on roads whose length is indicated in the figure.

Task No. 5.

Three classmates - Maxim, Kirill and Vova decided to go in for sports and passed the selection of sports sections. It is known that 1 boy applied for the basketball section, and three wanted to play hockey. Maxim only auditioned for section 1, Kirill was selected for all three sections, and Vova was selected for section 2. Which of the boys was selected for which sports section?

Solution: To solve the problem we will use graphs

Basketball Maxim

Football Kirill

Hockey Vova

Since to basketball only one arrow goes, then Kirill was selected to the section basketball. Then Kirill will not play hockey, which means in hockey section was selected by Maxim, who auditioned only for this section, then Vova will be football player.

Task No. 6.

Due to the illness of some teachers, the head teacher of the school needs to draw up a fragment of the school schedule for at least one day, taking into account the following circumstances:

1. The life safety teacher agrees to give only the last lesson;

2. The geography teacher can give either the second or third lesson;

3. The mathematician is ready to give either only the first or only the second lesson;

4. A physics teacher can give either the first, second, or third lessons, but only in one class.

What kind of schedule can the head teacher of a school create so that it satisfies all teachers?

Solution: This problem can be solved by going through all possible options, but it’s easier if you draw a graph.

1. 1) physics 2. 1) mathematics 3. 1) mathematics

2) mathematics 2) physics 2) geography

3) geography 3) geography 3) physics

4) OBZH 4) OBZH 4) OBZH

Conclusion

In this research work, graph theory was studied in detail, the hypothesis was proven that the study of graphs can help in solving logical problems, in addition, graph theory in different fields of science was considered and 7 problems were compiled.

The use of graphs when teaching students how to find solutions to problems allows students to improve their graphic skills and communicate reasoning in a special language of a finite set of points, some of which are connected by lines. All this contributes to the work of teaching students to think.

Efficiency educational activities in the development of thinking largely depends on the degree of creative activity of students when solving mathematical problems. Therefore, there is a need for mathematical tasks and exercises that would activate the mental activity of schoolchildren.

The application of tasks and the use of elements of graph theory in elective classes at school precisely pursues the goal of activating the mental activity of students. We believe that practical material on our research can be useful in elective mathematics classes.

Thus, the goal of the research work has been achieved, the problems have been solved. In the future, we plan to continue studying graph theory and develop our own routes, for example, using a graph to create an excursion route for a school bus in ZATO Aleksandrovsk to museums and memorable places Murmansk.

LIST OF REFERENCES USED

Berezina L. Yu. “Graphs and their application” - M.: “Enlightenment”, 1979

Gardner M. “Mathematical leisure”, M. “Mir”, 1972

Gardner M. " Math puzzles and entertainment", M. "Mir", 1971

Gorbachev A. “Collection of Olympiad problems” - M. MTsNMO, 2005

Zykov A. A. Fundamentals of graph theory. - M.: “University Book”, 2004. - P. 664

Kasatkin V. N. “Unusual problems of mathematics”, Kyiv, “Radianska School”, 1987

Mathematical component / Editors and compilers N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M.: Foundation "Mathematical Etudes" 2015 - 151 p.

Melnikov O. I. “Entertaining problems in graph theory”, Mn. "TetraSystems", 2001

Melnikov O.I. Dunno in the land of counts: A manual for students. Ed. 3rd, stereotypical. M.: KomKniga, 2007. - 160 p.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Old entertaining problems”, M. “Science”, 1988

Ore O. “Graphs and their applications”, M. “Mir”, 1965

Harari F. Graph Theory / Translation from English. and preface V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2nd. - M.: Editorial URSS, 2003. - 296 p.

APPENDIX No. 1

Drawing up the optimal route for visiting the main attractions

Murmansk using the graph.

The optimal route will be:

8. Kola Bridge6. Park Lights of Murmansk7. Park Valley of Comfort2. St. Nicholas Cathedral10. Five Corners Square5. Nuclear icebreaker Lenin9. Museum of the History of the Murmansk Shipping Company11. Sea trade port1. Marine Orthodox Church of the Savior on Water4. Monument to the cat Semyon3. Oceanarium.

GUIDE TO MURMANSK ATTRACTIONS

APPENDIX No. 2

Sociological surveys No. 1, 2

What is the graph method?

The word "graph" in mathematics means a picture with several points drawn, some of which are connected by lines. First of all, it is worth saying that the counts that will be discussed have nothing to do with the aristocrats of bygone times. Our “graphs” are rooted in the Greek word “grapho,” which means “I write.” The same root is in the words “graph”, “biography”.

In mathematics graph definition is given as follows: a graph is a finite set of points, some of which are connected by lines. The points are called vertices of the graph, and the connecting lines are called edges.

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)

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

Note that if a complete graph has n vertices, then the number of edges will be equal to

n(n-1)/2

Indeed, the number of edges in a complete graph with n vertices is defined as the number of unordered pairs made up of all n edge points of the graph, i.e., as the number of combinations of n elements of 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.

Degrees of vertices and counting the number of edges.

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

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

Fig.5

Figure 5 shows a graph with five vertices. The degree of vertex A will be denoted by St.A.

In the figure: 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.

Proof:

This pattern is obvious after considering any complete graph. Each vertex is connected by an edge to every vertex except itself, i.e., from each vertex of a graph that has n vertices, n-1 edges emanate, which is what needed to be proved.

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. Proof:

Indeed, each edge of the graph connects two vertices. This means that if we add the number of degrees of all vertices of the graph, we will get twice the number of edges 2R (R is the number of edges of the graph), since each edge was counted twice, which is what needed to be proved

The number of odd vertices in any graph is even. Proof:

Consider an arbitrary graph G. Let the number of vertices in this graph whose degree is 1 be equal to K1; the number of vertices whose degree is 2 is equal to K2; ...; the number of vertices whose degree is n is equal to Kn. Then the sum of the degrees of the vertices of this graph can be written as
K1 + 2K2 + ZK3 + ...+ nKn.
On the other hand: if the number of edges of the graph is R, then from Law 2 it is known that the sum of the degrees of all vertices of the graph is equal to 2R. Then we can write the equality
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
Let us select on the left side of the equality a sum equal to the number of odd vertices of the graph (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
The second bracket is an even number as the sum of even numbers. The resulting sum (2R) is an even number. Hence (K1 + K3 + K5 +...) is an even number.

Let us now consider problems solved using graphs:

Task. Class Championship . There are 6 participants in the table tennis class championship: Andrey, Boris, Victor, Galina, Dmitry and Elena. The championship is held on a round-robin basis - each participant plays each of the others once. To date, some games have already been played: Andrey played with Boris, Galina and Elena; Boris, as already mentioned, is with Andrei and also with Galina; Victor - with Galina, Dmitry and Elena; Galina with Andrey and Boris; Dmitry - with Victor and Elena - with Andrey and Victor. How many games have been played so far and how many are left?

Discussion. Let's depict these tasks in the form of a diagram. We will depict the participants as dots: Andrey - point A, Boris - point B, etc. If two participants have already played with each other, then we will connect the points representing them with segments. The result is the diagram shown in Figure 1.

Points A, B, C, D, D, E are the vertices of the graph, and the segments connecting them are the edges of the graph.

Note that the intersection points of the edges of the graph are not its vertices.

The number of games played so far is equal to the number of edges, i.e. 7.

To avoid confusion, the vertices of a graph are often depicted not as dots, but as small circles.

To find the number of games that need to be played, we will build another graph with the same vertices, but with edges we will connect those participants who have not yet played with each other (Fig. 2). This graph turned out to have 8 edges, which means there are 8 games left to play : Andrey - with Victor and Dmitry; Boris - With Victor, Dmitry and Elena, etc.

Let's try to build a graph for the situation described in the following problem:

Task . Who plays Lyapkin - Tyapkin? The school drama club decided to stage Gogol's The Inspector General. And then a heated argument broke out. It all started with Lyapkin - Tyapkin.

Lyapkin - I will be Tyapkin! – Gena stated decisively.

No, I will be Lyapkin - Tyapkin, Dima objected. - From early childhood I dreamed of bringing this image to life on stage.

Well, okay, I’ll give up this role if they let me play Khlestakov,” Gena showed generosity.

“...And for me - Osipa,” Dima did not yield to him in generosity.

“I want to be Strawberry or Mayor,” said Vova.

No, I will be the Mayor,” Alik and Borya shouted in unison. - Or Khlestakov, -

Will it be possible to distribute the roles so that the performers are satisfied?

Discussion. Let's depict the young actors with circles in the top row: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima, and the roles they are going to play - with circles in the second row (1 - Lyapkin - Tyapkin, 2 - Khlestakov, 3 – Osip, 4 – Strawberry, 5 – Mayor). Then we will draw segments from each participant, i.e. ribs, to the roles he would like to play. We will get a graph with ten vertices and ten edges (Fig. 3)

To solve the problem, you need to select five edges out of ten that do not have common vertices. It's easy to do. It is enough to note that one edge leads to vertices 3 and 4, from vertices D and B, respectively. This means that Osip (vertex 3) should be played by Dima (who else?), and Zemlyanichka by Vova. Vertex 1 - Lyapkin - Tyapkin - is connected by edges to G and D. Edge 1 - D gives up, since Dima is already busy, 1 - G remains, Lyapkina - Tyapkina should be played by Gena. It remains to connect vertices A and B with vertices 2 and 5, corresponding to the roles of Khlestakov and Gorodnichy. This can be done in two ways: either select edge A -5 and B - 2, or edge A -2 and B -5. In the first case, Alik will play Gorodnichy, and Borya will play Khlestakov, in the second case, vice versa. As the graph shows, the problem has no other solutions.

The same graph will be obtained when solving the following problem:

Task. Grumpy neighbors. The inhabitants of five houses quarreled with each other and, in order not to meet at the wells, decided to divide them (the wells) so that the owner of each house would go to “his” well along “his” path. Will they be able to do this?

The question arises:were graphs really needed in the problems discussed? Isn't it possible to arrive at a solution through purely logical means? Yes, you can. But the graphs made the conditions clearer, simplified the solution and revealed the similarity of the problems, turning two problems into one, and this is not so little. Now imagine problems whose graphs have 100 or more vertices. But it is precisely such problems that modern engineers and economists have to solve. You can't do without graphs here.

III. Euler graphs.

Graph theory is a relatively young science: in Newton’s time such a science did not yet exist, although “family trees”, which are varieties of graphs, were in use. The first work on graph theory belongs to Leonhard Euler, and it appeared in 1736 in the publications of the St. Petersburg Academy of Sciences. This work began with consideration of the following problem:

A) Problem about the Königsberg bridges. The city of Koenigsberg (now Kaliningrad) is located on the banks and two islands of the Pregel River (Pregoli). The various parts of the city were connected by seven bridges, as shown in the figure. On Sundays, citizens take walks around the city. Is it possible to choose a route such that you cross each bridge once and only once and then return to the starting point?
Before considering the solution to this problem, we introduce the concept “ Euler graphs.

Let's try to circle the graph shown in Fig. 4 with one stroke, that is, without lifting the pencil from the sheet of paper and without passing along the same part of the line more than once.

This figure, so simple in appearance, turns out to have an interesting feature. If we start moving from vertex B, then we will definitely succeed. What will happen if we start moving from vertex A? It is easy to see that in this case we will not be able to trace the line: we will always have untraversed edges, which are no longer possible to reach.

In Fig. Figure 5 shows a graph that you probably know how to draw with one stroke. This is a star. It turns out that, although it looks much more complex than the previous graph, you can trace it by starting from any vertex.

The graphs drawn in Fig. 6 can also be drawn with one stroke of the pen.

Now try to draw with one stroke graph shown in Fig. 7

You failed to do this! Why? Can't find the vertex you're looking for? No! That's not the point. This graph generally cannot be drawn with one stroke of the pen.

Let us carry out reasoning that will convince us of this. Consider node A. Three vertices emerge from it. Let's start drawing the graph from this vertex. To go along each of these edges, we must exit vertex A along one of them, at some point we must return to it along the second and exit along the third. But we won’t be able to enter again! This means that if we start drawing from vertex A, we will not be able to finish there.

Let us now assume that vertex A is not the beginning. Then, in the process of drawing, we must enter it along one of the edges, exit along the other and return again along the third. And since we cannot get out of it, then peak A in this case must be the end.

So, vertex A must be either the beginning or the end node of the drawing.

But the same can be said about the other three vertices of our graph. But the starting vertex of drawing can only be one vertex, and the final vertex can also be only one vertex! This means that it is impossible to draw this graph with one stroke.

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 1. (follows from the theorem we considered).

It is impossible to draw a graph with an odd number of odd vertices.
Pattern 2.

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 3.

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 4.

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.

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

Fig.7 Fig.8

Figure 7 obviously shows a disconnected graph. If, for example, in the figure you draw an edge between vertices D and E, 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 in Figure 7 could be the edges DE, A3, VZH, etc., 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 connectivity components graph. Each connected component is, of course, a connected graph. Note that a connected graph has one connected component.
THEOREM.

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

Proof:

Drawing the graph for each vertex, with the exception of the initial and final ones, we will enter the same number of times as we exit it. Therefore, the degrees of all vertices must be even, except for two, which means that an Eulerian graph has at most two odd vertices.

Let us now return to the problem of the Königsberg bridges.

Discussion of the problem . Let's denote the different parts of the city with the letters A, B, C, D, and the bridges with the letters a, b, c, d, e, f, g - bridges connecting the corresponding parts of the city. In this problem, there are only crossings over bridges: crossing any bridge, we always end up from one part of the city to another. And, conversely, crossing from one part of the city to another, we will certainly cross a bridge. Therefore, let us depict the city plan in the form of a graph, the vertices of which A, B, C, D (Fig. 8) depict individual parts of the city, and the edges a, b, c, d, e, f, g are bridges connecting the corresponding parts of the city . It is often more convenient to depict edges not as straight segments, but as curvilinear ones - “arcs”.

If there were a route that satisfied the conditions of the problem, then there would be a closed continuous traversal of this graph, passing once along each edge. In other words, this graph should be drawn with one stroke. But this is impossible - no matter which vertex we choose as the initial one, we will have to go through the remaining vertices, and at the same time, each “incoming” edge (the bridge along which we entered this part of the city) will correspond to an “outgoing” edge, the bridge by which we and then use it to leave this part of the city): the number of edges entering each vertex will be equal to the number of edges leaving it, i.e. total number edges converging at each vertex must be even. Our graph does not satisfy this condition, and therefore the required route does not exist.