1736, Koenigsberg. The Pregelya River flows through the city. There are seven bridges in the city, located as shown in the figure above. Since ancient times, the inhabitants of Königsberg have struggled with a riddle: is it possible to cross all the bridges, crossing each one only once? This problem was solved both theoretically, on paper, and in practice, on walks - passing along these very bridges. No one was able to prove that this was impossible, but no one could make such a “mysterious” walk across the bridges.

The famous mathematician Leonhard Euler managed to solve the problem. Moreover, he solved not only this specific problem, but came up with a general method for solving similar problems. When solving the problem of the Königsberg bridges, Euler proceeded as follows: he “compressed” the land into points, and “stretched” the bridges into lines. Such a figure, consisting of points and lines connecting these points, is called COUNT.

A graph is a collection of a non-empty set of vertices and connections between vertices. Circles are called vertices of the graph, lines with arrows are arcs, and lines without arrows are edges.

Types of graphs:

1. Directed graph(briefly digraph) - whose edges are assigned a direction.

2. Undirected graph is a graph in which there is no direction of the lines.

3. Weighted graph– arcs or edges have weight (additional information).

Solving problems using graphs:

Task 1.

Solution: Let us denote the scientists as the vertices of the graph and draw lines from each vertex to four other vertices. We get 10 lines, which will be considered handshakes.

Task 2.

There are 8 trees growing on the school site: apple tree, poplar, birch, rowan, oak, maple, larch 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. Arrange the trees from shortest to tallest.

Solution:

The vertices of the graph are trees, indicated by the first letter of the tree name. There are two relationships in this task: “to be lower” and “to be higher.” Consider the relation “to be lower” and draw arrows from a lower tree to a higher one. If the problem says that the mountain ash is taller than the larch, then we put an arrow from the larch to the mountain ash, etc. We get a graph that shows that the shortest tree is maple, followed by apple, larch, rowan, pine, oak, birch and poplar.

Task 3.

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

Solution:

Below is a breakdown of the tasks.

MUNICIPAL AUTONOMOUS EDUCATIONAL INSTITUTION SECONDARY SCHOOL No. 2

Prepared

Legkokonets Vladislav, student of class 10A

Practical application of Graph Theory

Supervisor

L.I. Noskova, mathematics teacher

Art. Bryukhovetskaya

2011

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

2. History of the emergence of graph theory………………………………………….………..4

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

4. Problems solved using graphs……………………………..………………………..8

4.1 Famous problems………………………………….………………………...8

4.2 Several interesting problems………………………………….……………..9

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

6. Solving problems………………………………………………………………………………………...12

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

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

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

Introduction

Born from solving puzzles and entertaining games, graph theory has now become a simple, accessible and powerful tool for solving questions 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 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 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. That's why relevance The topic is determined, on the one hand, by the popularity of graphs and related research methods, and on the other, an undeveloped, holistic system for its implementation.

Solving many problems in life requires long calculations, and sometimes even these calculations do not bring success. This is what research problem. The question arises: is it possible to find a simple, rational, short and elegant solution to solve them. Is problem solving easier if you use graphs? This determined topic of my research: “Practical application of graph theory”

Purpose The research was to use 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 activity.

Research objectives:

1. Study literature and Internet resources on this issue.

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

3. Draw a conclusion.

Practical significance of the study is that the results will undoubtedly arouse the interest of many people. Haven't any of you tried to build your family tree? How to do this correctly? The head of a transport enterprise probably has to solve the problem of more profitable use of transport when transporting goods from a destination to several settlements. Every schoolchild has encountered logical transfusion problems. It turns out that they can be easily solved using graphs.

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

History 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 given a problem about an island located in the city of Königsberg and surrounded by a river with seven bridges across it.

