Wide application of graph theory in computer science. The use of graphs in various areas of people's lives

MUNICIPAL AUTONOMOUS GENERAL EDUCATIONAL INSTITUTION SECONDARY EDUCATIONAL SCHOOL № 2

Prepared

Legkokonets Vladislav, 10A student

Practical application of Graph Theory

Supervisor

L.I. Noskova, mathematics teacher

st.Bryukhovetskaya

2011

1.Introduction………………………………………………………………………….………….3

2. The history of the emergence of graph theory………………………………………….………..4

3.Basic definitions and theorems of graph theory……………………………….………6

4. Tasks solved with the help of graphs……………………………..……………………..8

4.1 Famous tasks………………………………….………………………...8

4.2 Some interesting tasks………………………………….……………..9

5. Application of graphs in various areas of people's lives……………………………...11

6. Problem solving……………………………………………………………………………...12

7. Conclusion………………….…………………………………………………………….13

8. List of references………….…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………….

9.Appendix……………………………………………………………………….…………15

Introduction

Born in solving puzzles and entertaining games, graph theory has now become a simple, accessible and powerful tool for solving problems related to a wide range of problems. Graphs are literally ubiquitous. In the form of graphs, you can, for example, interpret road maps and electrical circuits, geographic 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 area. It is used in the design of integrated circuits and control circuits, in the study of automata, logical circuits, program flowcharts, in economics and statistics, chemistry and biology, in scheduling theory. That's why relevance The topic is due, on the one hand, to the popularity of graphs and related research methods, and on the other hand, an undeveloped, integral system for its implementation.

The solution of many life problems requires long calculations, and sometimes these calculations do not bring success. This is what it consists research problem. The question arises: is it possible to find a simple, rational, short and elegant solution for their solution. Is it easier to solve problems if you use graphs? It determined topic of my research: "Practical Application of Graph Theory"

aim research was with the help of graphs to learn how to quickly solve practical problems.

Research hypothesis. The graph method is very important and widely used in various fields of science and human life.

Research objectives:

1. To study the literature and Internet resources on this issue.

2. Check the effectiveness of the graph method in solving practical problems.

3. Make a conclusion.

Practical significance research is that the results will undoubtedly arouse the interest of many people. Haven't any of you tried to build a family tree of your family? And how to do it correctly? The head of a transport company probably has to solve the problem of more profitable use of transport when transporting goods from a destination to several settlements. Each student faced logical transfusion tasks. It turns out they are solved with the help of graphs easily.

The following methods are used in the work: observation, search, selection, analysis.

The history of the emergence of graph theory

The mathematician Leonhard Euler (1707-1783) is considered to be the founder of graph theory. The history of the emergence 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.

“Once I was given a problem about an island located in the city of Koenigsberg and surrounded by a river, across which seven bridges are thrown.

[Appendix Fig.1] The question is whether anyone can go around them continuously, passing only once through each bridge. And then I was informed that no one had yet been able to do this, but no one had proved that it was impossible. This question, although banal, seemed to me, however, noteworthy the fact that neither geometry, nor algebra, nor combinatorial art is sufficient for its solution. After much thought, I found an easy rule, based on a completely convincing proof, with the help of which in all problems of this kind one can immediately determine whether such a round can be made through any number and arbitrarily located bridges or cannot. The Konigsberg bridges are located so that they can be represented in the following figure [Appendix Fig.2], where A denotes an island, and B , C and D are parts of the continent separated from each other by river branches

Regarding the method he discovered for solving problems of this kind, Euler wrote:

"This solution, by its nature, seems to have little to do with mathematics, and it is not clear to me why this solution should be expected from a mathematician rather than from any other person, for this solution is supported by reason 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 resolved by mathematicians than by others. "

So is it possible to get around the Königsberg bridges by passing only once through 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 get around 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 sections are separated by water - such , which have no other transition from one to another, except through the 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 to the rest, i.e. The number of bridges leading to individual sections is odd, and this one is already enough to solve the problem.When this is determined, we apply the following rule : if the number of bridges leading to each individual section were even, then the bypass, about which 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 odd, for only one cannot be odd, then even then the transition could take place, as prescribed, but only the beginning of the bypass must necessarily be taken from one of those two sections to which the odd number leads. bridges. If, finally, there were more than two sections to which an odd number of bridges leads, then such a movement is generally impossible ... if other, more serious problems could be cited here, this method could be even more useful and should not be neglected " .

Basic definitions and theorems of graph theory

Graph theory is a mathematical discipline created by the efforts of mathematicians, so its presentation includes the necessary rigorous definitions. So, let's proceed to the organized introduction of the basic concepts of this theory.

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

This definition can be formulated differently: a graph is a non-empty set of points (vertices) and segments (edges), both ends of which belong to a given set of points

In the future, we will denote the vertices of the graph in Latin letters A, B, C, D. Sometimes the graph as a whole will be denoted by one capital letter.

Definition 2. The vertices of the graph that do not belong to any edge are called isolated.

Definition 3. A graph consisting only of isolated vertices is called zero - count .

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

Definition 4. A graph in which each pair of vertices is connected by an edge is called complete.

Designation: U" – a graph consisting of n 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

Definition 5. The degree of a vertex is the number of edges that the vertex belongs to.

Definition 6. A graph whose degrees of all k vertices are the same is called a homogeneous graph of degree k .

Definition 7. The complement of a given graph is a graph consisting of all the edges and their ends that must be added to the original graph in order to obtain a complete graph.

Definition 8. A graph that can be represented in a plane in such a way that its edges intersect only at the vertices is called planar.

Definition 9. A polygon of a planar graph that does not contain any vertices or edges of the graph inside is called its face.

The concepts of a plane graph and graph faces are used in solving problems for the "correct" coloring of various maps.

