Applied significance of graph theory research paper. Project research work "graph theory"
Municipal secondary education state-financed organization -
Secondary school No. 51
Orenburg.
Project on:
mathematic teacher
Egorcheva Victoria Andreevna
2017
Hypothesis : If graph theory is brought closer to practice, then the most beneficial results can be obtained.
Target: Get acquainted with the concept of graphs and learn how to apply them in solving various problems.
Tasks:
1) Expand knowledge about methods of constructing graphs.
2) Identify types of problems whose solution requires the use of graph theory.
3) Explore the use of graphs in mathematics.
“Euler calculated, without any visible effort, how a person breathes or how an eagle soars above the earth.”
Dominic Arago.
I. Introduction. p.
II . Main part.
1. The concept of a graph. Problem about the Königsberg bridges. p.
2. Properties of graphs. p.
3. Problems using graph theory. p.
Sh. Conclusion.
The meaning of graphs. p.
IV. Bibliography. p.
I . INTRODUCTION
Graph theory is a relatively young science. “Graphs” has the root of the Greek word “grapho,” which means “I write.” The same root is in the words “graph”, “biography”.
In my work, I look at how graph theory is used in various areas of people's lives. Every math teacher and almost every student knows how difficult it is to solve geometric problems, as well as algebra word problems. Having explored the possibility of using graph theory in a school mathematics course, I came to the conclusion that this theory greatly simplifies understanding and solving problems.
II . MAIN PART.
1. The concept of a graph.
The first work on graph theory belongs to Leonhard Euler. It appeared in 1736 in publications of the St. Petersburg Academy of Sciences and began with a consideration of the problem of the Königsberg bridges.
You probably know that there is such a city as Kaliningrad; it used to be called Koenigsberg. The Pregolya River flows through the city. It is divided into two branches and goes around the island. In the 17th century there were seven bridges in the city, arranged as shown in the picture.
They say that one day a city resident asked his friend if he could walk across all the bridges so as to visit each of them only once and return to the place where the walk began. Many townspeople became interested in this problem, but no one could come up with a solution. This issue has attracted the attention of scientists from many countries. The famous mathematician Leonhard Euler managed to solve the problem. Leonhard Euler, a native of Basel, was born on April 15, 1707. Euler's scientific achievements are enormous. He influenced the development of almost all branches of mathematics and mechanics both in the field basic research, and in their applications. Leonhard Euler not only solved this specific problem, but also came up with a general method for solving these problems. Euler did the following: he “compressed” the land into points, and “stretched” the bridges into lines. The result is the figure shown in the figure.
Such a figure, consisting of points and lines connecting these points, is calledcount. Points A, B, C, D are called the vertices of the graph, and the lines that connect the vertices are called the edges of the graph. In a drawing of vertices B, C, D 3 ribs come out, and from the top A - 5 ribs. Vertices from which an odd number of edges emerge are calledodd vertices, and vertices from which an even number of edges emerge areeven.
2. Properties of the graph.
While solving the problem about the Königsberg bridges, Euler established, in particular, the properties of the graph:
1. If all the vertices of the graph are even, then you can draw a graph with one stroke (that is, without lifting the pencil from the paper and without drawing twice along the same line). In this case, the movement can start from any vertex and end at the same vertex.
2. A graph with two odd vertices can also be drawn with one stroke. The movement must begin from any odd vertex and end at another odd vertex.
3. A graph with more than two odd vertices cannot be drawn with one stroke.
4.The number of odd vertices in a graph is always even.
5. If a graph has odd vertices, then the smallest number of strokes that can be used to draw the graph will be equal to half the number of odd vertices of this graph.
For example, if a figure has four odd numbers, then it can be drawn with at least two strokes.
In the problem of the seven bridges of Königsberg, all four vertices of the corresponding graph are odd, i.e. You cannot cross all the bridges once and end the journey where it started.
3. Solving problems using graphs.
1. Tasks on drawing figures with one stroke.
Attempting to draw each of the following shapes with one stroke of the pen will result in different results.
If there are no odd points in the figure, then it can always be drawn with one stroke of the pen, no matter where you start drawing. These are figures 1 and 5.
If a figure has only one pair of odd points, then such a figure can be drawn with one stroke, starting drawing at one of the odd points (it doesn’t matter which). It is easy to understand that the drawing should end at the second odd point. These are figures 2, 3, 6. In figure 6, for example, drawing must begin either from point A or from point B.
If a figure has more than one pair of odd points, then it cannot be drawn with one stroke at all. These are figures 4 and 7, containing two pairs of odd points. What has been said is enough to accurately recognize which figures cannot be drawn with one stroke and which ones can be drawn, as well as from what point the drawing should begin.
I propose to draw the following figures in one stroke.
2. Solving logical problems.
TASK No. 1.
There are 6 participants in the table tennis class championship: Andrey, Boris, Victor, Galina, Dmitry and Elena. The championship is held in a round robin system - each participant plays each of the others once. To date, some games have already been played: Andrey played with Boris, Galina, Elena; Boris - with Andrey, Galina; Victor - with Galina, Dmitry, Elena; Galina - with Andrey, Victor and Boris. How many games have been played so far and how many are left?
SOLUTION:
Let's build a graph as shown in the figure.
7 games played.
In this figure, the graph has 8 edges, so there are 8 games left to play.
TASK #2
In the courtyard, which is surrounded by a high fence, there are three houses: red, yellow and blue. The fence has three gates: red, yellow and blue. From the red house, draw a path to the red gate, from the yellow house to the yellow gate, from the blue house to the blue one so that these paths do not intersect.
SOLUTION:
The solution to the problem is shown in the figure.
3. Solving word problems.
To solve problems using the graph method, you need to know the following algorithm:
1.What process are we talking about in the problem?2.What quantities characterize this process?3.What is the relationship between these quantities?4.How many different processes are described in the problem?5.Is there a connection between the elements?
Answering these questions, we analyze the condition of the problem and write it down schematically.
For example . The bus traveled for 2 hours at a speed of 45 km/h and for 3 hours at a speed of 60 km/h. How far did the bus travel during these 5 hours?
S 
¹=90 km V ¹=45 km/h t ¹=2h
S=VT
S ²=180 km V ²=60 km/h t ²=3 h
S ¹ + S ² = 90 + 180
Solution:
1)45x 2 = 90 (km) - the bus traveled in 2 hours.
2)60x 3 = 180 (km) - the bus traveled in 3 hours.
3)90 + 180 = 270 (km) - the bus traveled in 5 hours.
Answer: 270 km.
III . CONCLUSION.
As a result of working on the project, I learned that Leonhard Euler was the founder of graph theory and solved problems using graph theory. I concluded for myself that graph theory is used in various areas of modern mathematics and its numerous applications. There is no doubt about the usefulness of introducing us students to the basic concepts of graph theory. Solving many mathematical problems becomes easier if you can use graphs. Data presentation V the form of a graph gives them clarity. Many proofs are also simplified and become more convincing if you use graphs. This especially applies to such areas of mathematics as mathematical logic and combinatorics.
Thus, the study of this topic has great general educational, general cultural and general mathematical significance. IN Everyday life Graphic illustrations, geometric representations and other techniques and methods of visualization are increasingly used. For this purpose, it is useful to introduce the study of elements of graph theory in primary and secondary schools, at least in extracurricular activities, since this topic is not included in the mathematics curriculum.
V . BIBLIOGRAPHY:
2008
Review.
The project on the theme “Graphs around us” was completed by Nikita Zaytsev, a student of class 7 “A” at Municipal Educational Institution No. 3, Krasny Kut.
A distinctive feature of Nikita Zaitsev’s work is its relevance, practical orientation, depth of coverage of the topic, and the possibility of using it in the future.
The work is creative, in the form information project. The student chose this topic to show the relationship of graph theory with practice using the example of a school bus route, to show that graph theory is used in various areas of modern mathematics and its numerous applications, especially in economics, mathematical logic, and combinatorics. He showed that solving problems is greatly simplified if it is possible to use graphs; presenting data in the form of a graph gives them clarity; many proofs are also simplified and become convincing.
The work addresses issues such as:
1. The concept of a graph. Problem about the Königsberg bridges.
2. Properties of graphs.
3. Problems using graph theory.
4. The meaning of graphs.
5. School bus route option.
When performing his work, N. Zaitsev used:
1. Alkhova Z.N., Makeeva A.V. " Extracurricular activities mathematics".
2. Magazine “Mathematics at school”. Appendix “First of September” No. 13
2008
3. Ya.I.Perelman “Entertaining tasks and experiments.” - Moscow: Education, 2000.
The work was done competently, the material meets the requirements of this topic, the corresponding drawings are attached.
Kuchin Anatoly Nikolaevich
Project Manager:
Kuklina Tatyana Ivanovna
Institution:
MBOU "Basic secondary school" Troitsko-Pechorsk Rep. Komi
In his research work in mathematics "In the world of graphs" I will try to find out the features of using graph theory in solving problems and in practical activities. The result of my mathematics research work on graphs will be my family tree.
In my research work in mathematics, I plan to get acquainted with the history of graph theory, study the basic concepts and types of graphs, and consider methods for solving problems using graphs.
Also in research project in mathematics about graphs, I will show the application of graph theory in various areas of human activity.
Introduction
Chapter 1. Getting to know graphs
1.1. History of graphs.
1.2. Types of graphs
Chapter 2. Possibilities of applying graph theory in various areas of everyday life
2.1. Application of graphs in various areas of people's lives
2.2. Application of graphs in problem solving
2.3. Family tree is one of the ways to apply graph theory
2.4. Description of the research and compilation of the family tree of my family
Conclusion
References
Applications
“In mathematics, it is not the formulas that should be remembered,
but the process of thinking."
E.I. Ignatyeva
Introduction
Counts are everywhere! In my research paper on mathematics on the topic “In the world of graphs” we will talk about graphs that have nothing to do with the aristocrats of the past. "" have the root of the Greek word " grapho", What means " writing" The same root in the words " schedule», « biography», « holography».
For the first time with the concept “ graph” I met while solving math olympiad problems. Difficulties in solving these problems were explained by the absence of this topic in the compulsory school curriculum. The problem that arose was the main reason for choosing the topic of this research work. I decided to study in detail everything related to graphs. How widely the graph method is used and how important it is in people's lives.
There is even a special section in mathematics, which is called: “ Graph theory" Graph theory is part of both topology, so combinatorics. The fact that this is a topological theory follows from the independence of the properties of the graph from the location of the vertices and the type of lines connecting them.
And the convenience of formulating combinatorial problems in terms of graphs has led to the fact that graph theory has become one of the most powerful tools of combinatorics. When solving logical problems, it is usually quite difficult to keep in memory numerous facts given in the condition, establish connections between them, express hypotheses, draw particular conclusions and use them.
Find out the features of using graph theory in solving problems and in practical activities.
Object of study is mathematical graphs.
Subject of research are graphs as a way to solve a number of practical problems.
Hypothesis: If the graph method is so important, then it will certainly be widely used in various fields of science and human activity.
To achieve this goal, I put forward the following tasks:
1. get acquainted with the history of graph theory;
2. study the basic concepts of graph theory and types of graphs;
3. consider ways to solve problems using graphs;
4. show the application of graph theory in various areas of human life;
5. create a family tree of my family.
Methods: observation, search, selection, analysis, research.
Study:
1. Internet resources and printed publications were studied;
2. areas of science and human activity in which the graph method is used are outlined;
3. solution of problems using graph theory is considered;
4. I studied the method of compiling the family tree of my family.
Relevance and novelty.
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. Graph theory is used in various areas of modern mathematics and its numerous applications, especially in economics, technology, and management. Solving many mathematical problems becomes easier if you can use graphs. Presenting data in the form of a graph makes it clearer and simpler. Many mathematical proofs are also simplified and become more convincing if graphs are used.
To make sure of this, the director and I proposed to students in grades 5-9, participants in school and municipal tours All-Russian Olympiad schoolchildren, 4 problems in solving which you can apply graph theory ( Annex 1).
The results of solving the problems are as follows:
A total of 15 students (5th grade - 3 students, 6th grade - 2 students, 7th grade - 3 students, 8th grade - 3 students, 9th grade - 4 students) applied graph theory in 1 problem - 1, in 2 problem - 0, in Problem 3 – 6, problem 4 – 4 students.
Practical significance research is that the results will undoubtedly be of interest to many people. Haven't any of you tried to build your family tree? How to do this correctly?
It turns out that they can be easily solved using graphs.
Scientific society students
"Search"
40 Open regional Scientific Conference students.
Mathematics section.
Scientific work on the topic:
"Counts" in my pedigree
Completed by: Victoria Loburets
7th grade studentMunicipal educational institution "Kulomzinskaya secondary school"
Supervisor:
Lysenko Olga Grigorievna
mathematic teacher
Municipal educational institution "Kulomzinskaya secondary school"
Omsk - 2008
Relevance and novelty
Goal and tasks
II. MAIN PART
1. The concept of graphs
2.Properties of graphs
3.Use of graphs
III.Practical part
IV.Conclusion
V.Literature
VI.Appendix
CONTENT
Introduction………………………………………………………………………………..…….3
P.1.1. Relevance and novelty……………………………………………..4
P.1.2.Goals and objectives………………………………………………………4
Chapter I. Theoretical part…………………………………….……….5
P.2.1. The concept of graphs……………………………………………………..5
Chapter II. Practical part………………………………………………………..11
P.2.1. “Counts” in my pedigree……………………………………..11
P.2.2. Solving logical problems using the graph method………………………..11
Conclusion…..………………………………………………………………………………...17
Literature……..……………………………………………………………..18
Applications…………………………………………………………………………………..19
Introduction
1.Relevance and novelty
Graph theory is used in various areas of modern mathematics and its numerous applications, especially in economics, technology, and management. Graph theory is an important section of discrete mathematics, the practical role of which has increased due to the development of various automated control systems and discrete computing technology; in theoretical terms, in addition to connections with combinatorics and geometry, there have been shifts at the intersection of graph theory with algebra and mathematical logic.
Historically, graph theory originated from puzzle solving more than two hundred years ago. For a very long time she was away from the main directions of scientific research. Graph theory received an impetus for development at the turn of the 19th and 20th centuries, when the number of works in the field of topography and combinatorics, with which it is closely related, increased sharply. The earliest mention of graphs is found in the work of L. Euler (1736). In the middle of the 19th century, electrical engineer G. Kirchhoff developed the theory of trees to study electrical circuits, and mathematician A. Cayley, in connection with the description of the structure of hydrocarbons, solved enumeration problems for three types of trees. Graph theory finally took shape as a mathematical discipline in 1936. after the publication of D. Koenig’s monograph “The Theory of Finite and Infinite Graphs”.
Recently, graphs and related research methods have organically permeated the different levels almost all modern mathematics. Graph theory finds many applications in various fields of mathematics: algebra, geometry, topology, combinatorics, coding theory, operations research, and in physics, chemistry, linguistics, economics, psychology and other sciences.
Solving many mathematical problems becomes easier if you can use graphs. Presenting data in the form of a graph makes it clearer and simpler.
The novelty of this work is the proof of the effectiveness of the graph method in solving logical problems.
The main goal of school mathematics education is to develop the mental abilities of students. We need a transition from information and explanatory technology to activity-development technology aimed at development personal qualities every schoolchild. Not only the acquired knowledge should become important, but also the methods of assimilation and processing. educational information, development cognitive activity and the student’s creative potential. Most schoolchildren are unlikely to use their acquired knowledge in mathematics in everyday life, although many of them will graduate from technical universities. A person quickly forgets the knowledge that he does not constantly use, but logical development remains with him forever. It is this topical topic of student personality development that my work is dedicated to.
Object research is the process of teaching students the graph method.
Hypothesis: according to our assumption, solving logical problems by students using the graph method can contribute to the formation and development of logical thinking.
Based on the hypothesis, the following goals and objectives of the study have been put forward.
2. Goal and objectives.
Target: use the graph method to solve logical problems, thereby promoting the development of logical thinking, consider solving problems using the concept of “Graph”, check the implementation of “Graphs” on genealogies.
Tasks:
1) Study popular scientific literature on this issue.
2) Investigate the implementation of “Graphs” to clarify family relationships.
3) Analyze the results of the experiments.
4) Study of the “graph” method as a method for solving logical problems.
Chapter I. Theoretical part
P.2.1. Concept of graphs
The word "graph" in mathematics means a picture with several points drawn, some of which are connected by lines. Mathematical graphs with the noble title "count" are connected by a common origin from the Latin word "graphio" - I write. Typical graphs are airline diagrams, which are often posted at airports, subway diagrams, and on geographic maps - an image railways(Fig. 1). The selected points of the graph are called its vertices, and the lines connecting them are called edges.
Uses counts and nobility. Figure 2 shows part of the family tree of a famous noble family. Here its vertices are the members of this genus, and the segments connecting them are the relationships of kinship leading from parents to children.
The word “tree” in graph theory means a graph in which there are no cycles, that is, in which it is impossible to go from a certain vertex along several different edges and return to the same vertex. A family tree will also be a tree in the sense of graph theory if there were no marriages between relatives in this family.
It is not difficult to understand that a tree graph can always be depicted so that its edges do not intersect. Graphs formed by the vertices and edges of convex polyhedra have the same property. Figure 3 shows graphs corresponding to five regular polyhedra. In the graph corresponding to a tetrahedron, all four vertices are connected in pairs by edges.
Consider a graph with five vertices connected in pairs to each other (Fig. 4). Here the edges of the graph intersect. It is impossible to depict him in such a way that there are no intersections, just as it is impossible to fulfill the intentions of the three people described by Lewis Carroll. They lived in three houses, not far from them there were three wells: one with water, another with oil, and the third with jam, and they walked to them along the paths shown in Figure 5. One day these people quarreled and decided to draw paths from their houses to wells so that these paths do not intersect. Figure 6 shows another attempt to build such trails.
The graphs depicted in Figures 4 and 5 turn out to play a decisive role in determining for each graph whether it is planar, that is, whether it can be drawn on a plane without intersecting its edges. Polish mathematician G. Kuratowski and academician
L.S. Pontryagin independently proved that if the graph is not planar, then at least one of the graphs shown in Figures 4 and 5 “sits” in it, that is, a “complete five-vertex” or a “houses-wells” graph. .
Graphs are block diagrams of computer programs, network construction graphs, where vertices are events indicating the completion of work on a certain area, and the edges connecting these vertices are work that can begin after one event has occurred and must be completed to complete the next.
If the edges of a graph have arrows indicating the direction of the edges, then such a graph is called directed.
The arrow from one job to another in the graph shown in Fig. 7 means the sequence of work. You can’t start installing walls without finishing building the foundation; in order to start finishing, you need to have water on the floors, etc.
Fig.7.
Numbers are indicated near the vertices of the graph - the duration in days of the corresponding work. Now we can find out the shortest possible construction duration. To do this, from all the paths along the graph in the direction of the arrows, you need to choose the path whose sum of numbers at the vertices is the largest. It is called the critical path (in Fig. 7 it is highlighted in brown). In our case we get 170 days. And if you reduce the time for laying the electrical network from 40 to 10 days, then the construction time will also be reduced by 30 days? No, in this case the critical path will not pass through this vertex, but through the vertices corresponding to the construction of the pit, laying the foundation, etc. And total time construction will be 160 days, i.e. the period will be reduced by only 10 days.
Figure 8 shows a map of roads between the villages M, A, B, C, 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 (below) will help you do this, where you can easily see possible routes. Peak M at the top is the beginning of the routes. You can start moving from it with four different ways: in A, in B, in C, in D. After visiting one of the villages, there are three possibilities for continuing the route, then two, then the road to the last village and again to M. A total of 4 × 3 × 2 × 1 = 24 ways.
Let's place numbers along the edges of the graph indicating the distances between villages, and at the end of each route we'll write the sum of these distances along the route. Of the 24 numbers obtained, the smallest are two numbers of 28 km, corresponding routes M-V-B-A-G-M and M-G-A-B-V-M. This is the same path, but traveled in different directions. Note that the graph in Fig. 8 can also be made directional by indicating the direction from top to bottom on each of the edges, which would correspond to the direction of movement of the postman. Similar problems often arise when finding the best options for distributing goods to stores and building materials to construction sites.
Graphs are often used to solve logical problems involving enumeration of options. For example, consider the following problem. 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 each moment can be described by three numbers, where A is the number of liters of water in the bucket, B is in a large pan, C is in a smaller one. At the initial moment, the situation was described by a triple of numbers (8, 0, 0), from which we can go to one of two situations: (3, 5, 0), if we fill a large pan with water, or (5, 0, 3), if fill the smaller pan. As a result, we get two solutions: one in 7 moves, the other in 8 moves.
In a similar way, you can create a graph of any positional game: chess, checkers, tic-tac-toe, where the positions will become vertices, and the directed segments between them will mean that in one move you can move from one position to another, in the direction of the arrow. However, for chess and checkers such a graph will be very large, since the various positions in these games number in the millions. But for the game “tic-tac-toe” on a 3x3 board, drawing the corresponding graph is not so difficult, although it will contain several tens (but not millions) of vertices. In terms of graphs, the problem of appointment to positions can be easily formulated and solved. Namely: if there are several vacant positions and a group of people willing to fill them, and each of the applicants is qualified for several positions, then under what conditions will each of the applicants be able to get a job in one of their specialties?
The properties of graphs do not depend on whether the vertices are connected by segments or curved lines. This makes it possible to study their properties using one of the young sciences - topology, although the problems of graph theory themselves are typical problems of combinatorics.
Chapter II. Practical part.
P.2.1. "Counts" in my pedigree.
Working methods:
Comparison and analysis of experimental results.
Working method:
The following were selected for research:
A) My family’s pedigree, data archives, birth certificates.
B) Pedigree of the Golitsyn princes, data archives.
I conducted research, put the research results into diagrams and analyzed them.
Method 1.
Goal: check the implementation of the “Counts” on your pedigree.
Results: Scheme 1 (see Appendix 1).
Method 2.
Goal: check the implementation of the “Counts” on the genealogy of the Golitsyn princes.
Result: scheme 2 (see Appendix 2).
Conclusion: I noticed that the pedigree is a typical graph.
P. 2.2. Solving logical problems using the graph method
During all the years of studying at school, we solve a lot of various problems, including logical ones: entertaining problems, puzzles, anagrams, rebuses, etc. To successfully solve problems of this type, you need to be able to identify them general signs, notice patterns, put forward hypotheses, test them, build chains of reasoning, draw conclusions. Logical problems differ from ordinary ones in that they do not require calculations, but are solved using reasoning. We can say that a logical task is special information that not only needs to be processed in accordance with a given condition, but you also want to do it. Logic helps to assimilate knowledge consciously, with understanding, i.e. not formal; creates the possibility of better mutual understanding. Logic is the art of reasoning, the ability to draw correct conclusions. This is not always easy, because very often the necessary information is “disguised”, presented implicitly, and you need to be able to extract it. As you know, vision gives birth to thinking. A problem arises: how to establish logical connections between disparate facts and how to formulate them into a single whole. The method of graph diagrams allows you to see the progress of the proof and solution of problems, which makes the proof more visual and allows you to briefly and accurately present the proofs of theorems and solutions to problems.
Example 1.1. 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?
Solution. 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 G1 (Fig. 1). 
Fig.1
Next, we complete the graph according to the following rule: since there can be exactly one pencil in the box, then one solid line and three dotted ones should come out of each point. The result is a graph G2 that gives a solution to the problem.
Example 1.2. 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?
Solution. Let's construct a graph of the relationship specified in the problem statement. To do this, first of all, we select the set of surnames M and the set of hair colors K, the elements of which will be denoted by dots. Let's call the points of the set M letters B, H, R(Belokurov, Chernov and Ryzhov); points of the second set – b, br, r(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, therefore, first the graph shown in Figure 2 should appear.
Fig.2 
From the conditions of the problem it follows that for each point from the set M, there is one and only one point from the sets K, which corresponds to the first one and, conversely, for each point from the set K there corresponds one and only one point from the set M. The problem boils down to: to find this only possible correspondence between the elements of the sets M and K, that is, to find 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 2 is supplemented with solid lines connecting the points B And R, R And br(Fig. 3).
Fig.3 
Next, it remains to connect the point with a solid line H and period b, since the point H connected to a point br dashed line and dot R is already “busy” (Fig. 4).
Rice. 4 
Thus, in the graph of this figure we automatically read the answer: Belokurov is red-haired, Chernov is blond, Ryzhov is brunette.
In the following problem, the use of graphs helps to detect the presence of two solutions.
Example 1.3. Masha, Lida, Zhenya and Katya can play different instruments (cello, piano, guitar and violin), but each only plays one. They speak different foreign languages (English, French, German and Spanish), but each only one. It is known that:
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. the girl who speaks German does not play the cello;
5. Zhenya knows French, but does not play the violin.
Who plays which instrument and which one? foreign language knows?
Solution. The problem conditions correspond to the graph shown in Figure 5.
Rice. 5 
Let us draw sequentially the following solid segments: KS, VZH, VF, AK (Fig. 6).
Rice. 6 
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.
In some cases, solving combinatorial problems can be difficult. You can make the search process easier by learning to use search tools such as tables and graphs. They allow you to dissect the course of reasoning and clearly carry out a search without missing any opportunities.
First, as the simplest means of organizing the search, you need to get acquainted with tables.
For example, consider this task:
There are two vessels with a capacity of 3L and 5L. How to use these vessels to pour 4 liters of water from a tap?
Let's start from the end. How can the result be 4L? – From a 5-liter vessel, pour 1 liter. How to do it? – You need to have exactly 2 liters in a 3-liter vessel. How to get them? – Pour 3 liters from a 5-liter vessel. Now let's write down the solution to the problem first in the form of a table.
The search for a solution can be started with the action 3+1, which would lead to the solution written in the following table.
From the numbers 3 and 5 you can create expressions that have the value 4:
5-3+5-3=4 and 3+3-5+3=4
It is easy to verify that the resulting expressions correspond to the solutions found above.
The second organizational tool that can be used when solving combinatorial problems is graphs.
I will give an example of a solution using a graph tree to solve a combinatorial problem.
For example, you need to solve task:“One day five friends met. Everyone greeted each other and shook hands. How many handshakes were done?
First, it becomes clear how each person should be designated. Considering different offers, come to the conclusion that it is faster and more convenient to depict people with dots. The dots need to be placed approximately in a circle, drawn with a colored pencil so that the notes are clear and visual. From two points towards each other, draw lines - “hands”, which meet to form one line. This is how they come to the symbolic image of a handshake. First, all the handshakes of one person are compiled (the point is connected by lines to all the others). Then they move on to another person. The lines drawn help to see who he has already said hello to and who he has not. The missing handshakes are drawn up (it is better to draw these lines in a different color, since later it will be better to calculate total number handshakes). And they do this until everyone says hello to each other. Using the graph received, count the number of handshakes (there are 10 in total).
Next task:
“How many two-digit numbers can you make using the numbers 1,2,3,4?”
Solution. Number 12: you need to show that it starts with the number 1 and ends with the number 2. A loop appears when designating, for example, the number 11: the arrow must start and end on the same number. Having discovered these symbols (dots, lines, arrows, loops) in the first problems, I began to use them in solving various problems, creating graphs of one type or another (Figure 2).
answer: 16 numbers.
Let me give some examples:
1
.Two Russian players, two German and two American players reached the finals of the checkers tournament. How many games will there be in the final if everyone plays everyone else once and representatives of the same country do not play each other? (Fig. 3.).
n
N 
In the final, 4x6 = 24 games will be played.
2. There were four types of sweets in the vase. Each child took two candies. And everyone had different sets of candies. How many children could there be? (graph in Fig. 4).
From this graph it becomes clear that there may be 6 different sets of sweets, and therefore there could be 6 children.
Conclusion: Graph problems have a number of advantages that allow them to be used to develop reasoning and improve the logical thinking of children, from kindergarten to high school. high school. The language of the graphs is simple, clear and visual. Graph problems can be presented in an entertaining, playful form. On the other hand, graph problems are more difficult to formalize than, for example, school tasks in algebra, solving them often does not require deep knowledge, but requires the use of ingenuity.
With their help, you can provide students with new knowledge that will make it easier for them to study computer science in the future; increase the logical and mental development of schoolchildren; accustom them to independent work; develop their imagination and improve the culture of communication.
When solving combinatorial problems, a close connection between thinking and practical actions is maintained, a gradual transition to actions in the mind is ensured, and contributes to the development of the quality of thinking, such as variability.
CONCLUSION
While doing this work, I studied one of the most interesting issues in graph theory, I looked at mathematical graphs, their areas of application, and solved several problems using graphs. I learned to use “graphs” to clarify family relationships. I studied the graph method as one of the methods for solving logical problems.
Graph theory is not studied in the school course, but problems in discrete mathematics are encountered quite often at various mathematical Olympiads and competitions. Graphs are widely used in mathematics, technology, economics, and management. Knowledge of the basics of graph theory is necessary in various areas related to production and business management (for example, network construction schedules, mail delivery schedules), and having become acquainted with the elements of graph theory, I hope that I will be able to successfully solve not only Olympiad problems.
In the future, I am going to continue studying graph theory, because I found this section of mathematics interesting and useful. In addition, while working on my research work, I mastered working on a computer in the text editor Word and Power Point. I believe that I fulfilled the objectives of the research work.
Literature.
Berezina L.Yu. Graphs and their application. – M., 1979.
Vilenkin N.Ya. Mathematics. – M.: Russian word, 1997.
Gardner M. “Mathematical leisure” M.: Mir, 1972
Gnedenko B.V. Probability theory course. - M.: URSS, 2005.
Konnova L.P. Meet the Counts. – Samara, 2001.
Lykova I.A. Logical puzzles – M.: Karapuz, 2000.
Savin A.V. encyclopedic Dictionary young mathematician. 2nd ed., - M.: Pedagogy, 1989
Shadrinova V.D. Cognitive processes and abilities in learning - M.: Education, 1980
Chistyakov V.P. Course in probability theory. M., Education, 1982.
Applications.
Annex 1.
Loburets Victoria Vladimirovna, born in 1994.
Loburets V. N
1962
.
Orlovskaya L.V.
Students' Scientific Society
"Search"
Computer science section
Scientific work on the topic:
"His Majesty the Count"
Performed: Sapozhnikova Svetlana,
7th grade student
Municipal educational institution "Sergeevskaya Secondary School"
Okoneshnikovsky MR
Supervisor: Garms Elena Anatolyevna,
IT-teacher
Municipal educational institution "Sergeevskaya Secondary School"
Omsk - 2010
Content
Student Scientific Society 1
"Search" 1
Scientific work on the topic: 1
Introduction 3
GRAPH THEORY 4
1.2.Eulerian graphs 7
1.3. The Bridge Problem, Leonhard Euler and Graph Theory 8
2.1. Solving problems using graphs “One day in the life of the Count” 11
Bibliography 16
Introduction
The relevance of research. This is the second year now that I have been interested in chess and have been studying at school in the “Checkmate” chess club. In one of the classes as homework A task was proposed in which it was necessary to calculate the rearrangement of pieces in a smaller number of moves. How to do it? I began to look for solutions, and it turned out that this can be done using graphs. Previously, I came across the concept of “count” only in history class when studying the topic of nobility.
Graphs interested me because of their ability to help solve various puzzles, mathematical and logical problems. 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, all kinds of transport schemes and much, much more. Very important for the normal functioning of social life. It is this factor that determines the relevance of their more detailed study. I decided to figure out what role graphs play in everyday life.
Object of study: concept of graph
Subject of study: degree of prevalence of graph use
Purpose of the study: Explore the role of graphs in our lives.
Research objectives:
1. get acquainted with the history of the emergence of graphs;
2. get acquainted with the basic concepts of a graph, types, elements;
3.learn to solve problems using graphs;
4. create your own family tree.
Research methods: partially - search, analytical.
Chapter 1
GRAPH THEORY
Concept of a graph
The word "graph" in mathematics means a picture with several points drawn, some of which are connected by lines. They are connected with the noble title “count” by a common origin from the Latin word “graphio” - I write.
In mathematics, the definition of a graph is given as follows: “a graph is a finite set of points, some of which are connected by lines.”
In computer science, a graph is understood as a means for visually representing the composition and structure of a system.
The graph consists of vertices and connection lines. Vertices can be depicted as circles, ovals, dots, or rectangles. Vertices can be connected by arcs or edges.
Connections between vertices are represented by lines. If the line is directed (i.e. with an arrow), then it is called an arc; if not directed (i.e., without an arrow), then it is called an edge. It is generally accepted that one edge replaces two arcs directed in opposite directions.
A graph in which all lines are directed is called a directed graph.
All vertices connected by an arc or edge are called adjacent.
although the term "graph" was first coined in 1936 by the Hungarian mathematician Dénes König.
With the help of graphs, the solution of problems formulated in various fields of knowledge was often simplified: in automation, electronics, physics, chemistry, etc. Graphs help in solving mathematical and economic problems.
A graph layout consisting of "isolated" vertices is called a null 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)
Degrees of vertices and counting the number of edges.
The number of edges leaving a vertex of the graph is called the degree of the vertex. A vertex of a graph that has an odd degree is called odd, and a vertex that has an even degree is called even.
If the degrees of all vertices of a graph are equal, then the graph is called homogeneous. Thus, any complete graph is homogeneous.
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 was what needed to be proven.
THEOREM.
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.
Note that if a complete graph has n vertices, then the number of edges will be equal to
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.
1.2.Eulerian graphs
A graph that can be drawn without lifting the pencil from the paper is called an Eulerian graph. (Fig.6)These graphs are named after the scientist Leonhard Euler.
Regularity 3 (follows from the theorem we considered).
It is impossible to draw a graph with an odd number of odd vertices.
Pattern 4.
If all the vertices of the graph are even, then you can draw this graph without lifting your pencil from the paper (“with one stroke”), moving along each edge only once. The movement can start from any vertex and end at the same vertex.
Pattern 5.
A graph with only two odd vertices can be drawn without lifting the pencil from the paper, and the movement must begin at one of these odd vertices and end at the second of them.
Pattern 6.
A graph with more than two odd vertices cannot be drawn with “one stroke.”
A figure (graph) that can be drawn without lifting the pencil from the paper is called unicursal.
Fig.6 (Eulerian graphs)
Connected graphs.
A graph is called connected 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.
A graph is said to be disconnected 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 turns from connected to disconnected) is called a 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 the connected components of the graph. Each connected component is, of course, a connected graph. Note that a connected graph has one connected component.
1.3. The Bridge Problem, Leonhard Euler and Graph Theory
Former Koenigsberg (now Kaliningrad) is located on the Pregel River. Within the city, the river washes two islands. Bridges were built from the shores to the islands. The old bridges have not survived, but a map of the city remains, where they are depicted.
The following riddle has long been common among the residents of Königsberg: how to cross all the bridges without crossing any of them twice? Many Königsbergers tried to solve this problem both theoretically and practically during walks. But no one succeeded, but they also failed to prove that it was even theoretically impossible.
This question has attracted the attention of scientists different countries. In 1736, the problem of seven bridges interested the outstanding mathematician, member of the St. Petersburg Academy of Sciences, Leonhard Euler, which he wrote about in a letter to the Italian mathematician and engineer Marioni dated March 13, 1736. In this letter, Euler writes that he was able to find a rule, using which it is easy to determine whether it is possible to walk across all the bridges without passing over any of them twice (in the case of the seven bridges of Königsberg, this is impossible).
Moreover, he not only solved this specific problem, but came up with a general method for solving similar problems. Euler acted as follows: he “compressed” the land into points, and “stretched” the bridges into lines, as shown in Figure 9 a, b.
Figure 9
In a simplified diagram of parts of a city (graph), bridges correspond to lines (edges of the graph), and parts of the city correspond to points connecting lines (vertices of the graph). During his reasoning, Euler came to the following conclusions:
The number of odd vertices (vertices to which an odd number of edges lead) of a graph is always even. It is impossible to draw a graph that has an odd number of odd vertices.
If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex.
A graph with more than two odd vertices cannot be drawn with one stroke.
Let's clearly formulate the task at hand. Under what condition is it possible to traverse all the edges of a graph, passing each one exactly once? The solution turned out to be very simple. Let's count how many edges come out of each vertex. Some of these numbers will be even and others will be odd. We will call the vertices themselves even if they have an even number of edges, and odd otherwise. As we already know: the number of edges coming out of a given vertex is called the degree of the vertex. A vertex of a graph that has odd degree, is called odd, and an even degree is called even.
The graph of Königsberg bridges had four odd vertices, therefore it is impossible to walk across all the bridges without passing over one of them twice.
While solving the problem about the Königsberg bridges, Euler established, in particular, the properties of the graph:
If all the vertices of the graph are even, then you can draw a graph with one stroke (that is, without lifting the pencil from the paper and without drawing twice along the same line). In this case, the movement can start from any vertex and end at the same vertex.
A graph with two odd vertices can also be drawn with one stroke. The movement must begin from any odd vertex and end at another odd vertex.
A graph with more than two odd vertices cannot be drawn with one stroke.
Trees.
A tree is any connected graph that has no cycles. We agreed to consider any graph consisting of one (isolated) vertex to be a “tree”.
A cycle is a path in which the beginning and the end coincide.
If all the vertices of a cycle are different, then such a cycle is called an elementary (or simple) cycle. If a cycle includes all the edges of the graph once, then such a cycle is called an Euler line (Fig. 10a). The graph in Fig. 10b has two cycles: 1-2-3-4-1 and 5-6-7-5.
A path in a graph from one vertex to another is a sequence of edges along which a route can be laid between these vertices. In this case, no edge of the route should appear more than once. The peak from which the route is laid is called the beginning of the path, the peak at the end of the route is the end of the path.
A hanging vertex is a vertex from which exactly one edge emerges. (Fig. 12)
Fig. 10 a;b
Property 1.
For each pair of tree vertices, there is a unique path connecting them.
This property is used when finding all the ancestors in a family tree, for example, in the male line, of any person whose pedigree is represented in the form of a family tree, which is a “tree” in the sense of graph theory.
Property 2.
Every edge in a tree is a bridge.
Indeed, after removing any edge of a tree, it “splits” into two trees.
Fig. 12 (hanging peaks are circled)
A graph in which any two vertices are connected by exactly one simple path is a tree.
Proof:
It is obvious that this graph is connected. Let's assume it has a loop. Then any two vertices of this cycle are connected by at least two simple paths. We received a contradiction, which means our assumption is incorrect.
A tree is a graph in which any two vertices are connected by exactly one simple path.
LEMMA (about the hanging vertex)
Every tree has a hanging top.
Proof:
Let's consider an arbitrary vertex of the tree and follow any edge leaving it to another vertex. If no more edges come out of the new vertex, then we remain in it, and otherwise, we move along any other edge further. It is clear that on this journey we will never be able to reach a peak that we have already visited: this would mean the presence of a cycle. Since the graph has a finite number of vertices, our journey must end. But it can only end at a hanging top. The lemma is proven.
What can be described using graphs? Let us indicate the areas of application of this description.
Graphs are used in many areas of practical and scientific activity of people.
For example:
The map of subway lines can be thought of as a graph;
In chemistry, a graph can be thought of as a way of representing the structure of a molecule;
In medicine - the question of blood type;
A family tree can be represented as a graph;
Classification systems in science.
Hierarchical structure of administrative management of an enterprise, university, etc.
In computer science: disk file system, Internet domain address system, block diagrams of algorithms.
And many more different examples can be given...
Chapter 2
2.1. Solving problems using graphs “One day in the life of a Count”
Let's look at solving problems using graphs from school life.
Task 1. In the morning, students from our school were brought from the surrounding villages of Volchino, Olkhovka, Kochkovatoe, Pavlovka to classes. The figure shows a graph representing information about roads between four villages: Volchino, Olkhovka, Kochkovatoe, Pavlovka. The weights of the vertices are the names of the villages, the weights of the lines are the length of the roads in kilometers.
The bus route is a graph.
Task 2. When we met, each of my classmates shook hands with the other (each shook each other). How many handshakes were made if there were: 1) three friends; 2) four; 3) five?
Solution.
The problem is solved using complete graphs.
1) Three people met:
The number of handshakes is equal to the number of edges, i.e. 3.
2) Four people met:
Number of ribs 6; 6 handshakes possible.
3) Five people met:
There are 10 edges in the graph; maybe 10 handshakes.
Answer: 1)3; 2)6; 3)10.
According to the schedule, we have six lessons: geometry, history, computer science, geography, Russian language and physics.
Task 3. In a geometry lesson, it was proposed to construct a classification graph of geometric objects. This turned out to be easy to do using the concept of a graph. 
Problem 4. And in history class we had to make a family tree. Family tree. Uses counts and nobility. For example, in a family tree, the vertices are members of the clan, and the segments connecting them are relationships of kinship.
Everyone knows that the word “count” means a noble title, for example, Count Lev Nikolaevich Tolstoy. There is another graph in the figure - part of the family tree of Count L.N. Tolstoy. Here the vertices are the ancestors of the writer, and the edges show the family connections between them.
Problem 5. In computer science class we met new topic"Algorithms". And to my surprise, it turned out that a block diagram is a directed graph. A block diagram of an algorithm is a graph of the control process of some executor. The blocks - the vertices of this graph - indicate individual commands, and the arcs indicate the sequence of transitions from one command to another. In the algorithm, any path starts from the beginning vertex and ends with an exit to the end vertex. Inside, the path may be different depending on the source data.
Task 6. In geography lesson we looked at a paragraph. And to find it faster, I opened the contents at the end of the textbook. And to my surprise I noticed that the structure of the sections of the textbook is reflected in the form of a tree.
Problem 7. During the Russian language lesson, the topic was “Numerals” and the teacher suggested that we make a supporting summary.
Numerals in the Russian language are classified according to composition and meaning. Based on their composition, they are divided into simple, complex and compound. Example of simple numbers: four, five. Example of complex numerals: sixty, five hundred. An example of compound numerals: 35, 154. Based on their meaning, numerals are divided into ordinal and cardinal. Example of ordinal numbers: second, ninth. Example of cardinal numbers: six, two.
After class, we all ran to the cafeteria, where a set lunch was served. I love borscht, and my neighbor at the desk is rassolnik.
Problem 8. The dining room offers two first courses: borscht, rassolnik, as well as four second courses: goulash, cutlets, sausages, dumplings. List all two-course meals that a diner may order. Illustrate your answer by constructing a tree of possible options.
Solution.
To indicate all two-course meals, we will reason like this.
Let's choose one first course (borscht) and add different second courses to it one by one
Answer: 8 different two-course meals.
Comment. In the problem, two choices are made, but each choice is from its own set of options.
Answer: 6 combinations.
Arriving home, I quickly completed all my homework. And the semantic network, a knowledge model in the form of a graph, helped me with this. It is based on the idea that any knowledge can be represented as a set of objects (Concepts) and connections (Relationships) between them.
After school, in the classes of the “Entertaining Informatics” and “Check and MAT” clubs, thanks to graph theory, we easily solved logical problems.
In the evening, my mother asked me to go to the store to buy bread. The “Bread Store” system consists of the following elements: bread, seller, buyer, counter, car, driver, loader, money, check. The vertices of the graph are the listed objects, and the arcs are the relationships between them. Returning home from the store, I involuntarily caught myself thinking about Counts: Counts surround me everywhere.
So the counts became my best friends. Classmates and teachers noticed that my performance in subjects had improved. But I know that this is thanks to “His Majesty the Count”!
Conclusion
Graphs are wonderful mathematical objects that can be used to solve mathematical, economic and logical problems. You can also solve various puzzles and simplify the conditions of problems in physics, chemistry, electronics, and automation. Graphs are used in the compilation of maps and family trees.
There is even a special section in mathematics called “Graph Theory”. Graphs present the facts being studied in a visual form. Techniques for solving logical problems using graphs are captivating with their naturalness and simplicity, eliminating unnecessary reasoning, which in many cases reduces the load on memory.
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 problems have a number of advantages that allow them to be used to develop imagination and improve logical thinking, and are applicable in solving many geometric problems.
Bibliography
1. Genkin, S. A, Itenberg I. V. Leningrad mathematical circles: a manual for
extracurricular activities.-Kirov, 1994.
2.Gorbachev, V.G. Collection of Olympiad problems in mathematics. - M., 2004.
3. Ignatiev E.I. Mathematical savvy. - Moscow, 1994
4. Ore, O. Graphs and their application. - Moscow, 1979.
5. Perelman, Ya.I. Fun tasks. - Moscow, 2003
6. Physics and mathematics journal “Kvant”, A. Savin, No. 6, 1994.
Page 1
|
|
Third city scientific
student conference
Computer Science and Mathematics
Euler circles and graph theory in problem solving
school mathematics and computer science
Valiev Airat
Municipal educational institution
"Secondary school No. 10 with in-depth study
individual subjects", 10 B class, Nizhnekamsk
Scientific supervisors:
Khalilova Nafise Zinnyatullovna, mathematics teacher
IT-teacher
Naberezhnye Chelny
Introduction. 3
Chapter 1. Euler circles. 4
1.1. Theoretical foundations about Euler circles. 4
1.2. Solving problems using Euler circles. 9
Chapter 2. About columns 13
2.1.Graph theory. 13
2.2. Solving problems using graphs. 19
Conclusion. 22
Bibliography. 22
Introduction
“All our dignity lies in thought.
It's not space, it's not time that we can't fill,
elevates us, namely it, our thought.
Let us learn to think well.”
B. Pascal,
Relevance. The main task of the school is not to provide children with a large amount of knowledge, but to teach students to acquire knowledge themselves, the ability to process this knowledge and apply it in everyday life. The given tasks can be solved by a student who not only has the ability to work well and hard, but also a student with developed logical thinking. In this regard, many school items Various types of tasks are included, which develop logical thinking in children. When solving these problems, we use various solution techniques. One of the solution methods is the use of Euler circles and graphs.
Purpose of the study: study of material used in mathematics and computer science lessons, where Euler circles and graph theory are used as one of the methods for solving problems.
Research objectives:
1. Study the theoretical foundations of the concepts: “Eulerian circles”, “Graphs”.
2. Solve the problems of the school course using the above methods.
3. Compile a selection of material for use by students and teachers in mathematics and computer science lessons.
Research hypothesis: the use of Euler circles and graphs increases clarity when solving problems.
Subject of study: concepts: “Euler circles”, “Graphs”, problems of a school course in mathematics and computer science.
Chapter 1. Euler circles.
1.1. Theoretical foundations about Euler circles.
Euler circles (Euler circles) are a method of modeling accepted in logic, a visual representation of the relationships between volumes of concepts using circles, proposed by the famous mathematician L. Euler (1707–1783).
The designation of relationships between the volumes of concepts by means of circles was used by a representative of the Athenian Neoplatonic school - Philoponus (VI century), who wrote commentaries on Aristotle's First Analytics.
It is conventionally accepted that a circle visually depicts the volume of one concept. The scope of a concept reflects the totality of objects of one or another class of objects. Therefore, each object of a class of objects can be represented by a point placed inside a circle, as shown in the figure:
The group of objects that makes up the appearance of a given class of objects is depicted as a smaller circle drawn inside a larger circle, as is done in the figure.
https://pandia.ru/text/78/128/images/image003_74.gif" alt="overlapping classes" width="200" height="100 id=">!}
This is precisely the relationship that exists between the scope of the concepts “student” and “Komsomol member”. Some (but not all) students are Komsomol members; some (but not all) Komsomol members are students. The unshaded part of circle A reflects that part of the scope of the concept “student” that does not coincide with the scope of the concept “Komsomol member”; The unshaded part of circle B reflects that part of the scope of the concept “Komsomol member” that does not coincide with the scope of the concept “student”. The shaded part, which is common to both circles, denotes students who are Komsomol members and Komsomol members who are students.
When not a single object displayed in the volume of concept A can simultaneously be displayed in the volume of concept B, then in this case the relationship between the volumes of concepts is depicted by means of two circles drawn one outside the other. Not a single point lying on the surface of one circle can be on the surface of another circle.
https://pandia.ru/text/78/128/images/image005_53.gif" alt=" concepts with the same volumes - coinciding circles" width="200" height="100 id=">!}
Such a relationship exists, for example, between the concepts “the founder of English materialism” and “the author of the New Organon.” The scope of these concepts is the same; they reflect the same historical figure - the English philosopher F. Bacon.
It often happens like this: one concept (generic) is subordinated to several specific concepts at once, which in this case are called subordinate. The relationship between such concepts is depicted visually by one large circle and several smaller circles, which are drawn on the surface of the larger circle:
https://pandia.ru/text/78/128/images/image007_46.gif" alt="opposite concepts" width="200" height="100 id=">!}
At the same time, it is clear that between opposite concepts a third, average, is possible, since they do not completely exhaust the scope of the generic concept. This is exactly the relationship that exists between the concepts “light” and “heavy”. They are mutually exclusive. It is impossible to say about the same object, taken at the same time and in the same relation, that it is both light and heavy. But between these concepts there is a middle ground, a third: objects are not only light and heavy weight, but also medium weight.
When there is a contradictory relationship between concepts, then the relationship between the volumes of concepts is depicted differently: the circle is divided into two parts as follows: A is a generic concept, B and non-B (denoted as B) are contradictory concepts. Conflicting concepts exclude each other and belong to the same genus, which can be expressed by the following diagram:
https://pandia.ru/text/78/128/images/image009_38.gif" alt="subject and predicate of definition" width="200" height="100 id=">!}
The diagram of the relationship between the volumes of the subject and the predicate in a general affirmative judgment, which is not a definition of a concept, looks different. In such a judgment, the scope of the predicate is greater than the scope of the subject; the scope of the subject is entirely included in the scope of the predicate. Therefore, the relationship between them is depicted by means of large and small circles, as shown in the figure:
School libraries" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">school library, 20 - in the district. How many of the fifth graders:
a) are not readers of the school library;
b) are not readers of the district library;
c) are readers only of the school library;
d) are readers only of the regional library;
e) are readers of both libraries?
3. Each student in the class learns either English or French, or both. English language 25 people study French, 27 people study French, and 18 people study both. How many students are there in the class?
4. On a sheet of paper, draw a circle with an area of 78 cm2 and a square with an area of 55 cm2. The area of intersection of a circle and a square is 30 cm2. The part of the sheet not occupied by the circle and square has an area of 150 cm2. Find the area of the sheet.
5. B kindergarten 52 children. Each of them loves either cake or ice cream, or both. Half of the children like cake, and 20 people like cake and ice cream. How many children love ice cream?
6. There are 86 high school students in the student production team. 8 of them do not know how to operate either a tractor or a combine. 54 students mastered the tractor well, 62 - the combine. How many people from this team can work on both a tractor and a combine?
7. There are 36 students in the class. Many of them attend clubs: physics (14 people), mathematics (18 people), chemistry (10 people). In addition, it is known that 2 people attend all three circles; Of those who attend two circles, 8 people are involved in mathematical and physical circles, 5 are in mathematical and chemical circles, 3 are in physical and chemical circles. How many people do not attend any clubs?
8. 100 sixth-graders at our school took part in a survey to find out which computer games they liked best: simulators, quests or strategies. As a result, 20 respondents named simulators, 28 - quests, 12 - strategies. It turned out that 13 schoolchildren give equal preference to simulators and quests, 6 students - to simulators and strategies, 4 students - to quests and strategies, and 9 students are completely indifferent to the mentioned computer games. Some of the schoolchildren answered that they were equally interested in simulators, quests, and strategies. How many of these guys are there?
Answers
https://pandia.ru/text/78/128/images/image012_31.gif" alt="Oval: A" width="105" height="105">1.!}
A – chess 25-5=20 – people. know how to play
B – checkers 20+18-20=18 – people play both checkers and chess
2. Ш – many visitors to the school library
P – many visitors to the district library
 |