[Appendix Fig.1] The question is whether someone can go around them continuously, passing only once over each bridge. And then I was informed that no one had yet been able to do this, but no one had proven that it was 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 in all problems of this kind to immediately determine whether such a detour can be made through any number and any number of bridges located or not. The Koenigsberg bridges are located in such a way that they can be represented in the following figure [Appendix Fig.2], in which A denotes an island, and B, C and D - parts of the continent separated from each other by river branches

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 is generally impossible ... if other, more serious problems could be brought here, this method could be of even greater benefit and should not be neglected." .

Basic definitions and theorems of graph theory

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

Definition 1. A graph is a collection of a finite number of points, called the vertices of the graph, and pairwise lines connecting some of these vertices, called the 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 what follows, we will denote the vertices of the graph by Latin letters A, B, C, D. Sometimes the graph as a whole will be denoted by one capital letter.

Definition 2. Vertices of a graph that do not belong to any edge are called isolated.

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

Notation: O "– a graph with vertices that has 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 to which the vertex belongs.

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

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 to obtain a complete graph.

Definition 8. A graph that can be represented on 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 is called its face.

The concepts of a planar graph and a graph face are used when solving problems on the “correct” coloring of various maps.

Definition 10. A path 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 in which the starting and ending points coincide.

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. Length of the path , laid on a loop , the number of edges of this path is called.

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.

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 tree graph 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 entirely of trees is called a forest.

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

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

Problems solved using graphs

Famous problems

Traveling salesman problem

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

The problem statement is as follows.
A traveling salesman (wandering merchant) must leave the first city, visit cities 2,1,3..n once in an unknown order and return to the first city. The distances between cities are known. In what order should one go around the cities so that the closed path (tour) of a 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 severely for greed.
Consider for example the network in the figure [Appendix Fig.3], representing a narrow rhombus. Let a traveling salesman start from city 1. The “go to the nearest city” algorithm will take him to city 2, then 3, then 4; at the last step you will have to pay for your greed, returning along the long diagonal of the diamond. The result will be not the shortest, but the longest tour.

Problem about the Königsberg bridges.

The problem is formulated as follows.
The city of Koenigsberg is located on the banks of the Pregel River and two islands. The different parts of the city were connected by seven bridges. On Sundays, townspeople took walks around the city. Question: is it possible to take a walk in such a way that, when you leave the house, you return back by walking exactly once over each bridge?
Bridges across the Pregel River are located as in the picture[Appendix Fig.1].

Consider the graph corresponding to the bridge diagram [Appendix Fig. 2].

To answer the question of the problem, it is enough to find out whether the graph is Eulerian. (An even number of bridges must extend from at least one vertex). You can’t walk around the city and cross all the bridges once and come back.

Several interesting tasks

1. "Routes".

Problem 1

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

Solution:

The road map shows that Chichikov began his journey from estate E, and ended with estate O. We note that only two roads lead to estates B and C, so Chichikov had to travel along these roads. Let's mark them with a bold line. Sections of the route passing through A have been identified: AC and AB. Chichikov did not travel on the roads AE, AK and AM. Let's cross them out. Let us mark with a bold line ED; Let's cross out DK. Let's cross out MO and MN; Let's mark with a bold line MF; cross out FO; Let's mark FH, NK and KO with a bold line. Let's find the only possible route under this condition. And we get: estate E - belongs to Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Appendix Fig.5].

Problem 2

The figure shows a map of the area [Appendix Fig. 6].

You can only move in the direction of the arrows. You can visit each point 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:

We sequentially “stratify” the circuit into a tree, starting from vertex 1 [Appendix Fig.7]. Let's get a tree. The number of possible ways to get 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"

Problem 1

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

a) an even number of envelopes were handed over;

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 the guys exchanging 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. The total number of transmitted envelopes N is equal to the sum of the degrees of all vertices of the graph N = degree. A 1 + step. A 2 + + . . . + step. A n -1 + degree. And n, N =2p, where p is the number of edges of the graph, i.e. N – even. Consequently, an even number of envelopes were handed over;

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

Problem 2

One day Andrei, Boris, Volodya, Dasha and Galya agreed to go to the cinema in the evening. They decided to coordinate the choice of cinema and show over the phone. It was also decided that if it was not possible to contact someone by phone, then the trip to the cinema would be cancelled. In the evening, not everyone gathered at the cinema, and therefore the movie visit was cancelled. 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 couldn't get on the phone and therefore didn't come to the meeting?