Definition 10. A path from A to X is a sequence of edges leading from A to X such that every two adjacent edges have a common vertex and no edge occurs more than once.

Definition 11. A cycle is a path where the start and end points are the same.

Definition 12. A simple cycle is a cycle that does not pass through any of the vertices of the graph more than once.

Definition 13. long way , laid on a loop , is the number of edges of this path.

Definition 14. Two vertices A and B in a graph are called connected (disconnected) if there exists (does not exist) a path leading from A to B in it.

Definition 15. A graph is called connected if every two of its vertices are connected; if the graph contains at least one pair of disconnected vertices, then the graph is called disconnected.

Definition 16. A tree is a connected graph that does not contain cycles.

A three-dimensional model of a graph-tree is, for example, a real tree with its intricately branched crown; the river and its tributaries also form a tree, but already flat - on the surface of the earth.

Definition 17. A disconnected graph consisting solely of trees is called a forest.

Definition 18. A tree, all n vertices of which are numbered from 1 to n, is called a tree with renumbered vertices.

So, we have considered the main definitions of graph theory, without which it would be impossible to prove theorems, and, consequently, to solve problems.

Problems solved using graphs

Famous Challenges

The traveling salesman problem

The traveling salesman problem is one of the famous problems in the theory of combinatorics. It was put up in 1934, and the best mathematicians broke their teeth about it.

The problem statement is the following.
The traveling salesman (traveling merchant) must leave the first city, visit cities 2,1,3..n once in an unknown order, and return to the first city. Distances between cities are known. In what order should the cities be traversed so that the closed path (tour) of the traveling salesman is the shortest?

Method for solving the traveling salesman problem

Greedy Algorithm “go to the nearest (which you have not yet entered) city.”
This algorithm is called “greedy” because in the last steps you have to pay dearly for greed.
Consider for example the network in Figure [app fig.3] representing a narrow rhombus. Let the salesman start from city 1. The “go to the nearest city” algorithm will take him to city 2, then 3, then 4; on the last step, you will have to pay for greed, returning along the long diagonal of the rhombus. The result is not the shortest, but the longest tour.

The problem of the Königsberg bridges.

The task is formulated as follows.
The city of Konigsberg is located on the banks of the Pregel River and two islands. Different parts of the city were connected by seven bridges. On Sundays, the townspeople took walks around the city. Question: is it possible to take a walk in such a way that, having left the house, come back, passing exactly once over each bridge.
Bridges over the Pregel river are located as in the picture[Appendix Fig.1].

Consider a graph corresponding to the bridge scheme [appendix fig.2].

To answer the question of the problem, it is enough to find out whether the graph is Euler. (At least one vertex must have an even number of bridges). It is impossible, walking around the city, to go through all the bridges once and come back.

Several interesting challenges

1. "Routes".

Task 1

As you remember, the hunter dead souls Chichikov visited famous landowners once each. He visited them in the following order: Manilov, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Colonel Koshkarev. A diagram was found on which Chichikov sketched mutual arrangement estates and country roads connecting them. Determine which estate belongs to whom, if Chichikov did not pass any of the roads more than once [appendix fig.4].

Solution:

According to the road map, it can be seen that Chichikov began his journey with the E estate, and ended with the O estate. We notice that only two roads lead to the estates B and C, so Chichikov had to drive along these roads. Let's mark them with bold lines. The sections of the route passing through A are determined: AC and AB. Chichikov did not travel on the roads AE, AK and AM. Let's cross them out. Let's mark with a thick line ED ; cross out DK . Cross out MO and MN; mark with a bold line MF ; cross out FO ; we mark FH , NK and KO with a bold line. Let us find the only possible route under the given condition. And we get: the estate E - belongs to Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [app fig.5].

Task 2

The figure shows a map of the area [appendix fig.6].

You can only move in the direction of the arrows. Each point can be visited no more than once. In how many ways can you get from point 1 to point 9? Which route is the shortest and which is the longest.

Solution:

Sequentially "stratify" the scheme into a tree, starting from vertex 1 [app fig.7]. Let's get a tree. Number possible ways hits from 1 to 9 is equal to the number of "hanging" vertices of the tree (there are 14 of them). Obviously the shortest path is 1-5-9; the longest is 1-2-3-6-5-7-8-9.

2 "Groups, dating"

Task 1

Participants of the music festival, having met, exchanged envelopes with addresses. Prove that:

a) an even number of envelopes were sent in total;

b) the number of participants who exchanged envelopes an odd number of times is even.

Solution: Let the festival participants be A 1 , A 2 , A 3 . . . , And n are the vertices of the graph, and the edges connect pairs of vertices representing guys who exchanged envelopes [Appendix Fig.8]

Solution:

a) the degree of each vertex A i shows the number of envelopes that participant A i gave to his friends. Total number transferred envelopes N is equal to the sum of the degrees of all vertices of the graph N = step. A 1 + step. A 2 + + . . . + step. And n -1 + step. And n , N =2p , where p is the number of graph edges, i.e. N is even. Therefore, an even number of envelopes were sent;

b) in the equality N = step. A 1 + step. A 2 + + . . . + step. And n -1 + step. And n the sum of odd terms must be even, and this can only be if the number of odd terms is even. And this means that the number of participants who exchanged envelopes an odd number of times is even.

Task 2

Once Andrei, Boris, Volodya, Dasha and Galya agreed to go to the cinema in the evening. They decided to agree on the choice of the cinema and the session by phone. It was also decided that if it was not possible to phone someone, then the trip to the cinema would be cancelled. In the evening, not everyone gathered at the cinema, and therefore the visit to the cinema fell through. The next day, they began to find out who called whom. It turned out that Andrey called Boris and Volodya, Volodya called Boris and Dasha, Boris called Andrey and Dasha, Dasha called Andrey and Volodya, and Galya called Andrey, Volodya and Boris. Who was unable to phone and therefore did not come to the meeting?