https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">
 |
5. 46. P – cake, M – ice cream
6 – children love cake
6. 38. T – tractor, K – combine
54+62-(86-8)=38 – able to work on both a tractor and a combine
graphs" and systematically study their properties.
Basic concepts.
The first of the basic concepts of graph theory is the concept of a vertex. In graph theory it is taken as primary and is not defined. It is not difficult to imagine it on your own intuitive level. Usually the vertices of the graph are visually depicted in the form of circles, rectangles and other figures (Fig. 1). At least one vertex must be present in each graph.
Another basic concept in graph theory is arcs. Typically, arcs are straight or curved segments connecting vertices. Each of the two ends of the arc must coincide with some vertex. The case when both ends of the arc coincide with the same vertex is not excluded. For example, in Fig. 2 there are acceptable images of arcs, and in Fig. 3 they are unacceptable:
In graph theory, two types of arcs are used - undirected or directed (oriented). A graph containing only directed arcs is called a directed graph or digraph.
Arcs can be unidirectional, with each arc having only one direction, or bidirectional.
In most applications, it is possible without loss of meaning to replace an omnidirectional arc with a bidirectional arc, and a bidirectional arc with two unidirectional arcs. For example, as shown in Fig. 4.
As a rule, the graph is either immediately constructed in such a way that all arcs have the same directional characteristic (for example, all are unidirectional), or is brought to this form through transformations. If the arc AB is directed, then this means that of its two ends, one (A) is considered the beginning, and the second (B) is the end. In this case, they say that the beginning of the arc AB is vertex A, and the end is vertex B, if the arc is directed from A to B, or that the arc AB comes from vertex A and enters B (Fig. 5).
Two vertices of a graph connected by some arc (sometimes, regardless of the orientation of the arc) are called adjacent vertices.
An important concept in the study of graphs is the concept of path. A path A1,A2,...An is defined as a finite sequence (tuple) of vertices A1,A2,...An and arcs A1, 2,A2,3,...,An-1, n sequentially connecting these vertices.
An important concept in graph theory is the concept of connectivity. If for any two vertices of a graph there is at least one path connecting them, the graph is called connected.
For example, if you depict the human circulatory system as a graph, where the vertices correspond to internal organs and the arcs correspond to blood capillaries, then such a graph is obviously connected. Is it possible to say that the circulatory system of two arbitrary people is a disconnected graph? Obviously not, since the so-called are observed in nature. "Siamese twins".
Connectedness can be not only a qualitative characteristic of a graph (connected/disconnected), but also a quantitative one.
A graph is called K-connected if each of its vertices is connected to K other vertices. Sometimes they talk about weakly and strongly connected graphs. These concepts are subjective. A researcher calls a graph strongly connected if for each of its vertices the number of adjacent vertices, in the researcher’s opinion, is large.
Sometimes connectivity is defined as a characteristic not of each, but of one (arbitrary) vertex. Then type definitions appear: a graph is called K-connected if at least one of its vertices is connected to K other vertices.
Some authors define connectivity as the extreme value of a quantitative characteristic. For example, a graph is K-connected if there is at least one vertex in the graph that is connected to K adjacent vertices and no vertex that is connected to more than K adjacent vertices.
For example, children's drawing person (Fig. 6) is a graph with maximum connectivity equal to 4.
Another graph characteristic studied in a number of problems is often called graph cardinality. This characteristic is defined as the number of arcs connecting two vertices. In this case, arcs having the opposite direction are often considered separately.
For example, if the vertices of the graph represent information processing nodes, and the arcs are unidirectional channels for transmitting information between them, then the reliability of the system is determined not by the total number of channels, but by the smallest number of channels in any direction.
Cardinality, like connectivity, can be determined both for each pair of vertices of the graph, and for some (arbitrary) pair.
An essential characteristic of a graph is its dimension. This concept is usually understood as the number of vertices and arcs existing in a graph. Sometimes this quantity is defined as the sum of the quantities of elements of both types, sometimes as a product, sometimes as the number of elements of only one (one or another) type.
Types of graphs.
Objects modeled by graphs are of a very diverse nature. The desire to reflect this specificity led to the description large quantity types of graphs. This process continues to this day. Many researchers, for their specific purposes, introduce new varieties and carry out their mathematical study with greater or lesser success.
At the heart of all this diversity are several fairly simple ideas, which we will talk about here.
Coloring
Graph coloring is a very popular way to modify graphs.
This technique allows you to increase the clarity of the model and increase the mathematical workload. Methods for introducing color can be different. Both arcs and vertices are colored according to certain rules. The coloring can be determined once or change over time (that is, when the graph acquires any properties); colors can be converted according to certain rules, etc.
For example, let the graph represent a model of human blood circulation, where the vertices correspond to internal organs, and the arcs correspond to blood capillaries. Let's color the arteries red and the veins blue. Then the following statement is obviously true - in the graph under consideration (Fig. 8) there are, and only two, vertices with outgoing red arcs (the red color is shown in bold in the figure).
Length
Sometimes the object elements modeled by vertices have significantly different characters. Or, during the formalization process, it turns out to be useful to add some fictitious elements to the elements that actually exist in the object. In this and some other cases, it is natural to divide the vertices of the graph into classes (shares). A graph containing vertices of two types is called bipartite, etc. In this case, rules regarding the relationships between vertices are included in the graph restrictions different types. For example: “there is no arc that would connect vertices of the same type.” One of the varieties of graphs of this kind is called a “Petri net” (Fig. 9) and is quite widespread. Petri nets will be discussed in more detail in the next article in this series.
The concept of valleys can be applied not only to vertices, but also to arcs.
2.2. Solving problems using graphs.
1. Problem about the Königsberg bridges. In Fig. 1 shows a schematic plan of the central part of the city of Koenigsberg (now Kaliningrad), including two banks of the Pergola River, two islands in it and seven connecting bridges. The task is to go around all four parts of the land, crossing each bridge once, and return to the starting point. This problem was solved (it was shown that there was no solution) by Euler in 1736. (Fig. 10).
2. The problem of three houses and three wells. There are three houses and three wells, somehow located on a plane. Draw a path from each house to each well so that the paths do not intersect (Fig. 2). This problem was solved (it was shown that there is no solution) by Kuratovsky in 1930. (Fig. 11).
3. The four color problem. A division of a plane into non-overlapping areas is called a map. Areas on a map are called adjacent if they have a common border. The task is to color the map in such a way that no two adjacent areas are painted with the same color (Fig. 12). Since the end of the century before last, the hypothesis has been known that four colors are enough for this. In 1976, Appel and Heiken published a solution to the four-color problem, which was based on a computer search. The solution to this problem “programmatically” was a precedent that gave rise to a heated debate, which is by no means over. The essence of the published solution is to try a large but finite number (about 2000) types of potential counterexamples to the four-color theorem and show that not a single case is a counterexample. This search was completed by the program in about a thousand hours of supercomputer operation. It is impossible to check the resulting solution “manually” - the scope of enumeration goes far beyond human capabilities. Many mathematicians raise the question: can such a “program proof” be considered a valid proof? After all, there may be errors in the program... Methods for formally proving the correctness of programs are not applicable to programs of such complexity as the one being discussed. Testing cannot guarantee the absence of errors and in this case is generally impossible. Thus, we can only rely on the programming skills of the authors and believe that they did everything right.
4.
Dudeney's tasks.
1. Smith, Jones and Robinson work on the same train crew as a driver, conductor and fireman. Their professions are not necessarily named in the same order as their surnames. There are three passengers with the same last names on the train served by the brigade. In the future, we will respectfully call each passenger “Mr.”
2. Mr. Robinson lives in Los Angeles.
3. The conductor lives in Omaha.
4. Mr. Jones has long forgotten all the algebra that he was taught in college.
5. The passenger, the conductor’s namesake, lives in Chicago.
6. The conductor and one of the passengers, a famous expert in mathematical physics, although they go to the same church.
7. Smith always wins over the fireman when they happen to meet at a game of billiards.
What is the driver's last name? (Fig. 13)
Here 1-5 are the numbers of moves, in brackets are the numbers of points of the problem on the basis of which the moves (conclusions) were made. It further follows from paragraph 7 that the fireman is not Smith, therefore, Smith is the machinist.
Conclusion
Analysis of theoretical and practical material on the topic under study allows us to draw conclusions about the success of using Euler circles and graphs for the development of logical thinking in children, instilling interest in the material being studied, using visual aids in lessons, as well as reducing difficult problems to easy ones for understanding and solving.
Bibliography
1. “Entertaining tasks in computer science”, Moscow, 2005
2. “Scenarios for school holidays” by E. Vladimirova, Rostov-on-Don, 2001
3. Tasks for the curious. , M., Education, 1992,
4. Extracurricular work in mathematics, Saratov, Lyceum, 2002.
5. The wonderful world of numbers. , ., M., Education, 1986,
6. Algebra: textbook for 9th grade. , and others, ed. , - M.: Enlightenment, 2008
Presentation - Soviet rear during the Great Patriotic War
Presentation for a lesson on fairy tale G
Why Alexander Nevsky became a friend of the Tatar Khan and entered into an alliance with the horde