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 [see. pp. 41-42]:
“I was once asked a problem about an island located in the city of Königsberg and surrounded by a river across which seven bridges are thrown. The question is whether anyone can go around them continuously, passing only once through each bridge. And then I was informed that no one still have not been able to do this, but no one has proven that it is impossible. This question, although trivial, seemed to me, however, worthy of attention in that neither geometry, nor algebra, nor combinatorial art are sufficient to solve it... After much thought, I found an easy rule, based on a completely convincing proof, with the help of which it is possible to immediately determine in all problems of this kind whether such a detour can be made through any number of bridges located in any way or not. so that they can be represented in the following figure[fig.1] , in which A denotes an island, and B, C and D - parts of the continent, separated from each other by river branches. The seven bridges are labeled a, b, c, d, e, f, g."
(FIGURE 1.1)
Regarding the method he discovered to solve problems of this kind, Euler wrote [see. pp. 102-104]:
“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:
0 "The question is to determine whether it is possible to go 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 there are separated by water - those that 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 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." .
The rationale for the above rule can be found in a letter from L. Euler to his friend Ehler dated April 3 of the same year. We will retell below an excerpt from this letter.
The mathematician wrote that the transition is possible if there are no more than two areas in the fork of the river, to which an odd number of bridges lead. To make it easier to imagine this, we will erase the already traversed bridges in the figure. It’s easy to check that if we start moving in accordance with Euler’s rules, cross one bridge and erase it, then the figure will show a section where again there are no more than two areas to which an odd number of bridges leads, and if there are areas with an odd number bridges we will be located in one of them. Continuing to move on like this, we will cross all the bridges once.
The story of the bridges of the city of Königsberg has a modern continuation. Let's open, for example, a school textbook on mathematics edited by N.Ya. Vilenkina for the sixth grade. In it, on page 98, under the heading of developing attentiveness and intelligence, we will find a problem that is directly related to the one that Euler once solved.
Problem No. 569. There are seven islands on the lake, which are connected to each other as shown in Figure 1.2. Which island should a boat take travelers to so that they can cross each bridge and only once? Why can't travelers be transported to the island? A?
Solution. Since this problem is similar to the problem of the Königsberg bridges, when solving it we will also use Euler’s rule. As a result, we get the following answer: the boat must deliver travelers to the island E or F so that they can cross each bridge once. From the same Euler rule it follows that the required detour is impossible if it starts from the island A.
In conclusion, we note that the problem of the Königsberg bridges and similar problems, together with a set of methods for their study, constitute a very important branch of mathematics in practical terms, called graph theory. The first work on graphs belonged to L. Euler and appeared in 1736. Subsequently, Koenig (1774-1833), Hamilton (1805-1865), and modern mathematicians C. Berge, O. Ore, A. Zykov worked on graphs.
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
Our world is full of not only letters and numbers, but also a wide variety of images. These include paintings, all kinds of photographs, as well as numerous diagrams. Schemes are found on company and car logos, road signs and maps. If you look at a map of a subway or bus route, they are just lines with dots. Such patterns of lines (edges) and points (vertices) are called graphs.
Graph theory came into being thanks to an interesting problem solved by Leonhard Euler. History says that in 1736 this brilliant mathematician stopped in Konigsberg. The city was divided by the river into 4 parts, connected by seven bridges. It was necessary to determine whether it was possible to bypass all the bridges by crossing each one 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 received incredible development; it found numerous applications in problems of planning, architecture, engineering, and especially in computer science and telecommunications. Graphs are related to combinatorics, discrete mathematics, topology, theory of algorithms and other branches of mathematics.
What opportunities does a student who masters this theory get? Will he be able to achieve any success in his studies or everyday life? This project is dedicated to such research.
Objective of the project: Show that graph theory methods give schoolchildren a tool that allows them to solve complex Olympiad problems, and in life, to organize the transfer of urgent information between people.
Hypotheses:
Using graphs you can easily solve many Olympiad problems
Graph theory helps create an urgent team notification system
Tasks:
Understand methods for solving problems using graphs
Develop a website for testing Olympiad problems
Design an Urgent Class Notification system using a graph
Objects of study: Olympiad tasks, 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” at the School of Information Technologies “REAL-IT”
Develop a website for testing Olympiad problems in graph theory and test it on friends
Design an Urgent Class Alert System (UCA)
Conduct an experiment to test the RNS system
Chapter 1. Graph theory in our lives
1.1. Application of graph theory in various fields
Graphs are used in a variety of areas: when designing electrical circuits, telephone networks, when searching for routes between populated areas, in economics.
In chemistry, graphs are used to represent different compounds. Using graphs, you can depict both simple molecules and quite complex organic compounds.
Graph theory plays a key role in various stages of architectural projects. Once the parts of the project have been identified, and before moving from sketches to drawings, it is useful to construct a graph of the relationships between the elements of the project. 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 can significantly simplify the analysis of complex situations.
Nowadays, thanks to the Internet, a “network of networks” connecting computers around the world, the digital revolution has become possible. The power of computers has steadily increased, but it was thanks to networks that the giant leap to the digital world was possible. Graphs and telecommunications have always gone hand in hand.
Figure 1.1 shows various diagrams for connecting computers to each other. Most often, there are three ways to connect computers into a local network: “common bus”, “star”, and “ring”. Each circuit has a corresponding graph, which is why the term “Network Topology” is used. Network topology is the configuration of a graph, the vertices of which are computers and routers, and the edges are communication lines (cable) between them. In Figure 1.2, all topologies are depicted 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 relationships (family trees) and to analyze 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 whether a winning strategy exists.
GPS, maps and driving directions presented on the Internet are another great example of the use of graphs. 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 you visualize public transport schemes, which makes it easier to plan your trip.
Graphs are also used in the oil and gas industry in oil and gas transportation systems. Using graphic-analytical methods of gas transportation systems, it is possible to select the shortest option from all possible routes bypassing the pipeline.
The development of computer science has led to the use of many mathematical models in automatic processes. A machine can easily handle calculations, but choosing the best option from a set under conditions of uncertainty is a much more difficult task. New algorithms have emerged that use mechanisms reminiscent of biological revolution. They use graphs as a way to visualize processes. Modeling the neurons of the human brain and the principle of their operation formed the basis of a new theory - the theory of neural networks.
1.2. Conclusions on the chapter.
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 high educational value, and therefore should be included in the school curriculum.
Indeed, it will be very useful for middle school students to study 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. Graph theory to help schoolchildren
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 on 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 interest among schoolchildren in graph theory, the authors of the article, based on the completed courses in Web programming at the REAL-IT School of Information Technologies, developed an online simulator, including testing in graph theory, located on the page of the Tyumen private school "Evolventa" ": evolventa-tmn.github.io. Schoolchildren are asked to solve six problems of varying difficulty levels, he enters the answers into the boxes, and then by clicking the “Done” button, the result is given: the number of problems he solved correctly (Figure 2.1).
Figure 2.1. Fragment of the site screen with testing options
Naturally, a cunning child will immediately start looking for answers on search servers, but he will not find exactly the same 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 problems, the student will have to understand the general principles of solving problems using graph theory. And in the future, the acquired knowledge 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. There was great interest in the site: judging by the visit counter, it was visited more than 150 times in the first week! Many guys tried to solve the problems, but they found them difficult. Even some parents with higher technical education were stumped by a number of problems, which suggests that graph theory is not even studied in all higher educational institutions. This means that the testing we prepared will be useful not only for schoolchildren, but also for adults!
2.2. Graph Theory in Designing a Classroom Alarm System
Currently, much attention is paid to the area of emergency personnel management systems in organizations, due to the fact that such systems play a significant role in organizing all employee activities.
Initially, warning and evacuation control systems were conceived to urgently inform workers, staff and guests about a fire in a building, providing information and broadcasting important information for the rapid and successful evacuation of people. Today, such systems can be observed not only within one organization or enterprise, but throughout our entire country, used to improve the safety of people.
It should be noted that most of the warning systems used are aimed at adults. But the most dangerous age is childhood. Children also need their own systems that allow them to quickly notify most of their peers about impending danger or a change in the situation.
Each child spends a significant part of his time at school: five to six days a week for several hours. Therefore, the creation of a child warning system would make it possible to organize each child to quickly and competently react to the changed situation.
For example, this system would be very useful when transmitting a message about danger, information about an urgent gathering or a change in the situation when they are in different parts of the school or even in the forest on vacation (Figure 2.2)
Figure 2.2. Our class on an excursion to the State Autonomous Institution "Regional Center for Pre-Conscription Training and Patriotic Education "Avanpost"
In this work, an attempt is made to create a Collective Notification System using the example of one class of an educational institution: MAOU Secondary School No. 89.
Since children must disseminate information themselves, they should use only all types of communication available to them - mobile communications. The entire roster of the class must be notified, so to analyze which children were ready to notify which of their friends, a class survey was conducted. The questionnaires initially set a limit: each child has time to call a maximum of four friends, and if there is time left, two more.
The survey showed a fairly high activity of the children: in total, 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), such a graph is labeled and weighted. The graph helps to 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 the graph of the RNS system.
On November 19, 2017, the designed SOC system was tested. Initially, we planned for the announcement to take place over three laps. For the first circle (start of 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). Then the information is transmitted to the second warning circle (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 spend 1.5-2 hours in training and do not look at the phone, others have a negative balance, so they cannot make calls.
Figure 2.3. Class alert system graph
Figure 2.4. SOK System Alert Circles
Therefore, in reality, our class was notified only 490 minutes in advance - that’s 8 hours 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 peak to another, so in any case, everyone will be notified!
Figure 2.6 shows a graph of class notification (number of people notified) versus time (in minutes).
Figure 2.6. Class notification schedule
To make it easier to monitor alertness, during the testing process children had to tell the Project authors their favorite subject, and they kept a protocol of when and who reported 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! This means that they may love graph theory just as much as we do.
Figure 2.7. Pie chart of favorite class items
2.3. Conclusions on the chapter.
We tested both hypotheses. The website we developed for testing Olympiad problems in graph theory helped establish that a number of Olympiad problems are simply impossible to solve without knowledge of graph theory, even for adult engineers. The first hypothesis was confirmed.
The second hypothesis also turned out to be correct. The designed and tested team notification system using the example of one class made it possible to notify an entire children's team in 8 hours and 10 minutes. By optimizing the graph, you can achieve faster results.
Conclusion.
We hope that after becoming familiar with graph theory and its many applications in various fields, schoolchildren will awaken an interest in graph theory, and they will continue to study this branch of mathematics on their own. The result of the study will be better 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 child warning system will increase the speed of transmission of urgent information, cover a large part of the children's team for which this system will be used, reduce the response time of children, and also ensure maximum safety for a children's group. All this points to the obvious advantages of implementing the designed system.
Bibliography
Beloborodova A.A. Development of spatial thinking using 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. HE. Kuzyakov. - Tyumen: TIU, 2017. - pp. 156-159.
Beloborodova A.A. You can't get lost with math! / A.A. Beloborodova // XVIII All-Russian children's scientific research competition. and creative works “First steps in science”: 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. Fairy tale story / For younger children. and Wednesday school age.- Kharkov: Publishing house - commerce. 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 / resp. editor A.N. Khalin. - Tyumen: TIU, 2016. - pp. 25-29.
Karnaukhova, A.A. Using graph theory in solving problems in economics / A.A. Karnaukhova, A.F. Dolgopolova // Materials 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-classics", 2007, 448 p.
Krause, M.V. Application of information technologies for designing a team warning 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. HE. Kuzyakov. - Tyumen: TIU, 2017. - pp. 153-156.
Course “Website Creation” of the School of Information Technologies “REAL-IT” http://it-schools.org/faculties/web/
The world of mathematics: in 40 volumes. T.11: Claudi Alsina. Metro maps and terron networks. Graph theory./Trans. from Spanish - M.: De Agostini, 2014. - 144 p.
Moskevich L.V. Educational Olympiad - one of the forms of extracurricular mathematics classes / L.V. Moskevich // Scientific and methodological electronic journal “Concept”. - 2015. - T. 6. - P. 166-170. - URL: http://e-koncept.ru/2015/65234.htm.
Memo to the population "Notifying the population in the event of a threat and emergency" http://47.mchs.gov.ru/document/1306125
Rumyantsev, V.O. Mathematical modeling of the gas transportation system using graph theory / V. O. Rumyantsev // Problems of geology and subsoil development: collection. scientific tr. / TPU. - Tomsk, 2017. - P. 340 - 342.
Website of the Ministry of Emergency Situations of the Russian Federation http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves
Leonard Euler is considered the founder of graph theory. In 1736, in one of his letters, he formulated and proposed a solution to the problem of the seven Königsberg bridges, which later became one of the classical problems of graph theory.
The first problems in graph theory were related to solving mathematical recreational problems and puzzles. Here is a retelling of an excerpt from Euler’s letter dated March 13, 1736: “I was given a problem about an island located in the city of Königsberg and surrounded by a river with 7 bridges across it. 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 in any way or not.” The Königsberg bridges can be schematically depicted as follows:
Euler's rule:
1. In a graph that does not have vertices of odd degrees, there is a traversal of all edges (and each edge is traversed exactly once) starting at any vertex of the graph.
2. In a graph that has two and only two vertices with odd degrees, there is a traversal that starts at one vertex with odd degree and ends at the other.
3. In a graph that has more than two vertices with odd degrees, such a traversal does not exist.
There is another type of problem related to traveling along graphs. We are talking about problems in which it is necessary to find a path passing through all vertices, and no more than once through each. A cycle that passes through each vertex once and only once is called a Hamiltonian line (after William Rowan Hamilton, the famous Irish mathematician of the last century who was the first to study such lines). Unfortunately, a general criterion has not yet been found with the help of which one could decide whether a given graph is Hamiltonian, and if so, then find all Hamiltonian lines on it.
Formulated in the mid-19th century. The four color problem also looks like an entertaining problem, but attempts to solve it have led to some graph studies that have theoretical and applied significance. The four-color problem is formulated as follows: “Can an area of any flat map be colored with four colors so that any two adjacent areas are colored with different colors?” The hypothesis that the answer is affirmative was formulated in the mid-19th century. In 1890, a weaker statement was proven, namely that any flat map can be colored in five colors. By associating any planar map with its dual planar graph, we obtain an equivalent formulation of the problem in terms of graphs: Is it true that the chromatic number of any planar graph is less than or equal to four? Numerous attempts to solve the problem influenced the development of a number of areas of graph theory. In 1976, a positive solution to the problem using a computer was announced.
Another old topological problem that has been particularly resistant to solution for a long time and has haunted the minds of puzzle lovers is known as the “electricity, gas and water supply problem.” In 1917, Henry E. Dudeney gave it this formulation. Gas, electricity and water must be installed in each of the three houses shown in the figure.
Graph theory. 1
The history of the emergence of graph theory. 1
Euler's rule. 1
Literature
1. Belov Graph Theory, Moscow, "Science", 1968.
2. New pedagogical and information technologies E.S. Polat , Moscow, "Akademia" 1999
3. Kuznetsov O.P., Adelson-Velsky G.M. Discrete mathematics for the engineer. – M.: Energoatomizdat, 1988.
4. Cook D., Baze G. Computer mathematics. – M.: Science, 1990.
5. Nefedov V.N., Osipova V.A. Discrete mathematics course. – M.: MAI Publishing House, 1992.
6. Ore O. Graph theory. – M.: Science, 1980.
7. Ismagilov R.S., Kalinkin A.V. Materials for practical classes in the course: Discrete Mathematics
What is the graph method?
The word "graph" in mathematics means a picture with several points drawn, some of which are connected by lines. First of all, it is worth saying that the counts that will be discussed have nothing to do with the aristocrats of bygone times. Our “graphs” are rooted in the Greek word “grapho,” which means “I write.” The same root is in the words “graph”, “biography”.
In mathematics graph definition is given as follows: a graph is a finite set of points, some of which are connected by lines. The points are called vertices of the graph, and the connecting lines are called edges.
A graph diagram consisting of "isolated" vertices is called zero graph. (Fig.2)
Graphs in which all possible edges are not constructed are called incomplete graphs. (Fig.3)
Graphs in which all possible edges are constructed are called complete graphs. (Fig.4)
A graph in which every vertex is connected to an edge of every other vertex is called complete.
Note that if a complete graph has n vertices, then the number of edges will be equal to
n(n-1)/2
Indeed, the number of edges in a complete graph with n vertices is defined as the number of unordered pairs made up of all n edge points of the graph, i.e., as the number of combinations of n elements of 2:
A graph that is not complete can be completed to be complete with the same vertices by adding the missing edges. For example, Figure 3 shows an incomplete graph with five vertices. In Figure 4, the edges that transform the graph into a complete graph are depicted in a different color; the collection of vertices of the graph with these edges is called the complement of the graph.
Degrees of vertices and counting the number of edges.
The number of edges leaving a vertex of the graph is called vertex degree. A vertex of a graph that has an odd degree is called odd, and even degree – even.
If the degrees of all vertices of a graph are equal, then the graph is called homogeneous. Thus, any complete graph is homogeneous.
Fig.5
Figure 5 shows a graph with five vertices. The degree of vertex A will be denoted by St.A.
In the figure: St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.
Let us formulate some regularities inherent in certain graphs.
Pattern 1.
The degrees of the vertices of a complete graph are the same, and each of them is 1 less than the number of vertices of this graph.
Proof:
This pattern is obvious after considering any complete graph. Each vertex is connected by an edge to every vertex except itself, i.e., from each vertex of a graph that has n vertices, n-1 edges emanate, which is what needed to be proved.
Pattern 2.
The sum of the degrees of the vertices of a graph is an even number equal to twice the number of edges of the graph.
This pattern is true not only for a complete graph, but also for any graph. Proof:
Indeed, each edge of the graph connects two vertices. This means that if we add the number of degrees of all vertices of the graph, we will get twice the number of edges 2R (R is the number of edges of the graph), since each edge was counted twice, which is what needed to be proved
The number of odd vertices in any graph is even. Proof:
Consider an arbitrary graph G. Let the number of vertices in this graph whose degree is 1 be equal to K1; the number of vertices whose degree is 2 is equal to K2; ...; the number of vertices whose degree is n is equal to Kn. Then the sum of the degrees of the vertices of this graph can be written as
K1 + 2K2 + ZK3 + ...+ nKn.
On the other hand: if the number of edges of the graph is R, then from Law 2 it is known that the sum of the degrees of all vertices of the graph is equal to 2R. Then we can write the equality
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
Let us select on the left side of the equality a sum equal to the number of odd vertices of the graph (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
The second bracket is an even number as the sum of even numbers. The resulting sum (2R) is an even number. Hence (K1 + K3 + K5 +...) is an even number.
Let us now consider problems solved using graphs:
Task. Class Championship . There are 6 participants in the table tennis class championship: Andrey, Boris, Victor, Galina, Dmitry and Elena. The championship is held on a round-robin basis - each participant plays each of the others once. To date, some games have already been played: Andrey played with Boris, Galina and Elena; Boris, as already mentioned, is with Andrei and also with Galina; Victor - with Galina, Dmitry and Elena; Galina with Andrey and Boris; Dmitry - with Victor and Elena - with Andrey and Victor. How many games have been played so far and how many are left?
Discussion. Let's depict these tasks in the form of a diagram. We will depict the participants as dots: Andrey - point A, Boris - point B, etc. If two participants have already played with each other, then we will connect the points representing them with segments. The result is the diagram shown in Figure 1.
Points A, B, C, D, D, E are the vertices of the graph, and the segments connecting them are the edges of the graph.
Note that the intersection points of the edges of the graph are not its vertices.
The number of games played so far is equal to the number of edges, i.e. 7.
To avoid confusion, the vertices of a graph are often depicted not as dots, but as small circles.
To find the number of games that need to be played, we will build another graph with the same vertices, but with edges we will connect those participants who have not yet played with each other (Fig. 2). This graph turned out to have 8 edges, which means there are 8 games left to play : Andrey - with Victor and Dmitry; Boris - With Victor, Dmitry and Elena, etc.
Let's try to build a graph for the situation described in the following problem:
Task . Who plays Lyapkin - Tyapkin? The school drama club decided to stage Gogol's The Inspector General. And then a heated argument broke out. It all started with Lyapkin - Tyapkin.
Lyapkin - I will be Tyapkin! – Gena stated decisively.
No, I will be Lyapkin - Tyapkin, Dima objected. - From early childhood I dreamed of bringing this image to life on stage.
Well, okay, I’ll give up this role if they let me play Khlestakov,” Gena showed generosity.
“...And for me - Osipa,” Dima did not yield to him in generosity.
“I want to be Strawberry or Mayor,” said Vova.
No, I will be the Mayor,” Alik and Borya shouted in unison. - Or Khlestakov, -
Will it be possible to distribute the roles so that the performers are satisfied?
Discussion.
Let's depict the young actors with circles in the top row: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima, and the roles they are going to play - with circles in the second row (1 - Lyapkin - Tyapkin, 2 - Khlestakov, 3 – Osip, 4 – Strawberry, 5 – Mayor). Then we will draw segments from each participant, i.e. ribs, to the roles he would like to play. We will get a graph with ten vertices and ten edges (Fig. 3)
To solve the problem, you need to select five edges out of ten that do not have common vertices. It's easy to do. It is enough to note that one edge leads to vertices 3 and 4, from vertices D and B, respectively. This means that Osip (top 3) should be played by Dima (who else?), and Zemlyanichka by Vova. Vertex 1 - Lyapkin - Tyapkin - is connected by edges to G and D. Edge 1 - D gives up, since Dima is already busy, 1 - G remains, Lyapkina - Tyapkina should be played by Gena. It remains to connect vertices A and B with vertices 2 and 5, corresponding to the roles of Khlestakov and Gorodnichy. This can be done in two ways: either select edge A -5 and B - 2, or edge A -2 and B -5. In the first case, Alik will play the Mayor, and Borya will play Khlestakov, in the second case, vice versa. As the graph shows, the problem has no other solutions.
The same graph will be obtained when solving the following problem:
Task. Grumpy neighbors. The inhabitants of five houses quarreled with each other and, in order not to meet at the wells, decided to divide them (the wells) so that the owner of each house would go to “his” well along “his” path. Will they be able to do this?
The question arises:were graphs really needed in the problems discussed? Isn't it possible to arrive at a solution through purely logical means? Yes, you can. But the graphs made the conditions clearer, simplified the solution and revealed the similarity of the problems, turning two problems into one, and this is not so little. Now imagine problems whose graphs have 100 or more vertices. But it is precisely such problems that modern engineers and economists have to solve. You can't do without graphs here.
III. Euler graphs.
Graph theory is a relatively young science: in Newton’s time such a science did not yet exist, although “family trees”, which are varieties of graphs, were in use. The first work on graph theory belongs to Leonhard Euler, and it appeared in 1736 in the publications of the St. Petersburg Academy of Sciences. This work began with consideration of the following problem:
A) Problem about the Königsberg bridges.
The city of Koenigsberg (now Kaliningrad) is located on the banks and two islands of the Pregel River (Pregoli). The various parts of the city were connected by seven bridges, as shown in the picture. On Sundays, citizens take walks around the city. Is it possible to choose a route such that you cross each bridge once and only once and then return to the starting point?
Before considering the solution to this problem, we introduce the concept “ Euler graphs.
Let's try to circle the graph shown in Fig. 4 with one stroke, that is, without lifting the pencil from the sheet of paper and without passing along the same part of the line more than once.
This figure, so simple in appearance, turns out to have an interesting feature. If we start moving from vertex B, then we will definitely succeed. What will happen if we start moving from vertex A? It is easy to see that in this case we will not be able to trace the line: we will always have untraversed edges, which are no longer possible to reach. 
In Fig. Figure 5 shows a graph that you probably know how to draw with one stroke. This is a star. It turns out that, although it looks much more complex than the previous graph, you can trace it by starting from any vertex.
The graphs drawn in Fig. 6 can also be drawn with one stroke of the pen.
Now try to draw with one stroke graph shown in Fig. 7
You failed to do this! Why? Can't find the vertex you're looking for? No! That's not the point. This graph generally cannot be drawn with one stroke of the pen.
Let us carry out reasoning that will convince us of this. Consider node A. Three vertices emerge from it. Let's start drawing the graph from this vertex. To go along each of these edges, we must exit vertex A along one of them, at some point we must return to it along the second and exit along the third. But we won’t be able to enter again! This means that if we start drawing from vertex A, we will not be able to finish there.
Let us now assume that vertex A is not the beginning. Then, in the process of drawing, we must enter it along one of the edges, exit along the other and return again along the third. And since we cannot get out of it, then peak A in this case must be the end.
So, vertex A must be either the beginning or the end node of the drawing.
But the same can be said about the other three vertices of our graph. But the starting vertex of drawing can only be one vertex, and the final vertex can also be only one vertex! This means that it is impossible to draw this graph with one stroke.
A graph that can be drawn without lifting the pencil from the paper is called Eulerian (Fig. 6).
These graphs are named after the scientist Leonhard Euler.
Pattern 1. (follows from the theorem we considered).
It is impossible to draw a graph with an odd number of odd vertices.
Pattern 2.
If all the vertices of the graph are even, then you can draw this graph without lifting your pencil from the paper (“with one stroke”), moving along each edge only once. The movement can start from any vertex and end at the same vertex.
Pattern 3.
A graph with only two odd vertices can be drawn without lifting the pencil from the paper, and the movement must begin at one of these odd vertices and end at the second of them.
Pattern 4.
A graph with more than two odd vertices cannot be drawn with “one stroke.”
A figure (graph) that can be drawn without lifting the pencil from the paper is called unicursal.
The graph is called coherent, if any two of its vertices can be connected by a path, that is, a sequence of edges, each of which begins at the end of the previous one.
The graph is called incoherent, if this condition is not met.
Fig.7 
Fig.8
Figure 7 obviously shows a disconnected graph. If, for example, in the figure you draw an edge between vertices D and E, the graph will become connected. (Fig.8)
In graph theory, such an edge (after removing which the graph from a connected one turns into a disconnected one) is called bridge.
Examples of bridges in Figure 7 could be the edges DE, A3, VZH, etc., each of which would connect the vertices of “isolated” parts of the graph. (Fig. 8)
A disconnected graph consists of several “pieces”. These "pieces" are called connectivity components graph. Each connected component is, of course, a connected graph. Note that a connected graph has one connected component.
THEOREM.
A graph is Eulerian if and only if it is connected and has at most two odd vertices.
Proof:
Drawing the graph for each vertex, with the exception of the initial and final ones, we will enter the same number of times as we exit it. Therefore, the degrees of all vertices must be even, except for two, which means that an Eulerian graph has at most two odd vertices.
Let us now return to the problem of the Königsberg bridges.
Discussion of the problem . Let's denote the different parts of the city with the letters A, B, C, D, and the bridges with the letters a, b, c, d, e, f, g - bridges connecting the corresponding parts of the city. In this problem, there are only crossings over bridges: crossing any bridge, we always end up from one part of the city to another. And, conversely, crossing from one part of the city to another, we will certainly cross a bridge. Therefore, let us depict the city plan in the form of a graph, the vertices of which A, B, C, D (Fig. 8) depict individual parts of the city, and the edges a, b, c, d, e, f, g are bridges connecting the corresponding parts of the city . It is often more convenient to depict edges not as straight segments, but as curvilinear ones - “arcs”.
If there were a route that satisfied the conditions of the problem, then there would be a closed continuous traversal of this graph, passing once along each edge. In other words, this graph should be drawn with one stroke. But this is impossible - no matter which vertex we choose as the initial one, we will have to go through the remaining vertices, and at the same time, each “incoming” edge (the bridge along which we entered this part of the city) will correspond to an “outgoing” edge, the bridge by which we and then use it to leave this part of the city): the number of edges entering each vertex will be equal to the number of edges leaving it, i.e. the total number of edges converging at each vertex must be even. Our graph does not satisfy this condition, and therefore the required route does not exist.
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.
Loading...