Solution:

Let's draw five points and designate them with the letters A, B, C, D, E. These are the first letters of the names. Let's connect those dots that correspond to the names of the guys who called each other.

[app fig.9]

It can be seen from the picture that each of the guys - Andrey, Boris and Volodya - phoned everyone else. That's why these guys came to the cinema. But Galya and Dasha failed to call each other (points D and D are not connected by a segment) and therefore, in accordance with the agreement, they did not come to the cinema.

The use of graphs in various areas of people's lives

In addition to the examples given, graphs are widely used in construction, electrical engineering, management, logistics, geography, mechanical engineering, sociology, programming, automation of technological processes and industries, psychology, and advertising. So, from all of the above, the practical value of graph theory irrefutably follows, the proof of which was the goal of this study.

In any field of science and technology, you meet with graphs. Graphs are wonderful mathematical objects with which you can solve mathematical, economic and logical problems, various puzzles and simplify the conditions of problems in physics, chemistry, electronics, automation. It is convenient to formulate many mathematical facts in the language of graphs. Graph theory is part of many sciences. Graph theory is one of the most beautiful and visual mathematical theories. Recently, graph theory has found more and more applications in applied issues. Even computer chemistry has emerged - a relatively young field of chemistry based on the application of graph theory.

Molecular graphs, used in stereochemistry and structural topology, chemistry of clusters, polymers, etc., are undirected graphs that display the structure of molecules [app fig.10]. The vertices and edges of these graphs correspond to the corresponding atoms and the chemical bonds between them.

Molecular graphs and trees: [app fig.10] a, b - multigraphs resp. ethylene and formaldehyde; in-mol. isomers of pentane (trees 4, 5 are isomorphic to tree 2).

In the stereochemistry of organisms, the most often use molecular trees - the main trees of molecular graphs, which contain only all the vertices corresponding to C atoms. trees and the establishment of their isomorphism allow you to determine the pier. structures and find total number isomers of alkanes, alkenes and alkynes

Protein networks

Protein networks - groups of physically interacting proteins that function in a cell jointly and in a coordinated manner, controlling the interconnected processes occurring in the body [app fig. eleven].

Hierarchical system graph called a tree. Distinctive feature of a tree is that there is only one path between any two of its vertices. The tree does not contain cycles and loops.

Usually a tree representing hierarchical system, one main vertex is allocated, which is called the root of the tree. Each vertex of the tree (except the root) has only one ancestor - the object designated by it belongs to one top-level class. Any vertex of the tree can generate several descendants - vertices corresponding to lower-level classes.

For each pair of tree vertices, there is a unique path connecting them. This property is used when finding all ancestors, for example, in the male line, of any person whose family tree is presented in the form of a family tree, which is a “tree” in the sense of graph theory as well.

An example of my family tree [appendix fig.12].

One more example. The figure shows the biblical family tree [appendix fig.13].

Problem solving

1. Transport task. Let there be a base with raw materials in the city of Krasnodar, which needs to be planted in the cities of Krymsk, Temryuk, Slavyansk-on-Kuban and Timashevsk in one run, while spending as little time and fuel as possible and returning back to Krasnodar.

Solution:

First, let's create a graph of all possible routes. [app fig.14], taking into account the real roads between these settlements and the distance between them. To solve this problem, we need to create another graph, a tree [app fig.15].

For the convenience of the solution, we denote the cities with numbers: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

This resulted in 24 solutions, but we only need shortest paths. Of all the solutions, only two are satisfied, these are 350 km.

Similarly, it is possible and, I think, it is necessary to calculate real transportation from one locality to another.

Logic task for transfusion. There are 8 liters of water in a bucket, and there are two pots with a capacity of 5 and 3 liters. it is required to pour 4 liters of water into a five-liter saucepan and leave 4 liters in a bucket, i.e. pour water equally into a bucket and a large saucepan.

Solution:

The situation at any moment can be described by three numbers [appendix fig.16].

As a result, we get two solutions: one in 7 moves, the other in 8 moves.

Conclusion

So, in order to learn how to solve problems, you need to understand what they are, how they are arranged, from which constituent parts they consist of what tools are used to solve problems.

Solving practical problems with the help of graph theory, it became clear that at every step, at every stage of their solution, it is necessary to apply creativity.

From the very beginning, at the first stage, it lies in the fact that you need to be able to analyze and encode the condition of the problem. The second stage is a schematic notation, which consists in the geometric representation of graphs, and at this stage the element of creativity is very important because it is far from easy to find correspondences between the elements of the condition and the corresponding elements of the graph.

When solving a transport problem or a problem of compiling a family tree, I concluded that the graph method is certainly interesting, beautiful and visual.

I was convinced that graphs are widely used in economics, management, and technology. Graph theory is also used in programming. This was not discussed in this paper, but I think that this is only a matter of time.

In this scientific work, mathematical graphs, their areas of application are considered, several problems are solved with the help of graphs. Knowledge of the basics of graph theory is necessary in various areas related to production management, business (for example, construction network diagram, mail delivery schedules). In addition, while working on a scientific work, I mastered working on a computer in text WORD editor. Thus, tasks scientific work completed.

So, from all of the above, the practical value of graph theory irrefutably follows, the proof of which was the goal of this work.

Literature

Berge K. Graph theory and its applications. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Introduction to finite mathematics. -M.: IIL, 1963.

Ore O. Graphs and their application. -M.: Mir, 1965.

Harary F. Graph theory. -M.: Mir, 1973.

Zykov A.A. Theory of Finite Graphs. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Graphs and their application. -M.: Education, 1979. -144 p.

"Soros Educational Journal" No. 11 1996 (Article "Flat Graphs");

Gardner M. "Mathematical leisure", M. "Mir", 1972 (chapter 35);