Solution:

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

[Appendix Fig.9]

From the picture it is clear that each of the guys - Andrey, Boris and Volodya - telephoned everyone else. That's why these guys came to the cinema. But Galya and Dasha were unable to get on the phone with each other (points G and E are not connected by a line segment) and therefore, in accordance with the agreement, did not come to the cinema.

Application 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 production, 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 encounter 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, and automation. Many mathematical facts can be conveniently formulated 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 is finding more and more applications in applied issues. Even computational 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 displaying the structure of molecules [Appendix Fig. 10]. The vertices and edges of these graphs correspond to the corresponding atoms and chemical bonds between them.

Molecular graphs and trees: [Appendix Fig. 10] a, b - multigraphs, respectively. ethylene and formaldehyde; they say pentane isomers (trees 4, 5 are isomorphic to tree 2).

In the stereochemistry of organisms the most. Molecular trees are often used - the main trees of molecular graphs, which contain only all the vertices corresponding to the C atoms. Compilation of sets of mol. trees and the establishment of their isomorphism make it possible to determine that they say. structures and find the total number of isomers of alkanes, alkenes and alkynes

Protein networks

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

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

Typically, a tree representing a hierarchical system has one main vertex, 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 is included in one top-level class. Any vertex of a tree can generate several descendants - vertices corresponding to classes of the lower level.

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 pedigree is represented in the form of a family tree, which is a “tree” in the sense of graph theory.

Example of my family tree [Appendix Fig. 12].

One more example. The picture shows the biblical family tree [Appendix Fig. 13].

Problem solving

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

Solution:

First, let's make a graph of all possible travel routes [Appendix 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-like [Appendix Fig.15].

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

The result is 24 solutions, but we only need the shortest paths. Of all the solutions, only two are satisfactory, this is 350 km.

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

Logical problem involving transfusion. The bucket contains 8 liters of water, and there are two pans with a capacity of 5 and 3 liters. you need to pour 4 liters of water into a five-liter pan and leave 4 liters in the bucket, i.e. pour the water equally into the bucket and a large pan.

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 structured, what components they consist of, what are the tools with which problems are solved.

Solving practical problems using graph theory, it became clear that in every step, in 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 of a geometric representation of the 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.

While solving a transport problem or a task of drawing up a family tree, I came to the conclusion that the graph method is certainly interesting, beautiful and visual.

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

This scientific work examines mathematical graphs, their areas of application, and solves several problems using graphs. Knowledge of the basics of graph theory is necessary in various areas related to production and business management (for example, network construction schedule, mail delivery schedules). In addition, while working on a scientific paper, I mastered working on a computer using the WORD text editor. Thus, the objectives of the scientific work have been 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.

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