Olekhnik S. N., Nesterenko Yu. V., Potapov M. K. "Old entertaining problems", M. "Nauka", 1988 (part 2, section 8; appendix 4);

Appendix

Rice. 6

Rice. 7

Rice. 8

application

Appendix

Rice. fourteen

application

Appendix

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

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

The main areas of application of graph theory:

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

In computer science and programming (algorithm graph diagram);

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

In economics;

in logistics;

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

There is a special kind of graph, wood.Wood is a connected acyclic graph. Connectivity 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 the Fig 1.3 presented binary tree.

binary tree is a tree-like data structure in which each node has at most two descendants(children). Usually the first one is called parent node and the children are named leftist And right heirs.

Matrix representation of graphs. Incident Matrix.

The development of algorithmic approaches to the analysis of the properties of graphs requires certain methods of describing graphs that are more suitable for practical calculations, including those using computers. Consider 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 the 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 given as follows:

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

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

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

Fig. 2.1 a Fig. 2.1 b

Adjacency matrix.

Despite the fact that the representation of a graph in the form of an incidence matrix plays a very important role in theoretical studies, in practice this method is very inefficient. First of all, there are only two non-zero elements in the matrix in each column, which makes this way of representing the graph uneconomical with a large number of vertices. In addition, solving practical problems using the incidence matrix is very laborious.

Let us estimate, for example, the time spent on 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 (+1 or -1) appears. If +1 is found, in the corresponding column you need to find the line in which the number -1 is written. The number of the line containing this number gives the number of the vertex directly reachable from the given vertex. If -1 is found, in the column you need to find the line in which 1 is written, and get the number of the vertex from which it is directly reachable given vertex. To get the entire "environment", you need to do the specified search for all non-zero elements of the k-th row. The most time-consuming procedure is to find a non-null 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 (of the order of).

It can be seen that finding the "environment" of all vertices will take time on the order of the product of the number of vertices of the directed graph times the sum of the degrees of all the vertices, which can be shown to be 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 B of order n, whose elements 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 represented on ( Fig 2.2 b).

The beginning of graph theory is unanimously attributed to 1736, when L. Euler solved the problem of Königsber 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 to study electrical circuits, and the mathematician A. Cayley, in connection with the description of the structure of hydrocarbons, solved enumerative problems for three types of trees.

Born while solving puzzles and entertaining games (problems about a chess horse, about queens, “ trip around the world”, problems about weddings and harems, etc.), graph theory has now become a simple, accessible and powerful tool for solving questions related to a wide range of problems. Graphs are literally ubiquitous. In the form of graphs, one can, for example, interpret road diagrams and electrical circuits, geographical maps and molecules of 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 area. It is used in the design of integrated circuits and control circuits, in the study of automata, logical circuits, program flowcharts, in economics and statistics, chemistry and biology, in scheduling theory. To a large extent, through the theory of graphs, the penetration of mathematical methods into science and technology is now taking place.

In this paper, we consider not the own problems of graph theory, but how it is used in school course geometry.

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 almost all modern mathematics at different levels, and on the other hand, an integral system for its implementation in the course of geometry has not been developed.

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

Object is the process of teaching geometry.

Subject – classroom and extracurricular activities

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

2) to develop PMK 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. The theory of graphs, which arose in 1736 (Leonhard Euler (1708-1783) was rapidly developed, remains relevant even now, because in Everyday life graphic illustrations, geometric representations and other techniques and methods of visualization are increasingly being used.

1. Graph theory finds application 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 the proofs of geometric theorems and in 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 provable statement. In order to reason logically competently, it is necessary to develop the skills of such thinking, which would help to build disparate geometric facts into logical relationships.

Forms play a special role in developing the skills of a culture of thinking. writing students. Written forms of work are the most important activity that forms stable skills in logical reasoning when proving theorems and solving problems. The form of writing the conditions of the problem, reasonable abbreviations and notation in calculations and proofs of problems disciplines thinking and promotes geometric vision. As you know, vision gives rise to thinking. The problem arises: how to establish logical connections between disparate geometric facts and how to arrange them in the form of a single whole. To see the progress of proving theorems and solving problems, the method of graph schemes allows, which makes the proof more visual and allows you to briefly and accurately state the proofs of theorems and solving problems.

For this, a tree graph is used.

The vertices of the "tree" (the condition of a theorem or problem and a sequence of logical connectives) are shown as rectangles with information placed in them, which are then connected by arrows. The end of the graph-scheme contains the assertion 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 distinguish the main stages of proving a theorem and solving a problem.

Research part.

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

“Once I was offered the problem of an island located in the city of Koenigsberg and surrounded by a river across which seven bridges are thrown. The question is whether anyone can continuously bypass them, passing only once through each bridge. so far he has not been able to do this, but no one has proved that it is impossible.This question, although banal, seemed to me, however, worthy of attention because neither geometry, nor algebra, nor combinatorial art is sufficient for its solution. After much deliberation, I found an easy rule, based on a completely convincing proof, with the help of which, in all problems of this kind, one can immediately determine whether such a circuit can be made through any number and arbitrarily located bridges or cannot. so that they can be represented in the following figure, in which A stands for an island, and B, C and D are parts of the continent, separated from each other by branches of the river. bridges are marked with letters a, b, c, d, e, f, g ".

Regarding the method he discovered for solving problems of this kind, Euler wrote

So is it possible to get around the Königsberg bridges by passing only once through 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 get around 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 sections are separated by water - such , which have no other transition from one to another, except through the 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 to the rest, i.e. The number of bridges leading to individual sections is odd, and this one is already enough to solve the problem.When this is determined, we apply the following rule : if the number of bridges leading to each individual 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. would be odd, for only one be odd cannot, then even then the transition could be made, 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 is generally impossible; if other, more serious problems could be cited here, this method could be even more useful and should not be neglected.

The rationale for the above rule can be found in a letter from L. Euler to his friend Eler 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 forking section of the river, to which an odd number of bridges leads. In order to make it easier to imagine this, we will erase the already passed bridges in the figure. It is 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 lead, and in the presence of areas with an odd number bridges we will be located in one of them. Continuing to move so on, we will pass through all the bridges once.

The history of the bridges of the city of Koenigsberg has a modern continuation.

Problem There are seven islands on the lake, which are interconnected as shown in Figure 2. Which island should the boat take travelers to so that they can pass through each bridge and only once? Why can't travelers be taken to island A?

Solution. Since this problem is similar to the Königsberg bridge problem, we will also use Euler's rule to solve it. As a result, we get the following answer: the boat must take travelers to island E or F so that they can pass over each bridge once. The same Euler rule implies that the required detour is impossible if it starts from island A.

Later on, Koenig (1774-1833), Hamilton (1805-1865) worked on graphs, among modern mathematicians - K. Berzh, O. Ore, A. Zykov.

Historically, graph theory was born more than two hundred years ago in the course of solving puzzles. For a very long time, she was away from the main directions of research of scientists, was in the realm of mathematics in the position of Cinderella, whose talents were fully revealed only when she was in the center of general attention.

The first work on graph theory, by the famous Swiss mathematician L. Euler, appeared in 1736. The impetus for the development of graph theory was at the turn of the 19th and 20th centuries, when the number of works in the field of topology and combinatorics, with which it has the closest ties, increased dramatically. 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 introduced in the work of the Hungarian mathematician Koenig in the 30s of the twentieth century.

Recently, graphs and related research methods organically permeate 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 management theory, scheduling theory, sociology, mathematical linguistics, economics, biology, medicine, and geography. Graphs are widely used in such areas as programming, finite automata theory, electronics, in solving probabilistic and combinatorial problems, shortest distance, etc. Mathematical fun and puzzles are also part of graph theory. Graph theory is developing rapidly, finding new applications.

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

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

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

No. Name of the graph Definition Figure An example of the use of this type of graph

1 Zero graph Vertices of the graph that do not belong Problem: Arkady, Boris. Vladimir, Grigory and Dmitry at the meeting shook hands with no one, each shook hands with each one once. How many edges are in total are called isolated. handshake was done? The situation corresponding to the moment when handshakes have not yet taken place is a dotted diagram 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 are made.

Notation: U" is 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 have not been built The situation when not all handshakes have yet been completed, shook hands A and B, A and D, E and possible edges are called incomplete D, C and E.

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 said to be instructed to remove snow from the streets of the part of the city shown in the picture. Is it possible for him to complete his work at the intersection where the garage is located, if it is possible to lay a route between these streets of his section of the city along each of them only once?

peaks.

In this case, no edge of the route should occur more than once. The vertex, from It is impossible, since a closed path passing through all the edges of the graph, and along which the route is laid, is called for each edge only once, if the degrees of all the vertices of the graph are even.

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

end of the path. A cycle is a path, in the figure, using a graph, a diagram of roads between populated areas is shown in which the beginning and end coincide. Simple points.

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

through one of the vertices of the graph more than one What is the difference between the AEH route and the AEFCEH route?

times. The fact that in the second route at the "crossroads" at point E we visited twice.

This route is longer than AEH. Route AEH can be obtained from route

If the cycle includes all edges AEFCEH "deleting" the FCE route from the last one.

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

called the Euler line.

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

Two vertices of the graph are called connected, 1 dm, without breaking the wire apart?

if there is a path in the graph that ends at these vertices. If there is no such path, the vertices are called not connected.

Since the path passing through all the 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 every 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. Genealogical tree Zholmurzaeva Tomiris.

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

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

8 The concept of a planar graph A graph that can be represented on a Task. In three different houses, three planes live in neighbors who have quarreled with each other. There are three wells not far from where its ribs cross from their houses. Is it possible from only at the tops, is called each house to lay 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 the ninth one, which does not intersect with any of the previously drawn paths.

We construct a graph whose vertices

A, B, C, 1, 2, 3

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

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 vertex hits

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” to the vertex B (i.e., it will not be possible to draw one of the edges B1, B2 or B3 that would not intersect the edges already in the graph).

The answer to the question of the task will be: “It is impossible!”

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

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

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

Conclusion on the work done:

I learned how to structure all information material into a table;

The composition of the theoretical material contributes to a visual representation of the types of graphs and their application;

She worked out examples of applying graph theory in compiling her family tree.

Application No. 1.

GENEOLOGICAL TREE

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

As an example, I took my family tree.

Section 3. Application of graph theory.

We meet with graphs more often than it is possible, it seems at first glance. Examples of graphs can be any road map, electrical circuit, drawing of polygons, etc. For a long time, it was believed that graph theory was 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 a connection between them. Graphs help to solve such problems, making it possible to visualize the relationship between the data of the problem. Graph theory itself was seen as 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 areas 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 one can use graphs. The presentation of data in the form of a graph gives them visibility. Many proofs are also simplified and become more convincing if graphs are used.

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

With the help of graphs, one can easily establish chains of logical consequences that lead to a provable statement. Briefly and accurately state the proof of the theorem and the solution of the problem.

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

Solution methods.

Proof of the problem by reasoning.

Let ABC be an isosceles triangle with

B1 A1 base AB and bisectors AA1 and BB1.

Consider ∆ABB1 and ∆BAA1. They have ∟B1AB=

∟A1BA as the angles at the base of the isosceles triangle ∆ABC. ∟ABB1= ∟A1AB

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

∆ABB1 = ∆BAB1 along the side and two corners adjacent to it. From the equality of triangles follows the equality of their sides AA1 and BB1.

Proof of the problem using a graph.

Prove: AA=BB

Let's use a 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-scheme is the assertion to be proved.

Color is used to highlight components. The condition of the theorem and the problem are blue. The assertion to be proved is red. Proof steps are in black.

The described form of proving theorems and solving problems is useful and convenient for students, because it makes it possible to single out the main stages of proving a theorem and solving a problem.

3. 2. Program-methodical complex.

a) Teacher's guide.

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