Zykov A.A. Finite graph theory. -Novosibirsk: Science, 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. "World", 1972 (chapter 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Old entertaining problems”, M. “Science”, 1988 (part 2, section 8; appendix 4);

Application

Application

P

Rice. 6

Rice. 7

Rice. 8

application

Application

Application

Application

P

Rice. 14

application

Application

Among the problems associated with solving logical problems, the close attention of researchers in recent years has been attracted by the question of applying graph theory to this type of problem.

Graph theory is currently an intensively developing branch of discrete mathematics. This is explained by the fact that many objects and situations are described in the form of graph models: communication networks, circuits of electrical and electronic devices, chemical molecules, relationships between people and much more.

Graph tasks have a number of advantages that allow them to be used to develop imagination and improve logical thinking. Graph problems can be presented in an entertaining, playful form.

Subject of research in this work is the solution of logical problems using graphs.

Purpose of the study: apply the graph apparatus to solve logical problems.

Hypothesis: In our opinion, solving many logical problems will be less labor-intensive; we will use graph theory for this.

Research objectives:

consider solving problems using graphs;

learn to translate problems into graph language;

compare traditional problem solving methods with graph theory methods.

In 1736, the great mathematician Leonhard Euler found a solution to a puzzle called the Königsberg Bridge Problem. The Pregel River, flowing through Kaliningrad (formerly the city was called Königsberg) washes two islands (Fig. Figure 1 Figure 1). In Euler's time, the banks of the river and the islands were connected by bridges as shown in the figure. The puzzle required finding a route that passed through all four landmasses once, and the end and beginning of the path must coincide.

Picture 1

L. Euler proved that there is no route that would meet the conditions of the puzzle, and developed a theory for solving this kind of puzzle. Knowing the material in the introductory part of the course “Introduction to Graphs,” it is not difficult to reproduce the idea of ​​​​L. Euler’s reasoning. To do this, you must first replace Figure 1 with the diagram shown in Figure 2, where islands and shores are represented by dots.

Figure 2

The diagram shown in Figure 2 is not, strictly speaking, a graph: it has multiple edges. However, the year 1736, when this puzzle was solved, is generally considered to be the year graph theory was born.

More than a hundred years later, in 1874, the German scientist G. Kirchhoff developed an effective method for determining the value of current in an electrical circuit, using methods and concepts that later received citizenship rights in graph theory. Another 10 years later, the English mathematician A. Keli (his mother was Russian, he spoke Russian and followed Russian mathematical literature; he was among those few mathematicians who from the very beginning understood and supported the ideas of N.I. Lobachevsky) developed the theory of trees to count the number of isomers of saturated hydrocarbons with a given number n carbon atoms.

In mathematics, a graph is a finite collection of points called vertices; which of them are connected to each other by lines called graph edges.

A graph is a set of points depicted on a plane (sheet of paper, board), some pairs of which are connected by lines. The points are called vertices of the graph, the lines are called edges. The degree of a vertex is the number of edges emerging from the vertex.

When looking at a geographical map, the railway network immediately catches your eye. This is a typical graph: the circles represent the stations that are the vertices of the graph, and the paths connecting them represent the edges.

Figure 3

The graph in Fig. Figure 3 depicts a diagram of roads between the villages M, A, B, C and D. Here, every two vertices are connected by an edge. Such a graph is called complete. The numbers in the figure indicate the distances between villages along these roads. Let there be a post office in village M and the postman must deliver letters to the other four villages. There are many different travel routes. How to choose the shortest one? The easiest way is to analyze all the options. A new graph will help you do this, making it easy to see possible routes. Peak M at the top is the beginning of the routes. From there you can start the journey in four different ways: to A, to B, to C or to D. After visiting one of the villages, there are three options for continuing the route, then two, then the road to the last village and again to M. Total 43 21  24 ways.

Similar problems often arise when finding the best options for distributing goods to stores and materials to construction sites.

Consider one of the simplest problems: “Red, blue, yellow and green pencils are in four boxes, one at a time. The color of the pencil is different from the color of the box. It is known that a green pencil is in a blue box, but a red pencil is not in a yellow one. Which box does each pencil come in?”

Let's denote pencils and boxes with dots. A solid line will indicate that the pencil is in the corresponding box, and a dotted line will indicate that it is not. Then, taking into account the problem, we have G 1 (Fig. Figure 4).

Figure 4

Next, we complete the graph according to the following rule: since exactly one pencil can lie in the box, then one solid line and three dotted ones should come out of each point. The result is a graph G 2 , which gives a solution to the problem.

When solving problems that are usually called logical in popular science and methodological literature, as a rule, they do not rely in any significant way on school knowledge and skills. In this regard, they are traditionally considered a measure of ingenuity, an indicator of the level of mathematical abilities, acuity of thinking, the ability to use memory, and are often discussed in school mathematics clubs.

Solving many logical problems using graphs is quite accessible to younger students. To do this, it is enough for them to have only an intuitive understanding of graphs and their most obvious properties.

Let's look at examples of using graphs to solve some well-known problems. In this case, we will represent the objects by points, and the relationships between them – by segments (the positions of the points and the lengths of the segments are arbitrary).

Clarification of the structures of logical problems from the point of view of the applied solution methods makes it possible to isolate certain classes of such problems.

Task 1. Three friends are talking: Belokurov, Chernov and Ryzhov. The brunette told Belokurov: “It’s curious that one of us is blond, another is a brunette, the third is red, but no one’s hair color matches their surname.” What hair color does each of your friends have?

Let's give a detailed solution. Let's construct a graph of the relationship specified in the problem statement. To do this, first of all, let’s highlight a lot of surnames M and many hair colors TO, the elements of which will be denoted by dots. Set points M let's call them the letters B, Ch, R (Belokurov, Chernov and Ryzhov); points of the second set - b, br, p (blond, brunette, red). If a point from one set corresponds to a point from another, we will connect them with a solid line, and if it does not correspond, we will connect them with a dashed line. The condition of the problem indicates only inconsistencies, so first the graph shown in Figure 5 should appear.

Figure 5

From the conditions of the problem it follows that for each point from the set M there is one and only one tonka of the many TO, which corresponds to the first and, conversely, to each point from the set TO corresponds to one and only one point from the set M. The task comes down to finding this only possible correspondence between the elements of the sets M And TO, i.e., to finding three solid lines connecting the corresponding points of the sets.

The principle of solving the problem is simple. If some point is connected to two points of another set by dashed lines, then it must be connected to its third point by a solid line. Therefore, the graph in Figure 5 is supplemented with solid lines connecting points B and p, P and b (Figure 6).

Figure 7

Thus, in the graph of this figure we automatically read the answer: Belokurov is red-haired, Chernov is blond, Ryzhov is brunette. The same technique can be used to solve, for example, problems 2 and 3.

Task 2. Pies were baked for Vanya, Kolya and Misha: one with cabbage, another with rice, the third with apples. Misha doesn't like apple pie and doesn't eat it with cabbage. Vanya doesn't like cabbage pie. Who's eating what pie?

Task 3. Three friends work at the same factory: a mechanic, a turner and a welder. Their last names are Borisov, Ivanov and Semenov. The locksmith has no brothers or sisters, he is the youngest of his friends. Semenov, married to Borisov's sister, is older than the turner. What are the names of the mechanic, turner and welder?

The above problems can be successfully solved using tables. This method or its modifications are recommended and discussed in many popular science books and teaching aids. It is possible, however, to indicate classes of problems in which the use of graphs represented by points and segments turns out to be more convenient and justified. Using the method of tables such as tournament tables or their generalizations in decisions forces an important part of the reasoning to be carried out “orally”. At the same time, you have to repeatedly return to the conditions of the problem, to intermediate results, remember a lot and use the information received at the right time. This type of problem includes problems with three or more sets of objects under consideration.

Task 4. Three comrades - Ivan, Dmitry and Stepan - teach various subjects (chemistry, biology, physics) in schools in Moscow, Leningrad and Kyiv. Known:

1. Ivan does not work in Moscow, and Dmitry does not work in Leningrad;

2. Moskvich does not teach physics;

3. The one who works in Leningrad teaches chemistry;

4. Dmitry does not teach biology.

What subject and in what city does each of the comrades teach?

Solution. Let us distinguish three sets: a set of names, a set of objects and a set of cities. An element of each of the sets in Figure 4 is given by its own point (the letters in this figure are the first letters of the corresponding words). If two points from different sets characterize the characteristics of different people, then we will connect such points with a dashed line. If two points from different sets correspond to the characteristics of one person, then we will connect such points in pairs with solid lines. It is important that, according to the conditions of the problem, for each point of any set in each of the other sets there is one and only one point corresponding to it.

Figure 8

Thus, the graph in Figure 8 contains all the elements of the sets specified in the condition and the relationships between them. The problem in the language of graphs comes down to finding three “solid” triangles with vertices in different sets.

Let's consider the graph in Figure 8. The dashed segment XD suggests itself. Indeed, A corresponds to X and, at the same time, A does not correspond to D, i.e. X cannot correspond to D. So, a typical graph operation for this kind of problem is used: if the triangle with vertices in three different sets, one side is solid, the second is dashed, then the third must be dashed. From the conditions of the problem it follows that another operation on the graph is uniform: if some point is connected by dashed segments to two points in the second set, then it should be connected to the third point of this set by a solid segment. This is how a continuous segment of the DF is drawn. Next, draw the dashed segment DM (in the triangle DFM the side DF is solid, and FM is dashed), DK is solid (DM and DL are dashed), Now we connect the points F and K with a solid segment. If in a triangle with vertices in different sets two sides are solid, then the third will also be solid. The first “solid” triangle DFK has been found. So, without returning to the text of the problem, guided only by the natural operations on the graph described above, we find a solution (Fig. 9).

Figure 9

Let us note the sequence in which the segments were carried out: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. The vertices of each of the three resulting “solid” triangles determine the answer to the problem: Ivan teaches chemistry in Leningrad, Dmitry teaches physics in Kyiv, and Stepan teaches biology in Moscow.

In the following problem, the use of graphs helps to detect the presence of two solutions.

Task 5. Masha, Lida, Zhenya and Katya can play different instruments (cello, piano, guitar and violin), but each only on one. They also speak different foreign languages ​​(English, French, German and Spanish), but each only on one. It is known :

1. the girl who plays the guitar speaks Spanish;

2. Lida does not play the violin or cello and does not know English;

3. Masha does not play the violin or cello and does not know English;

4. a girl who speaks German does not play the cello;

5. Zhenya knows French, but does not play the violin.

Who plays what instrument and what foreign language does he know?

The problem conditions correspond to the graph shown in Figure 10.

Figure 10

The notation and principle of solution here are the same as in problem 4. Let us draw the following solid segments sequentially: KS, VZH, VF, AK (Fig. 11).

Figure 11

Thus, two “solid” triangles ZHVF and KSA are formed. We carry out another continuous segment of the launch vehicle. Now we are convinced that the conditions of the problem do not ensure the unambiguous choice of the third point for each of the pairs of RN and GI. The following options for “solid” triangles are possible: MGI and OSR or LGI and MRN. Thus, the problem has two solutions.

Let us present a problem in which the graph allows one to quite easily detect the redundancy of a condition.

Task 6. Six partners from different professions took part in the chess tournament: a turner, a mechanic, an engineer, a teacher, a doctor and a driver. Known:

1. in the first round, Andreev played with the doctor, the teacher with Borisov, and Grigoriev with Evdokimov;

2. in the second round, Dmitriev played with the turner, and the doctor with Borisov;

3. in the third round, Evdokimov played with an engineer;

4. at the end of the tournament the places were distributed like this - BorisovIplace, Grigoriev and the engineer sharedIIAndIIIplaces, Dmitriev tookIVplace, and Zolotarev and the mechanic shared fifth and sixth places.

What professions did Grigoriev, Dmitriev and Evdokimov have?

The text of the work is posted without images and formulas.
The full version of the 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: to 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 teaching, 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

1. Graph theory. Basic Concepts

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 .

1. Characteristics of graphs

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, the English mathematician Percy Heawood proved that five colors would be 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.
Practical research of the problem	Consider and analyze the areas of practical application of 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. The structural formulas of 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 the nth generation of 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 the demand for the 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.

Roads have been built between settlements A, B, C, D, E. You need to determine the length of the shortest path between points A and E. You can only move along 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.

The effectiveness of educational activities in developing 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 in Murmansk.

LIST OF REFERENCES USED

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

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

Gardner M. “Mathematical 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

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 promotes the acquisition of fundamental education, the formation of a worldview and the 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 automata 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.

The tutorial 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 edges (length, curvature), as well as the relative position of the vertices on the plane, are essential.

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

with bijection

Transitivity.

G 1 G 2

bijection

1,a

with bijection

then G G

with bijection

2 (1 ) .