b) Workbook for students.

The manual is in the form of a workbook. The manual includes 28 graph-schemes with theorems and 28 graph-schemes 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 make up the solution to the problem.

Color is used to highlight components. The condition of the theorem and the problem are blue, the assertion being proved is red, the stages of the proof are black.

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

c) Electronic manual.

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

Creation programmatically - methodical complex and its implementation was carried out in the course of:

Conducting classes of the club "Aristotle" on the topic "Solving logical problems using graphs".

Applications of graphs in the proofs of geometric theorems and problems

At geometry lessons in grade 8.9.

Performances with the project at the school scientific and practical conferences.

CONCLUSION.

Summing up the results of the study of the use of graphs in the 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. The developed software and methodological complex for studying geometry in grades 7-9: a) a guide for the teacher; b) a workbook for students; c) the electronic manual is useful for students in grades 7-9.

Send your good work in the knowledge base is simple. Use the form below

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Similar Documents

Restoring graphs from given vertex adjacency matrices. Construction for each graph of the matrix of adjacency of edges, incidence, reachability, counterreachability. Search for the composition of graphs. Determination of local degrees of graph vertices. Search for the base of graphs.

laboratory work, added 01/09/2009

Graph theory as a branch of discrete mathematics that studies the properties of finite sets with given relationships between their elements. Basic concepts of graph theory. Adjacency and incidence matrices and their practical use when analyzing solutions.

abstract, added 06/13/2011

Basic concepts of graph theory. Vertex degree. Routes, chains, cycles. Connectivity and properties of directed and planar graphs, an algorithm for their recognition, isomorphism. operations on them. An overview of how to define graphs. Euler and Hamiltonian cycles.

presentation, added 11/19/2013

Description of a given graph by sets of vertices V and arcs X, adjacency lists, incidence and adjacency matrix. The weight matrix of the corresponding undirected graph. Determination of the shortest path tree using Dijkstra's algorithm. Finding trees on a graph.

term paper, added 09/30/2014

Basic concepts of graph theory. Distances in graphs, diameter, radius and center. The use of graphs in practical human activities. Definition of the shortest routes. Euler and Hamiltonian graphs. Elements of graph theory in optional classes.

thesis, added 07/19/2011

Concept and matrix representation of graphs. Directed and undirected graphs. Definition of adjacency matrix. Routes, chains, cycles and their properties. Metric characteristics of the graph. Application of graph theory in various fields of science and technology.

term paper, added 02/21/2009

Mathematical description of the system automatic control using graphs. Drawing up a graph and its transformation, getting rid of differentials. Optimization of directed and undirected graphs, compilation of adjacency and incidence matrices.

laboratory work, added 03/11/2012

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

Introduction

Our world is full of not only letters and numbers, but also a wide variety of images. These are paintings, and all kinds of photographs, as well as numerous diagrams. Schemes are found on the logos of companies and cars, road signs and maps. If you look at the metro map or bus route, it's just lines with dots. Such schemes of lines (edges) and points (vertices) are called graphs.

The theory of graphs appeared thanks to one entertaining problem that Leonhard Euler solved. History says that in 1736 this brilliant mathematician stopped in Königsberg. The city was divided by the river into 4 parts, connected by seven bridges. It was necessary to determine whether it is possible to bypass all the bridges by passing over each exactly once. Euler determined that it was impossible to solve the problem. The Königsberg bridges were destroyed during World War II, but this story gave rise to a beautiful mathematical theory - graph theory.

In the 20th century, graph theory has received incredible development, it has found numerous applications in planning, architecture, engineering, and especially in computer science and telecommunications. Graphs are related to combinatorics, discrete mathematics, topology, algorithm theory and other branches of mathematics.

What opportunities does a student who owns this theory get? Will he be able to achieve any success in his studies or ordinary life? This project is dedicated to such research.

Objective of the project: Show that the methods of graph theory give the student a tool to solve complex Olympiad problems, and in life - to organize the transfer of urgent information between people.

Hypotheses:

With the help of graphs, you can easily solve many Olympiad problems

Graph theory helps to create a system of urgent notification of the team

Tasks:

Learn how to solve problems using graphs

Develop a website for testing Olympiad tasks

Design an Urgent Classroom Alert system using a graph

Research objects: olympiad problems, warning systems

Subject of study: graph theory, web programming.

Research methods:

graph theory methods

web programming methods

Research plan:

Learn about the history of graph theory

Learn the rules for solving olympiad problems using graphs

Take the course "Web-programming" School Information technologies"REAL IT"

Develop a site for testing olympiad problems in graph theory and test it on friends

Design an Urgent Classroom Alert (SOK) system

Conduct an experiment to test the SOC system

Chapter 1. Graph Theory in Our Lives

1.1. Application of graph theory in different areas

Graphs are used in a variety of areas: in the design of electrical circuits, telephone networks, when searching for routes between settlements, in the economy.

In chemistry, graphs are used to represent different compounds. Graphs can be used to represent simple molecules and rather complex organic compounds.

Graph theory plays a key role in various phases of architectural projects. After the parts of the project are defined and before moving from sketches to drawings, it will be useful to build a relationship graph of the elements of the project. The analysis of graphs in public buildings will help determine the degree of accessibility of various departments, the location of premises (buffet, library, etc.), as well as fire escapes. Graphs allow you to significantly simplify the analysis difficult situations.

In our time, thanks to the Internet - a "network of networks" that connects computers around the world, the digital revolution has become possible. The power of computers has steadily increased, but it was thanks to networks that it was possible to make a giant leap to the digital world. Graphs and telecommunications have always gone hand in hand.

Figure 1.1 shows various schemes for connecting computers to each other. Most often there are three ways of connecting computers to a local network: "common bus", "star", and "ring". Each diagram has a graph, so the term "Network topology" is used. A network topology is a graph configuration whose vertices are computers and routers, and the edges are communication lines (cable) between them. In Figure 1.2, all topologies are shown as graphs.

A tree is a very simple graph in which there is only one path between any two vertices. Trees are used in genetics to illustrate family ties (family trees), as well as in the analysis of the probabilities of various events.

Figure.1.1. Options for building local computer networks

Figure 1.2. Options for building local computer networks

a - common bus, b - star, c - ring

There are many games in which you need to build a certain graph (maze games), or use the graph to determine if there is a winning strategy.

GPS, maps, and driving directions on the web are another great example of how graphs can be used. The edges in them are streets and roads, and the vertices are settlements. The vertices of such graphs have names, and the edges correspond to numbers indicating the distance in kilometers. Thus, such a graph is labeled and weighted. Graphs help visualize public transport patterns, making it easier to plan your trip.

Graphs are also used in the oil and gas industry in oil and gas transportation systems. With the help of graphic-analytical methods of gas transmission systems, it is possible to choose the shortest option from all possible ways of bypassing the pipeline.

The development of computer science has led to the fact that many mathematical models have been used in automatic processes. The machine can easily cope with the calculations, but choosing the best option from the set under uncertainty is a much more difficult task. New algorithms have emerged that use mechanisms reminiscent of a biological revolution. They use graphs as a way to visualize processes. Modeling of neurons in the human brain and the principle of their action formed the basis new theory- theories of neural networks.

1.2. Chapter conclusions.

Graph theory has found its application in many areas of science, technology and everyday life. However, despite its wide application in various fields, only superficial attention is paid to it in the school mathematics course. At the same time, various experiments in the field of education show that elements of graph theory have a high educational value, and therefore should be included in the school curriculum.

Indeed, it will be very useful for middle school students to learn the basics of graph theory, since they will help them in mastering the basic course of mathematics, and especially in solving olympiad problems in combinatorics and probability theory.

Chapter 2

2.1. Graph Theory in Olympiad Problems

Various mathematical olympiads, such as "Kangaroo", "Dino-Olympiad Uchi.ru", International Heuristic Olympiad "Owlet", also often include problems in graph theory in different formulations.

As you know, children are very fond of everything related to computers and the Internet, and it is not so easy to seat them at the table with a book on mathematics. In order to arouse the interest of schoolchildren in graph theory, the authors of the article, based on the courses on Web programming at the School of Information Technologies "REAL-IT", developed an online simulator that includes testing in graph theory, located on the page of the Tyumen private school "Evolventa »: evolventa-tmn.github.io . Schoolchildren are invited to solve six problems of different difficulty levels, he enters the answers in the boxes, and then by pressing the “Finish” button, the result is displayed: the number of problems he solved correctly (Figure 2.1).

Figure 2.1. Site screen fragment with test options

Naturally, a cunning child will immediately start looking for answers on search engines, but he will not find exactly such formulations, only similar ones, for example, on the website of the scientific and methodological electronic journal "Concept". Therefore, to obtain the desired result: 6 out of 6 tasks the student will have to understand general principles problem solving using graph theory. And in the future, the knowledge gained will help him successfully solve both school and Olympiad problems.

When the site was completely ready, tested and posted on the Internet, our classmates received a link to it. Interest in the site was great: judging by the visit counter, it was visited more than 150 times in the first week! Many guys tried to solve problems, but they seemed difficult to them. Even some parents with higher technical education, a number of tasks baffled, this suggests that graph theory is not even studied in all higher educational institutions. This means that the testing prepared by us will be useful not only for schoolchildren, but also for adults!

2.2. Graph theory in designing a class alert system

Currently, the sphere of urgent personnel management system in organizations is given great attention, due to the fact that such systems play a significant role in organizing all the activities of employees.

Initially, public address and evacuation management systems were conceived to urgently inform employees, staff and guests about a fire in a building, provide information and broadcast important information for a quick and successful evacuation of people. Today, such systems can be observed not only within the framework of one organization or enterprise, but throughout our country, used to improve people's safety.

It should be noted that most of the warning systems used are aimed at adults. But the most dangerous age is children. Children, too, need their own systems to alert most of their peers in the shortest possible time about an impending danger or a change in the situation.

At school, every child spends a significant part of his time: five to six days a week for several hours. Therefore, the creation of a warning system for children would make it possible to organize each child for a quick and competent reaction to the changed situation.

For example, this system would be very useful when transmitting a message about danger, information about an urgent gathering or about a change in the situation when they are in different parts of the school or in general in the forest on vacation (Figure 2.2)

Figure 2.2. Our class on an excursion to the GAU DO TO "Regional Center for Pre-Conscription Training and Patriotic Education" Outpost "

In this work, an attempt was made to create a Collective Notification System using the example of one class educational institution: MAOU SOSH No. 89.

Since children themselves must disseminate information, they should use only the types of communication available to them - mobile communications. The entire payroll of the class should be notified, therefore, in order to analyze which of the children is ready to notify which of their friends, a class survey was conducted. In the questionnaires, a restriction was initially set: each child manages to call a maximum of four friends, and if there is time, two more.

The survey showed a rather high activity of the guys: in general, about 118 calls will be made in the class. It is almost impossible to analyze such a volume of information in the mind, so it was decided to use information technology. The team notification model is best represented as a graph. The edges in it are calls (or sms), and the vertices are children. Since the vertices of the graph have names, and the edges correspond to numbers indicating the probability of a call (1 or 0.5), then such a graph is labeled and weighted. The graph helps visualize the team notification scheme, which facilitates modeling.

It was decided to visualize the graph using the RAMUS CASE tool, since it allows you to work with the color of vertices and edges, and also allows you to move graph vertices with edges attached to them for clarity. Figure 2.3 shows a graph of the RNS system.

On November 19, 2017, the designed SOK system was tested. Initially, we planned that the notification would take place over three laps. For the first circle (the beginning of the notification), we chose two children whom no one wants to call, but they are ready to call, as well as the authors of the Project themselves (Fig. 2.3, pink blocks). Further information is transmitted to the second circle of notification (Fig. 2.4, yellow blocks). And on the third notification circle (Fig. 2.4, green blocks) the whole class will be informed. But during the experiment, we saw that some children are in training for 1.5-2 hours and do not look at the phone, others with a negative balance, therefore, cannot call.

Figure 2.3. class alert graph

Figure 2.4. SOK alert circles

Therefore, in reality, our class was notified only in 490 minutes - that's 8 hours and 10 minutes. But it was all 100%. The important thing here is that our system has the structure not of a tree, but of a graph. And in it, several paths lead from one vertex to another, so in any case, everyone will be notified!

Figure 2.6 shows a graph of class alerts (number of alerted people) versus time (in minutes).

Figure 2.6. class alert schedule

To make it easier to keep track of notifications, during the testing process, the children had to tell the authors of the Project their favorite subject, and they kept a record of when and who reports the information.

Another test result - a survey of favorite subjects (Figure 2.7), showed that children in our class love mathematics, computer science and outdoor games most of all! And this means that they may like graph theory just as much as we do.

Figure 2.7. Pie Chart of Favorite Class Items

2.3. Chapter conclusions.

We tested both hypotheses. The site we developed for testing olympiad problems in graph theory helped to establish that a number of olympiad problems simply cannot be solved without knowledge of graph theory, and even for adult engineers. The first hypothesis was confirmed.

The second hypothesis also turned out to be correct. The designed and tested collective notification system, using the example of one class, made it possible to notify the entire children's team in 8 hours and 10 minutes. By optimizing the graph, you can achieve faster results.

Conclusion.

We hope that after getting acquainted with graph theory and its numerous applications in various fields, students will awaken interest in graph theory, and they will continue to study this branch of mathematics on their own. The result of the study will be higher results at the Olympiads.

Regarding the application of graph theory in real life, the relevance of the topic under consideration is emphasized by the fact that the creation of a warning system for children will increase the speed of transmission of urgent information, cover most of the children's team for which this system will be used, reduce the response time of children, and also ensure maximum safety for the children's team. All this indicates the obvious advantages of implementing the designed system.

Bibliography

Beloborodova A.A. Development of spatial thinking with the help of labyrinth games / A.A. Beloborodova // "Student Scientific Forum": materials of the VIII International Student Electronic scientific conference.- 2017. https://www.site/2017/7/26746

Beloborodova, A.A. Development of a web simulator for studying graph theory / A.A. Beloborodova, S.V. Pakhotin, A.A. Frolov // New information technologies in the oil and gas industry and education: materials of the VII International Scientific and Technical Conference; resp. ed. IS HE. Kuzyakov. - Tyumen: TIU, 2017. - S. 156-159.

Beloborodova A.A. Don't get lost in math! / A.A. Beloborodova // XVIII All-Russian Children's Competition of Scientific Research. and creative works "First Steps in Science": a collection of abstracts. - M.: NS Integration, State Duma of the Federal Assembly of the Russian Federation, Ministry of Education and Science of Russia. - 2016. - P. 110-111.

Gendenstein, L.E. Alice in the land of mathematics. Tale-tale / For junior. and avg. school age. - Kharkiv: Ed. - commercial. enterprise "Paritet" LTD, 1994.-288 p., ill.

Davletshin, M.I. Study of the effectiveness of image noise removal methods / M.I. Davletshin, K.V. Syzrantseva // Energy saving and innovative technologies in the fuel and energy complex: materials of Int. scientific-practical. conf. students, graduate students, young scientists and specialists. T.1 / otv. editor A.N. Khalin. - Tyumen: TIU, 2016. - S. 25-29.

Karnaukhova, A.A. The use of graph theory in solving problems in the economy / A.A. Karnaukhova, A.F. Dolgopolova // Proceedings of the VII International Student Electronic Scientific Conference "Student Scientific Forum". http://www.scienceforum.ru/2015/991.

Kern, G. Labyrinths of the World. St. Petersburg: Publishing house "Azbuka-classika", 2007, 448p.

Krause, M.V. Application of information technologies for designing a collective notification system / M.V. Krause, A.A. Beloborodova, E.I. Arbuzova // New information technologies in the oil and gas industry and education: materials of the VII International Scientific and Technical Conference; resp. ed. IS HE. Kuzyakov. - Tyumen: TIU, 2017. - S. 153-156.

Course "Creating Websites" School of Information Technology "REAL-IT" http://it-schools.org/faculties/web/

The World of Mathematics: in 40 volumes. V.11: Claudi Alsina. Metro maps and train networks. Graph theory./ Per. from Spanish - M.: De Agostini, 2014.- 144 p.

Moskevich L.V. Educational Olympiad - one of the forms of extracurricular activities in mathematics / L.V. Moskevich // Scientific and methodological electronic journal "Concept". - 2015. - T. 6. - S. 166-170. - URL: http://e-koncept.ru/2015/65234.htm.

Memo to the population "Notification of the population in the event of a threat and an emergency" http://47.mchs.gov.ru/document/1306125

Rumyantsev, V.O. Mathematical modeling of the gas transmission system using graph theory / V. O. Rumyantsev // Problems of Geology and Mineral Development: Sat. scientific tr. / TPU. - Tomsk, 2017. - S. 340 - 342.

Website of the Ministry of Emergency Situations of the Russian Federation http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves