Titov Maxim
1. Consider all routes of the Nizhnegorsk region.
2. Based on the route data, create new routes.
3. Show if the new routes are Euler graphs.
4. Build an adjacency matrix for new routes.
5. Find shortest distances from the village of Nizhnegorsky to settlements.
Download:
Preview:
INTRODUCTION ……………………………………………………………………………….3
SECTION 1. BASIC GRAPH DEFINITIONS ………………………………………………………………………………………………………………………………………………………………………….
- Basic concepts of graph theory ......…………………...……...…………5
- Characteristics of Euler graphs …………………………...…………...7
- Finding the shortest distance in a graph (Dikstree's Algorithm)…………..8
SECTION 2. ROUTES OF THE NIZHNEGORSKY DISTRICT ……………………..……10
- Routes of the Nizhnegorsk region …..…..……………………………….10
- Study of the routes of the Nizhnegorsk region ……..………………..11
CONCLUSION …………………………………………………………………………….17
LIST OF USED LITERATURE ……………………………………….19
INTRODUCTION
Graphs are wonderful mathematical objects with which you can solve mathematical, economic and logical problems. You can also solve various puzzles and simplify the conditions of tasks in physics, chemistry, electronics, automation. Graphs are used in the compilation of maps and family trees. Graphs are flowcharts of computer programs, network graphs of construction, where the vertices are events that indicate the completion of work in a certain area, and the edges connecting these vertices are work that can be started after one event and must be completed to complete the next. One of the most common graphs are subway line diagrams.
Mathematics even has a special section, which is called: “Graph Theory”. Graph theory is part of both topology and combinatorics. The fact that this is a topological theory follows from the independence of the properties of a 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 mind numerous facts given in a condition, to establish a connection between them, to express hypotheses, to draw particular conclusions and use them.
The relevance of the topic lies in the fact that graph theory is currently an intensively developing section 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.
The purpose of the work is to study the transport routes of the Nizhnegorsk region.
Work tasks:
1 . View all routes of the Nizhnegorsk region.
2 . Based on the routes, create new routes.
3. Show if the new routes are Euler graphs.
4. Build an adjacency matrix for new routes.
5. Find the shortest distances from the village of Nizhnegorsky to settlements.
The object of the study is a map of the transport routes of the Nizhnegorsk region.
The practical significance of this work is that it can be used in the classroom when solving various problems, as well as in various fields of science and in modern life.
Applied methods: search for sources of information, observation, comparison, analysis, mathematical modeling.
The structure of sections is connected with the general idea of the work. The main part consists of three chapters. The first deals with the basic concepts of graphs. The second chapter examines the routes of the Nizhnegorsk region.
When working, I used a number of literary sources: special literature on graph theory, cognitive literature, various popular science, educational, specialized journals.
SECTION 1
BASIC GRAPH DEFINITIONS
1.1. Basic concepts of graph theory
A graph is a non-empty set of points and a set of segments, both ends of which belong to a given set of points. (Fig.1.1.)
Fig.1.1.
Graph vertex is a point where edges and/or arcs can converge/exit.
Graph Edge - An edge connects two graph vertices.
The degree of the vertex is the number of edges coming out of the vertex of the graph.
The vertex of the graph, which has no even degree, is called odd, and an even degree is called even.
If the direction of the connection matters, then the lines are provided with arrows, and in this case the graph is called a directed graph, a digraph. (Fig.1.2.)
Fig.1.2.
A weighted graph is a graph, each edge of which is assigned a certain value (the weight of the edge). (Fig.1.3.)
Rice. 1.3.
Graphs in which all possible edges are built are called complete graphs. (Fig.1.4.)
Rice. 1.4.
A graph is called connected if any two of its vertices can be connected by a path, that is, by a sequence of edges, each of which starts at the end of the previous one.
The adjacency matrix is a matrix whose element M[i] [j] is equal to 1 if there is an edge from vertex i to vertex j, and is equal to 0 if there is no such edge (Fig.1.5. for the graph in Fig.1.1).
1.2. Characterization of Euler graphs
A graph that can be drawn without lifting the pencil from the paper is called an Euler graph. (fig.1.6.)
Such graphs are named after the scientist Leonhard Euler.
Regularity 1.
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 without lifting the pencil from the paper (“in one stroke”), drawing along each edge only once, draw this graph. The movement can start from any vertex and end it at the same vertex.
Pattern 3.
A graph that has 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 in one stroke.
A figure (graph) that can be drawn without lifting the pencil from the paper is called unicursal.
Fig.1.6.
1.3. Finding the Shortest Distance in a Graph (Dijkstree's Algorithm)
Task: a network of roads between cities is given, some of which can have one-way traffic. Find the shortest distances from a given city to all other cities (Fig. 1.7).
The same problem: given a connected graph with N vertices, edge weights given by the matrix W. Find the shortest distances from a given vertex to all the others.
Dijkstra's algorithm (E.W. Dijkstra, 1959):
1. Label all vertices ∞.
2. Among the unconsidered vertices, find the vertex j with the smallest label.
3. For each unprocessed vertex i: if the path to vertex i through vertex j is less than the existing label, replace the label with a new distance.
4. If there are unprocessed vertices, go to step 2.
5. Mark = minimum distance.
Fig.1.7.
Fig.1.8. The solution of the problem
SECTION 2
ROUTES OF THE NIZHNEGORSKY DISTRICT
2.1. Routes of the Nizhnegorsk region
Nizhnegorsky district is located in the steppe part in the north of the Autonomous Republic of Crimea. Nizhnegorsky district includes urban-type settlement Nizhnegorsky and 59 settlements.
Two highways pass through the Nizhnegorsk region: 2Р58 and 2Р64. There are 8 routes from A/S Nizhnegorskaya to other settlements. In my work, I will consider these routes:
1 route "Nizhnegorsk - Krasnogvardeysk". It follows through: Nizhnegorsk - Plodovoe - Mitofanovka - Burevestnik - Vladislavovka.
Route 2 "Nizhnegorsk - Izobilnoe": Nizhnegorsk - Semennoe - Kirsanovka - Deciduous - Okhotsk - Tsvetushchee - Emelyanovka - Izobilnoe.
Route 3 "Nizhnegorsk - Velikoselye": Nizhnegork - Semennoye - Mesopotamia - Akimovka - Luzhki - Zalivnoye - Stepanovka - Lugovoe - Chkalovo - Velikoselye.
Route 4 "Nizhnegorsk - Belogorsk (route 2P64)": Nizhnegorsk - Zhelyabovka - Ivanovka - Zarechye - Serovo - Sadovoye - Peny.
Route 5 "Nizhnegorsk - Uvarovka": Nizhnegorsk - Semennoe - Novoivanovka - Uvarvka.
Route 6 "Nizhnegorsk - Lyubimovka": Nizhnegorsk - Semennoye - Mesopotamia - Akimovka - Luzhki - Zalivnoye - Stepanovka - Lugovoe - Kovorovo - Dvorovoe - Lyubimovka.
Route 7 "Nizhnegorsk - Pshenichnoye": Nizhnegorsk - Semennoye - Mesopotamia - Akimovka - Luzhki - Zalivnoye - Stepanovka - Lugovoe - Kovorovo - Dvorovoe - Slivyanka - Pshenichnoye.
Route 8 "Nizhnegorsk - Zorkino (route 2Р58)": Nizhnegorsk - Spills - Mikhailovka - Kuntsevo - Zorkino.
There are a lot of villages where buses do not stop on the routes and people have to get to their settlements on their own, mostly on foot. Therefore, the task before me was: Is it possible to draw up new routes and include in them settlements that buses do not enter.
The routes Nizhnegorsk - Uvarovka, Nizhnegorsk - Lyubimovka, Nizhnegorsk - Pshenichnoye, cannot be changed, because along their route, buses call in all settlements, so I will not consider these routes.
Consider the other five routes. Settlements will be denoted by numbers - these are the vertices of the graph, and the distances between them - the edges of the graph and we will get five graphs. Let's consider each graph separately.
2.2. Study of the routes of the Nizhnegorsk region
Route 1: Nizhnegorsk - Krasnogvardeysk.
Nizhnegorsk - 1
Fruit - 2
Mitrofanovka - 3
Chervonoe - 6
Burevestnik - 4
Novogrigorievka - 7
Vladislavovka - 5
Doesn't call at points 6, 7. Let's add these settlements to the route.
Fig.2.1.
The graph is not Euler. The new route looks like this: Nizhnegorsk - Plodovoe - Mitrofanovka - Burevestnik - Novogrigorievka - Vladislavovka. The village of Novogrigorevka was added.
2 route: Nizhnegorsk - Izobilnoe.
Nizhnegorsk - 1
Seed - 2
Kirsanovka - 3
Deciduous - 4
Okhotsk - 5
Blooming - 6
Emelyanovka - 7
Abundant - 8
Easter cakes - 9
Springs - 10
Does not visit point 9.10. Let's add these settlements to the route.
Fig.2.2.
The graph is not Euler and connected, so it is impossible to build a new route. The route remains the same.
Route 3: Nizhnegorsk - Velikoselye
Nizhnegorsk - 1
Seed - 2
Mesopotamia - 3
Akimovka - 4
Meadows - 5
Jellied - 6
Stepanovka - 7
Lugovoe - 8
Chkalovo - 9
Greatness - 10
Wide - 11
Does not enter point 11. Let's add this settlement to the route.
Fig.2.3.
The graph is not Euler. The route remains the same.
Route 4: Nizhnegorsk - Belogorsk (Route 2Р64)
Nizhnegorsk - 1 Kostochkovka - 12
Zhelyabovka - 2 Frunze - 13
Ivanovka - 3 Prirechnoe - 14
District - 4 Pearl - 15
Serovo - 5
Garden - 6
Foam - 7
Lomonosovo - 8
Corn - 9
Tambovka - 10
Tarasovka - 11
Does not visit points 8-18. Let's add these settlements to the route.
Fig.2.4.
The graph is not Euler. The new route looks like this: Nizhnegorsk - Zhelyabovka - Ivanovka - Zarechye - Tambovka - Tarsovka - Prirechnoye - Zhemchuzhina - Peny.
Route 5: Nizhnegorsk - Zorkino (Route 2Р58)
Nizhnegorsk - 1
Spills - 2
Mikhailovka - 3
Kuntsevo - 4
Zorkino - 5
Cozy - 6
Nijinsky - 7
Does not visit point 6.7. Let's add these settlements to the route.
Fig.2.5.
The graph is not Euler and connected, so the route remains the same.
CONCLUSION
Fractal science is very young and has a great future ahead of it. The beauty of fractals is far from being exhausted and will still give us many masterpieces - those that delight the eye, and those that bring true pleasure to the mind. This is the novelty of the work.
In conclusion, I would like to say that after fractals were discovered, it became obvious to many scientists that the good old forms of Euclidean geometry are much worse than most natural objects due to the lack of some irregularity, disorder and unpredictability in them. It is possible that the new ideas of fractal geometry will help to study many mysterious phenomena surrounding nature. At present, fractals are rapidly invading many areas of physics, biology, medicine, sociology, and economics. Image processing and pattern recognition methods that use new concepts enable researchers to apply this mathematical apparatus to quantify huge amount natural objects and structures.
During the study, the following work was done:
1. Analyzed and worked out the literature on the research topic.
2. Various types of fractals are considered and studied.
3. A classification of fractals is presented.
4. A collection of fractal images has been assembled for the initial acquaintance with the world of fractals.
5. Compiled programs for constructing a graphic image of fractals.
For me personally, the study of the topic "The inexhaustible wealth of fractal geometry" turned out to be very interesting and unusual. In the process of research, I made a lot of new discoveries for myself, related not only to the theme of the project, but also to the surrounding worlds in general. I have a great interest in this topic, and therefore this work had an extremely positive impact on my understanding of modern science.
Having finished my project, I can say that everything that was planned was achieved. Next year I will continue to work on the topic of "fractals", as this topic is very interesting and multifaceted. I think that I have solved the problem of my project, since I have achieved all the goals I set. Working on the project showed me that mathematics is not only an exact, but also a beautiful science.
LIST OF USED SOURCES
1. V.M. Bondarev, V.I. Rublinetsky, E.G. Kachko. Fundamentals of Programming, 1998
2. N. Christofides. Graph Theory: An Algorithmic Approach, Mir, 1978
3. F.A. Novikov. Discrete Mathematics for Programmers, Peter, 2001
4. V.A. Nosov. Combinatorics and graph theory, MSTU, 1999
5. O. Ore. Graph Theory, Science, 1982
Nomination "Glorious sons of the Motherland"
Topic: "Chulkov Alexey Petrovich - Hero Soviet Union»
Galiullin Ravil
MBOU "Yukhmachinskaya secondary comprehensive school named after the Hero of the Soviet Union Alexei Petrovich Chulkov"
7th grade student
Moskvina G.A.
1. Introduction.
2. Main body
2.1. Life and feat of A.P. Chulkova
2.2. Memory - perpetuation of the name of the Hero of the Soviet Union in memorial objects
3.Conclusion
4. List of used literature
1. Introduction
The Great Patriotic War is one of the most terrible ordeals that befell our people. The severity and bloodshed of the war left a big imprint in the minds of people. Patriotism at all times Russian state was a feature of the national character.
Every town and village has its own heroes who glorified our country. Unfortunately, in Lately it is said that the younger generation began to forget about the exploits of our grandfathers and great-grandfathers. And all around there are information outbursts, seeking once again to denigrate the feat of the Soviet people. Therefore, this topic of research work is relevant for solving such a problem as the education of a moral and patriotic personality. Our task is to remember the heroes, cherish this memory and pass it on to future generations.
The memory of the past... No, this is not just a property of human consciousness, its ability to retain traces of the past.
Memory is the link between the past and the future. No matter how many years pass, no matter how many centuries pass, we must remember with gratitude those who saved the world from the brown plague, and our people from death. And don't let history be rewritten.
Now, when in the West, in the former Soviet republics of the Baltic states, in Ukraine, the exploits of the soldiers of the Red Army are put on a par with service on the side of the Nazis, monuments are being erected to the SS men, we must again and again remember those who laid their lives on the altar of the Fatherland.
Objective of the project: to study the military path and the feat of the Hero of the Soviet Union, whose name our school bears.
Tasks:- to get acquainted with the algorithm of work on the project;
Examine all available literature and publications in the media on the research topic;
Analyze the information received and draw conclusions
The work is devoted to the study of the biography of Aleksey Petrovich Chulkov, a hero of the Soviet Union, who was born in the village of Yukhmachi, Tatar ASSR.
Hero of the Soviet Union Aleksey Petrovich Chulkov is our fellow countryman, our school in the village of Yukhmachi bears his name. Who was he, how did he live, what did he dream about, for which he was awarded the title of Hero of the Soviet Union?
After the end of the Great Patriotic War more than 70 years have passed. In the vastness of our Motherland, there are obelisks to the fallen, to those who did not return from the battlefields. They were young. When they managed to do so much that they were presented to the highest award Motherland? Why did they sacrifice themselves? Did they not want to survive?
The theme of my research work: The fate of my countryman.
I decided to explore this issue in more detail. To do this, I visited the school museum, where a section is dedicated to Alexei Petrovich. Also in my work, I relied on the memoirs of the Hero of the Soviet Union, General - Colonel Vasily Vasilyevich Reshetnikov, Wikipedia, as well as the book by Yu.N. Khudov "The Winged Commissar".
Methods: During the implementation of the project, I got acquainted with the algorithm for conducting research work, studied local history literature, looked through the available literature, Internet materials, and memoirs of a colleague.
Significance of the study: this material can be used in history lessons, when conducting extracurricular activities dedicated to memorable and anniversaries, museum lessons.
2. Main body
2.1. Life and feat of A.P. Chulkova
Chulkov Alexey Petrovich was born on April 30, 1908 in the village of Yukhmachi Russian Empire, now Alkeyevsky district of Tatarstan, in a working class family. Russian by nationality. In 1920, after being wounded at the front, his father died. Four children were left orphans. The elder Sergey, even earlier, left for Karabanovo, to his relatives, where he gets a job at a factory. Together with ten-year-old Alexei, his mother left two younger sisters - Olya and Polina. This year, a terrible drought broke out in the Volga region. There was a great famine. Lyosha gets a job as a farm laborer for a kulak, for meager food she grazes his herd. Once the owner beat Lyosha. And the boy, having said goodbye to his mother and sisters, decides to go to his brother in Karabanovo. Money for the road and food - not a penny. With a gang of the same street children, Lyosha makes his way towards Moscow. At the railway station in Kostroma, they got into another raid. So Alexei ended up in the Kostroma orphanage, where he completed the remaining two classes and with a certificate of completion elementary school arrived 14 years old arrived in Karabanovo
Since 1925 - a resident of the village of Karabanovo (now a city) Vladimir region. Here Alexei worked at the weaving factory of the 3rd International from 1927 to 1933. Here at the factory he met his future wife, Vera. With which Alexei Petrovich had four sons.
Member of the CPSU (b) / CPSU since 1931. He graduated from the workers' faculty and 1st year of the Moscow Pedagogical Institute. Worked in Moscow.
Drafted into the Red Army in 1933, in 1934 he graduated from the Lugansk military aviation school. He made his first sorties during the Soviet-Finnish war of 1939-1940, successfully participated in the bombing and air attack of the fortifications of the Mannerheim Line. The combat skill and skillful fruitful political work of the pilot, senior political officer Alexei Chulkov were highly appreciated by the command. He was awarded the Order of the Red Banner, he was awarded military rank battalion commissar.
In the battles of the Great Patriotic War from the first days. By November 1942, Major Aleksey Chulkov, deputy squadron commander for the political part of the 751st Aviation Regiment, made 114 sorties to bombard military-industrial facilities deep behind enemy lines and his troops at the forefront.
On November 7, 1942, while returning from a combat mission near the city of Orsha, his plane was hit by anti-aircraft fire and crashed near Kaluga.
In 2004, the book of Vasily Vasilyevich Reshetnikov, Hero of the Soviet Union, Colonel General, was published.
During the war, the pilot of the 751st regiment of the 17th air division of long-range bombers. In 1942 he fought in a squadron, the commissar of which was Chulkov. Repeatedly flew under his leadership on combat missions. Vasily Vasilyevich recalls his commissar as follows: That night, from the seventh to the eighth of November 1942, the crew of commissar Alexei Petrovich Chulkov did not return from a combat mission. Although he was the state commissar of the Uruta squadron, the entire regiment honored him as his commissar, causing involuntary jealousy among others, including regimental, but non-flying political workers.
This is a delicate thing - authority, especially the commissar's. The criteria of official position here do not work at all, even if they successfully provide the whole complex of external signs of reverence. In the firm price of respect, only the moral and intellectual scale of the individual is singled out. It is individuals, not positions. In the war, an act was valued, and if a word is then alive, and not dead-official.
Alexei Petrovich was far from a textbook commissar - and outwardly quite discreet, and certainly not a tribune. He was more famous as an excellent combat pilot, and, as I remember, he did not fool anyone either with reports or edifications. He was given a strong natural mind, kind soul and strong fighting spirit. He went through the Soviet-Finnish war as a faithful soldier of his Motherland and did not hesitate on the first day of the Great Patriotic War. Now the score of his sorties was in the second hundred. He flew on a par with us, like an ordinary ship commander, but he liked to take off first, or maybe he didn’t like it, not seeing tactical advantages in that, but he apparently considered the place ahead of the squadron to be his own.
Chulkov, after the bombing of the Orsha airfield, was already walking home and was half an hour away from his own, when they suddenly came under fire, a shell hit the right engine. He smoked, swelled, coughed, had to be turned off. The screw, unfortunately, continued to rotate, slipping became inevitable, and the car went with a slight decrease. There was very little height left to the front line, but Alexei Petrovich and his constant navigator Grigory Chumash found a base for our fighters in the Kaluga region and decided to land on the move.
At night, such airfields do not work and do not even have means of night landing, but the duty "T" bowls were on fire, and Alexei Petrovich went along the landing strip successfully, except perhaps with some flight. The airfield was tiny, for camouflage it was furnished with stacks, animal models, and when the plane was on its very edge, the gunners - radio operators, seeing this "rural landscape", shouted in one voice: "False airfield!" Aleksey Petrovich succumbed to the cry, and although in the next moment Chumash shouted: "Sit down!" - It was too late. The left engine at full throttle dragged the car further, but it was unable to regain the lost speed and height, and even with one landing gear that had not retracted. On a turn, outside the airfield, the plane touched the pine trees with its wing, fell to the ground and caught fire. The flames from the tanks crawled to the pilot's cabin. Chulkov was wounded and could not get up on his own. There it burned. The radio operator Dyakov also died in the fire. Overcoming pain from bruises and abrasions, gunner Glazunov got out through the turret ring, but he could not get through the fire to the commander. Grisha Chumash was thrown out of his broken navigational shell and, in the fall, broke his leg in two places. He crawled away from the fire, bandaged the bleeding wounds with shreds of linen and waited for help. She came from the airport. After numerous operations, the leg was noticeably shortened, and I had to say goodbye to flight work.
This is how our legendary commissar perished.
For a little over a year of the war, he made 119 sorties, 111 of them at night.
Bombed Berlin and other cities and military installations in Germany. Delivering bombing strikes, he supported our ground troops on the front line. At the cost of his life, bringing the hour of Victory closer.
In December, an order was read out at the formation of the regiment. There are these words:
For boundless devotion to the Motherland, for the good organization of the squadron's combat work, for personal courage and heroism in battle, despising death, the battalion commissar Chulkov is worthy of the highest government award of the title of "Hero of the Soviet Union" with the award of the Order of Lenin and the Gold Star medal - Posthumously
Buried in the city of Kaluga.
Awards
Decree of the Presidium of the Supreme Soviet of the USSR of December 31, 1942 Major Aleksey Petrovich Chulkov was posthumously awarded the title of Hero of the Soviet Union for his heroism and excellent performance of the combat missions of the command.
He was awarded two Orders of Lenin and two Orders of the Red Banner.
From the award list:
Major Chulkov works as deputy air squadron commander for political affairs. Flying on an Il-4 aircraft as part of a night crew, where the navigator is Captain Chumash, the gunner-radio operator is foreman Kozlovsky and the air gunner is Senior Sergeant Dyakov.
He has been in the active army since the first days of the Patriotic War. During this period, he made 114 combat sorties, 111 of them at night and all with excellent performance of a combat mission. He flew to bombard military-industrial facilities and political centers of the enemy in the rear: Berlin - 2 times, Budapest - 1 time, Danzig - 1 time, Königsberg - 1 time, Warsaw - 2 times.
For the excellent performance of the combat missions of the command to defeat German fascism, he was awarded the Order of Lenin and the Order of the Red Banner. After the award, he flew 55 sorties. Working as a military commissar of an air squadron, he proved himself excellently as an educator of personnel in the spirit of devotion to the Motherland and hatred of the enemy. During the fighting, his squadron made 951 sorties against the enemy. Comrade Chulkov to his personal example inspires subordinate personnel to exploits. Disciplined, demanding of himself and his subordinates. Among the personnel enjoys well-deserved prestige. He is devoted to the cause of Lenin's party and the socialist motherland.
For the excellent performance of the combat missions of the command to defeat German fascism and the courage and heroism shown at the same time, Major Chulkov is worthy of the government award of the Order of Lenin.
Commander 751 AP DD Hero of the Soviet Union
lieutenant colonel TIKHONOV November 4, 1942.
Conclusion of the Military Council.
Worthy of the government award of the title of Hero of the Soviet Union.
Air Commander Member of the Military Council
long-range aviation
Aviation General GOLOVANOV
divisional commissar GURYANOV
November 30, 1942
2.2. Memory - perpetuation of the name of the Hero of the Soviet Union in memorial objects
Memorial of Glory on Poklonnaya Hill in Moscow
Memorial complex of Kaluga
The name of the Hero is a street in the city of Karabanovo, Vladimir Region.
In 2004, V.V. Reshetnikov’s book “What was - it was” was published, which refers to Chulkov.
The documentary story "The Winged Commissar" by Yu.N. Khudov
In 2000, our school was named after the Hero-Countryman.
The director of our school is a relative of Chulkov Alexei Petrovich Chulkov Petr Alexandrovich. In many respects, thanks to his activities, our school bears the name of the Hero. Pyotr Alexandrovich himself is a worthy son of the Fatherland. In 1983 he was drafted into the Armed Forces of the USSR. He served in the Republic of Afghanistan, the commander of the guard platoon of a separate motorized rifle escort. He and his comrades accompanied the columns of KAMAZ trucks with cargo. Once the column came under fire, and Pyotr Aleksandrovich was wounded.
Chulkov Petr Alexandrovich was awarded: the star "Participant Afghan war”, the order badge “Warrior - Internationalist”, the medal “From the grateful Afghan people”, the Diploma of the Presidium of the Supreme Soviet of the USSR “For courage and military prowess”.
He is distinguished by modesty, responsibility, rigor, elegance. He is a talented leader and organizer of pedagogical and student teams. Under his leadership, the school is one of the top school district.
Exposition in the school museum of Yukhmachi village
Victory Park in Kazan
Monument dedicated to Chulkov A.P. in the village of Yukhmachi, in the homeland of the Hero.
V.V. Reshetnikov with granddaughter Chulkov A.P. Elena Shusharina. Moscow 2007.
3.Conclusion
Life and feat, we often hear these words. A simple man from the outback, who was 34 years old, turned out to be a real hero of the war, bloody battles. A.P. Chulkov became a Hero for a reason, he was a real person, brought up by his family, the Motherland.
Work on materials about the Hero contributed to the definition of spiritual guidelines, moral values, universal priorities, the formation of patriotic consciousness, as one of the most important values and foundations of spiritual and moral unity.
And it becomes clear the need to participate in business Russian movement schoolchildren, of which I am a member. This is a public-state children's and youth organization, formed by the decision of the constituent assembly of March 28, 2016 at Moscow University named after M.V. Lomonosov. In accordance with the Decree of the President of the Russian Federation of October 29, 2015. RDSH works in the following areas: - military-patriotic - "Yunarmiya"
Civic activism (volunteering, search work, study of history, local history)
Information and media.
4. References:
1.V.V. Reshetnikov “What was, it was”, M., 2004.
2. Yu.N. Hudov "The Winged Commissar"
3. Materials of the school museum of Yukhmachi village
4. Photo from the personal archive of Chulkov P.A.
5.http://ru.wikipedia.org
Participant Application Form
Republican competition of projects “History glorious pages.
School of Heroes "for students in grades 5-7 of general education
Organizations of the Republic of Tatarstan bearing the name of the Hero
Territory Republic of Tatarstan, Alkeyevsky district, Yukhmachi village
Nomination "Glorious sons of the Fatherland"
Name, surname of the participant Ravil Galiullin
Date of Birth 05. 01.2005
Age group 7th grade
Full name of the educational organization MBOU "Yukhmachinskaya secondary school named after Hero of the Soviet Union Chulkov Alexei Petrovich"Yukhmachi village, st. School, house 10 a
Phone number 89276781352
E-mail [email protected]
Name of the teacher (in full) Moskvina Galina Alexandrovna
Teacher's contact number 89270389187
Consent to the processing of personal data
I, Shubina Tatyana Nikolaevna, the passport 9200097914
, issued ATC of the Aircraft Building District of Kazan, 01.11.2002________________________________________________________
(when, by whom)
Republic of Tatarstan, Alkeyevsky district, Yukhmachi village, st. School 4.
____________________________________________________________________________________________________________________
I consent to the processing of my child's personal data Galiullina Ravil Rashitovich
Republic of Tatarstan, Alkeyevsky district, Yukhmachi village, st. School 4.
operator of the Ministry of Education and Science of the Republic of Tatarstan to participate in the competition.
The list of personal data for which consent is given: last name, first name, patronymic, school, class, home address, date of birth, phone number, address Email, the results of participation in the final stage of the competition.
The operator has the right to collect, systematize, accumulate, store, clarify, use, transfer personal data to third parties - educational organizations, educational authorities of districts (cities), the Ministry of Education and Science of the Republic of Tatarstan, the Ministry of Education of the Russian Federation, other legal entities and individuals responsible for organizing and conducting various stages of the competition, depersonalization, blocking, destruction of personal data.
With this application, I authorize to consider publicly available, including posting on the Internet, the following personal data of my child: last name, first name, class, school, preschool, result final stage competition, as well as the publication in the public domain of a scanned copy of the work.
The processing of personal data is carried out in accordance with the norms of the Federal Law Russian Federation dated July 27, 2006 No. 152-FZ "On Personal Data".
This Consent comes into force from the date of its signing and is valid for 3 years.
______________________ _____________________________ (personal signature, date)
Kuchin Anatoly Nikolaevich
Project Manager:
Kuklina Tatyana Ivanovna
Institution:
MBOU "Basic Comprehensive School" Troitsko-Pechorsk Resp. Komi
In his research work in mathematics "In the world of graphs" I will try to find out the features of the application of graph theory in solving problems and in practical activities. The result of my research work in mathematics about graphs will be the genealogical tree of my family.
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, consider methods for solving problems using graphs.
Also, in a research project on mathematics about graphs, I will show the application of graph theory in various areas of human life.
Introduction
Chapter 1
1.1. History of graphs.
1.2. Types of graphs
Chapter 2 Everyday life
2.1. The use of graphs in various areas of people's lives
2.2. The use of graphs in solving problems
2.3. The family tree is one way to apply graph theory
2.4. Study Description and Compilation family tree my family
Conclusion
References
Applications
“In mathematics, it is not formulas to remember,
but the process of thinking.
E.I. Ignatieva
Introduction
Graphs are everywhere! In my research work in mathematics on the topic "In the world of graphs" we will talk about graphs, which, to the aristocrats of the past, have nothing to do. "" 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 at the decision olympiad tasks mathematics. Difficulties in solving these problems were explained by the absence of this topic in the compulsory course. school curriculum. The problem has become main reason choice of 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.
In mathematics, there is even a special section, which is called: “ graph theory". Graph theory is part of how topology, and combinatorics. The fact that this is a topological theory follows from the independence of the properties of a 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 mind numerous facts given in a condition, to establish a connection between them, to express hypotheses, to draw particular conclusions and use them.
Find out the features of the application of graph theory in solving problems and in practical activities.
Object of study is a mathematical graph.
Subject of study are graphs as a way to solve a number of practical problems.
Hypothesis: if the method of graphs is so important, then there is bound to be one wide application in various fields of science and human life.
To achieve this goal, I have 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. the fields of science and human life are written out, in which the graph method is used;
3. the solution of problems with the help of graph theory is considered;
4. studied the method of compiling the genealogical 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 finds application in various areas of modern mathematics and its numerous applications, especially in economics, technology, and management. The solution of many mathematical problems is simplified if you can use graphs. The presentation of data in the form of a graph gives them clarity and simplicity. Many mathematical proofs are also simplified and become more convincing if graphs are used.
To make sure of this, my supervisor and I proposed to students in grades 5-9, participants in the school and municipal tours All-Russian Olympiad schoolchildren, 4 tasks, in the solution of which graph theory can be applied ( Attachment 1).
The results of solving problems are as follows:
A total of 15 students (grade 5 - 3 students, grade 6 - 2 students, grade 7 - 3 students, grade 8 - 3 students, grade 9 - 4 students) applied graph theory in problem 1 - 1, in problem 2 - 0, in Task 3 - 6, task 4 - 4 students.
Practical significance research is that the results will undoubtedly arouse the interest of many people. Haven't any of you tried to build a family tree of your family? And how to do it correctly?
It turns out they are solved with the help of graphs easily.
Municipal general 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 how to build graphs.
2) Select the types of problems, the solution of which requires the application of graph theory.
3) Explore the use of graphs in mathematics.
"Euler calculated without any apparent effort how a person breathes or how an eagle soars above the earth."
Dominic Arago.
I. Introduction. page
II . Main part.
1. The concept of a graph. The problem of the Königsberg bridges. page
2. Properties of graphs. page
3. Problems using graph theory. page
Sh. Conclusion.
The meaning of graphs. page
IV. Bibliography. page
I . INTRODUCTION
Graph theory is a relatively young science. "Counts" is derived from the Greek word "grapho", which means "I write". The same root in the words "graph", "biography".
In my work, I consider 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 word problems in algebra. Having explored the possibility of applying graph theory in school course mathematics, I came to the conclusion that this theory greatly simplifies the understanding and solution of 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 the 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 river Pregolya 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 once a resident of the city asked his friend if he could cross all the bridges so that he would visit each of them only once and return to the place where the walk began. Many citizens became interested in this problem, but no one could come up with a solution. This question 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 merits are enormous. He influenced the development of almost all branches of mathematics and mechanics, both in the field of fundamental research and in their applications. Leonhard Euler not only solved this particular problem, but also came up with general method solutions to these problems. Euler acted as follows: 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 the edges of the graph. Pictured from the tops B, C, D 3 edges go out, and from the top A - 5 ribs. Vertices from which an odd number of edges emerge are calledodd peaks, and the vertices from which an even number of edges emerge -even.
2.Properties of the graph.
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 in one stroke. The movement must start from any odd vertex, and end at another odd vertex.
3. A graph with more than two odd vertices cannot be drawn in one stroke.
4. The number of odd graph vertices is always even.
5. If there are odd vertices in the graph, 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 ones, then it can be drawn with at least two strokes.
In the seven Königsberg bridge problem, all four vertices of the corresponding graph are odd, i.e. you cannot cross all the bridges once and end up where you started.
3. Problem solving using graphs.
1. Tasks for drawing figures in one stroke.
Attempts to draw each of the following figures with a single stroke of the pen lead to unequal 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 the figure has only one pair of odd points, then such a figure can be drawn in one stroke, starting drawing at one of the odd points (it doesn’t matter which one). It is easy to figure out 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 in one stroke at all. These are figures 4 and 7, containing two pairs of odd points. What has been said is enough to unmistakably recognize which figures cannot be drawn with one stroke and which ones can, and also from what point one should start drawing.
I propose to draw the following figures in one stroke.
2. Solving logical problems.
TASK #1.
There are 6 participants in the table tennis class championship: Andrey, Boris, Viktor, Galina, Dmitry and Elena. The championship is held in a round-robin system - each of the participants plays with 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.
Played 7 games.
In this picture, the graph has 8 edges, so there are 8 games left to play.
TASK #2
In the yard, which is surrounded by a high fence, there are three houses: red, yellow and blue. There are three gates in the fence: 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 one to the blue one so that these paths do not intersect.
SOLUTION:
The solution of the problem is shown in the figure.
3. Solving text problems.
To solve problems using the graph method, you need to know the following algorithm:
1.About what process in question in a task?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 2 hours at a speed of 45 km/h and 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 \u003d 90 (km) - the bus passed in 2 hours.
2)60x 3 \u003d 180 (km) - the bus passed in 3 hours.
3) 90 + 180 = 270 (km) - the bus passed 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, he solved problems using graph theory. For myself, I concluded that graph theory finds application in various areas of modern mathematics and its many applications. There is no doubt about the usefulness of introducing us students to the basic concepts of graph theory. The solution of many mathematical problems is simplified if you can use graphs. Data representation in the form of a graph gives them visibility. Many proofs are also simplified and become more convincing if graphs are used. This applies in particular to such areas of mathematics as mathematical logic and combinatorics.
Thus, the study of this topic is of great general educational, general cultural and general mathematical significance. In everyday life, graphic illustrations, geometric representations and other visualization techniques and methods are increasingly used. For this purpose, it is useful to introduce the study of elements of graph theory in primary and secondary school, at least in extracurricular activities, since this topic is not included in the mathematics curriculum.
V . BIBLIOGRAPHY:
2008
Review.
The project on the topic "Counts around us" was completed by a student of 7 "A" class MOU-sosh No. 3g. Krasny Kut Zaitsev Nikita.
Distinctive feature The work of Zaitsev Nikita is its relevance, practical orientation, depth of disclosure of the topic, the possibility of using it in the future.
The work is creative information project. The student chose this topic to show the relationship between graph theory and practice using the example of a school bus route, to show that graph theory finds application in various areas of modern mathematics and its many applications, especially economics, mathematical logic, and combinatorics. He showed that the solution of problems is greatly simplified if it is possible to use graphs, the presentation of data in the form of a graph gives them visibility, many proofs are also simplified and become convincing.
The work addresses issues such as:
1. The concept of a graph. The problem of the Königsberg bridges.
2. Properties of graphs.
3. Problems using graph theory.
4. Meaning of graphs.
5. School bus route option.
When doing his work, N. Zaitsev used:
1. Alkhova Z.N., Makeeva A.V. " Extracurricular work mathematics".
2. Journal "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 relevant drawings are attached.
The text of the work is placed without images and formulas.
Full version work is available in the "Files of work" tab in PDF format
“In mathematics, it is not the formulas that should be remembered, but the process of thinking ...”
E. I. Ignatiev
Graph theory is currently an intensively developing branch of mathematics. This is explained by the fact that many objects and situations are described in the form of graph models, which is very important for the normal functioning of social life. It is this factor that determines the relevance of their more detailed study. Therefore, the topic of this work is quite relevant.
Target research work: to find out the features of the application of graph theory in various fields of knowledge and in solving logical problems.
The goal has identified the following tasks:
learn about the history of graph theory;
study the basic concepts of graph theory and the main characteristics of graphs;
show the practical application of graph theory in various fields of knowledge;
consider ways to solve problems using graphs and create your own problems.
An object research: the scope of human activity for the application of the graph method.
Subject research: section of mathematics "Graph Theory".
Hypothesis. We assume that the study of graph theory can help students solve logical problems in mathematics, which will determine their future interests.
Methods research work:
In the course of our study, the following methods were used:
1) Working with various sources of information.
2) Description, collection, systematization of the material.
3) Observation, analysis and comparison.
4) Drawing up tasks.
Theoretical and practical significance of this work is determined by the fact that the results can be used in computer science, mathematics, geometry, drawing and classroom hours, as well as for a wide range of readers interested in this topic. Research has a pronounced practical orientation, since the author presents numerous examples of the use of graphs in many fields of knowledge, and formulated his own tasks. This material can be used in optional math classes.
CHAPTER I. THEORETICAL REVIEW OF THE MATERIAL ON THE TOPIC OF THE RESEARCH
Graph theory. Basic concepts
In mathematics, a "graph" can be represented as a picture, which is a number of points connected by lines. "Count" comes from the Latin word "graphio" - I write, like the well-known title of nobility.
In mathematics, the definition of a graph is given as follows:
The term "graph" in mathematics is defined as follows:
Graph is a finite set of points - peaks, which can be connected by lines - ribs .
Examples of graphs include drawings of polygons, electrical circuits, a schematic representation of airlines, subways, roads, etc. A genealogical tree is also a graph, where genus members serve as vertices, and family ties act as graph edges.
Rice. one Graph Examples
The number of edges that belong to one vertex is called graph vertex degree . If the degree of a vertex is an odd number, the vertex is called - odd . If the degree of a vertex is even, then the vertex is called even.
Rice. 2 Top of the graph
null graph is a graph consisting only of isolated vertices not connected by edges.
Complete graph is a graph, each pair of vertices of which is connected by an edge. An N-gon containing all diagonals is an example of a complete graph.
If we choose a path in the graph where the start and end points are the same, then such a path is called graph cycle . If the passage through each vertex of the graph occurs at most once, then cycle called simple .
If every two vertices in a graph are connected by an edge, then connected graph. The count is called unrelated if it has at least one pair of unconnected vertices.
If a graph is connected but does not contain cycles, then such a graph is called tree .
Graph Characteristics
Count's way is a sequence in which every two adjacent edges that have one common vertex occur only once.
The length of the shortest chain of vertices a and b is called distance between peaks a and b.
Vertex but called center graph if the distance between the vertex but and any other vertex is the smallest possible one. Such a distance is radius graph.
The maximum possible distance between any two vertices of a graph is called diameter graph.
Graph coloring and application.
If you look closely at geographical map, then you can see the railways or highways, which are graphs. In addition, there is a graph on the katra, which consists of borders between countries (districts, regions).
In 1852, English student Francis Guthrie was given the task of coloring a map of Great Britain, highlighting each county in a separate color. Due to the small selection of paints, Guthrie reused them. He chose the colors so that those counties that have a common section of the border were necessarily painted in different colors. The question arose, what is the smallest number of colors needed to color various maps. Francis Guthrie suggested, though he could not prove, that four colors would suffice. This problem was vigorously discussed in student circles, but was later forgotten.
The "Four Color Problem" was of increasing interest, but was never solved, even by eminent mathematicians. In 1890, the English mathematician Percy Heawood proved that five colors would be enough to color any map. And only in 1968 they were able to prove that 4 colors would be enough to color a map that shows less than forty countries.
In 1976, this problem was solved using a computer by two American mathematicians Kenneth Appel and Wolfgant Haken. To solve it, all cards were divided into 2000 types. A program was created for the computer that examined all types in order to identify such cards for coloring which four colors would not be enough. Only three types of maps could not be investigated by the computer, so mathematicians studied them on their own. As a result, it was found that 4 colors will be enough to color all 2000 types of cards. They announced a solution to the problem of four colors. On this day, the post office at the university, where Appel and Haken worked, put a stamp on all stamps with the words: "Four colors are enough."
The problem of four colors can be presented in a slightly different way.
To do this, consider an arbitrary map, presenting it as a graph: the capitals of states are the vertices of the graph, and the edges of the graph connect those vertices (capitals) whose states have common border. To obtain such a graph, the following problem is formulated - it is necessary to color the graph using four colors so that the vertices that have a common edge are colored with different colors.
Euler and Hamilton graphs
In 1859, the English mathematician William Hamilton released a puzzle for sale - a wooden dodecahedron (dodecahedron), twenty vertices of which were marked with carnations. Each peak had the name of one of the largest cities in the world - Canton, Delhi, Brussels, etc. The task was to find a closed path that goes along the edges of the polyhedron, having visited each vertex only once. To mark the path, a cord was used, which was clung to carnations.
A Hamiltonian cycle is a graph whose path is a simple cycle that passes through all the vertices of the graph once.
The city of Kaliningrad (formerly Koenigsberg) is located on the Pregel River. The river washed two islands, which were connected to each other and to the banks by bridges. The old bridges no longer exist. The memory of them remained only on the map of the city.
One day, a resident of the city asked his friend if it was possible to go through all the bridges, visit each one only once and return to the place where the walk began. This problem interested many townspeople, but no one could solve it. This question aroused the interest of scientists from many countries. The problem was solved by the mathematician Leonhard Euler. In addition, he formulated a general approach to solving such problems. To do this, he turned the map into a graph. The land became the vertices of this graph, and the bridges connecting it became the edges.
When solving the Königsberg bridge problem, Euler succeeded in formulating the properties of graphs.
It is possible to draw a graph, starting from one vertex and ending at the same vertex with one stroke (without drawing twice along the same line and without lifting the pencil from the paper) if all the vertices of the graph are even.
If there is a graph with two odd vertices, then its vertices can also be connected with one stroke. To do this, you need to start from one, and end at another, any odd vertex.
If there is a graph with more than two odd vertices, then the graph cannot be drawn in one stroke.
If we apply these properties to the bridge problem, then we can see that all the vertices of the graph under study are odd, which means that this graph cannot be connected with one stroke, i.e. it is impossible to cross all the bridges once and end the journey in the place where it started.
If a graph has a cycle (not necessarily a simple one) containing all the edges of the graph once, then such a cycle is called Euler cycle . Euler chain (path, cycle, contour) is a chain (path, cycle, contour) containing all the edges (arcs) of the graph once.
CHAPTER II. DESCRIPTION OF THE STUDY AND ITS RESULTS
2.1. Stages of the study
To test the hypothesis, the study included three stages (Table 1):
Research stages
Table 1.
|
Methods Used |
|||
|
Theoretical study of the problem |
To study and analyze cognitive and scientific literature. |
- independent thinking; study of information sources; - searching for the necessary literature. |
|
|
Practical research Problems |
Review and analyze areas practical application counts; |
- observation; - analysis; - comparison; - questioning. |
|
|
Stage 3. Practical use of the results |
Summarize the learned information; |
- systematization; report (oral, written, with demonstration of materials) |
September 2017 |
2.2. Areas of practical application of graphs
Graphs and information
Information theory makes extensive use of the properties of binary trees.
For example, if you need to encode a certain number of messages in the form of certain sequences of zeros and ones of various lengths. The code is considered the best, for a given probability of code words, if the average word length is the smallest in comparison with other probability distributions. To solve such a problem, Huffman proposed an algorithm in which the code is represented by a graph tree in the framework of search theory. For each vertex, a question is proposed, the answer to which can be either "yes" or "no" - which corresponds to two edges coming out of the vertex. The construction of such a tree is completed after establishing what was required. This can be applied in multi-person interviews where the answer to the previous question is not known in advance, the interview plan is presented as a binary tree.
Graphs and chemistry
Even A. Cayley considered the problem of possible structures of saturated (or saturated) hydrocarbons, the molecules of which are given by the formula:
C&H 2n+2
All hydrocarbon atoms are 4-valent, all hydrogen atoms are 1-valent. The structural formulas of the simplest hydrocarbons are shown in the figure.
Every molecule saturated hydrocarbon can be represented as a tree. When all hydrogen atoms are removed, the hydrocarbon atoms that remain form a tree with vertices whose degree is not higher than four. This means that the number of possible desired structures (homologues of a given substance) is equal to the number of trees whose vertex degrees are at most 4. This problem is reduced to the problem of listing trees of a particular type. D. Poya considered this problem and its generalizations.
Graphs and biology
The process of bacterial reproduction is one of the varieties of branching processes found in biological theory. Let each bacterium, after a certain time, either die or divide into two. Therefore, for one bacterium, we get a binary tree of reproduction of its offspring. The question of the problem is the following, how many cases does k descendants in the nth generation of one bacterium? This ratio in biology is called the Galton-Watson process, which denotes the required number of necessary cases.
Graphs and physics
A difficult tedious task for any radio amateur is the creation of printed circuits (a dielectric plate - an insulating material and etched tracks in the form of metal strips). The intersection of tracks occurs only at certain points (places where triodes, resistors, diodes, etc. are installed) according to certain rules. As a result, the scientist is faced with the task of drawing a planar graph, with vertices in
So, all of the above confirms the practical value of graphs.
Internet mathematics
Internet - world system United computer networks for storage and transmission of information.
The Internet can be represented as a graph, where the vertices of the graph are Internet sites, and the edges are links (hyperlinks) going from one site to another.
The web graph (Internet), which has billions of vertices and edges, is constantly changing - sites are added and disappear spontaneously, links disappear and are added. However, the Internet has a mathematical structure, obeys graph theory, and has several "stable" properties.
The web graph is sparse. It contains only a few times more edges than vertices.
Despite the sparseness, the Internet is very small. From one site to another using links, you can go in 5 - 6 clicks (the famous theory of "six handshakes").
As we know, the degree of a graph is the number of edges that a vertex belongs to. The degrees of web graph vertices are distributed according to a certain law: the proportion of sites (vertices) with a large number of links (edges) is small, and sites with a small number of links is large. Mathematically, this can be written as:
where is the proportion of vertices of a certain degree, is the degree of a vertex, is a constant independent of the number of vertices in the web graph, i.e. does not change in the process of adding or removing sites (vertices).
This power law is universal for complex networks - from biological to interbank.
The Internet as a whole is resistant to random attacks on sites.
Since the destruction and creation of sites occurs independently and with the same probability, then the web graph, with a probability close to 1, retains its integrity and is not destroyed.
To study the Internet, it is necessary to build a random graph model. This model should have the properties of the real Internet and should not be too complex.
This problem has not yet been completely solved! Solving this problem - building a qualitative model of the Internet - will allow us to develop new tools to improve information retrieval, spam detection, and information dissemination.
The construction of biological and economic models began much earlier than the task of constructing mathematical model the Internet. However, advances in the development and study of the Internet have made it possible to answer many questions regarding all these models.
Internet mathematics is in demand by many specialists: biologists (predicting the growth of bacterial populations), financiers (risks of crises), etc. The study of such systems is one of the central sections of applied mathematics and informatics.
Murmansk with the help of the graph.
When a person arrives in a new city, as a rule, the first desire is to visit the main attractions. But at the same time, the time reserve is often limited, and in the case of a business trip, it is very small. Therefore, it is necessary to plan sightseeing in advance. And the graphs will help in building the route!
As an example, consider a typical case of arrival in Murmansk from the airport for the first time. The following attractions are planned to be visited:
1. Marine Orthodox Church of the Savior on the Waters;
2. St. Nicholas Cathedral;
3. Oceanarium;
4. Monument to the cat Semyon;
5. nuclear icebreaker Lenin;
6. Park Lights of Murmansk;
7. Park Valley of Comfort;
8. Kola bridge;
9. Museum of the History of the Murmansk Shipping Company;
10. Square of the Five Corners;
11. Sea trading port
First, we will place these places on the map and get a visual representation of the location and distance between the attractions. The road network is quite developed, and moving by car will not be difficult.
Attractions on the map (left) and the resulting graph (right) are shown in the corresponding figure in APPENDIX #1. Thus, the newcomer will first pass near the Kola Bridge (and, if desired, can cross it back and forth); then he will have a rest in the Park of Lights of Murmansk and the Valley of Comfort and go further. As a result, the optimal route will be:
With the help of the graph, you can also visualize the scheme of conducting opinion polls. Examples are presented in APPENDIX #2. Depending on these answers, the respondent is asked different questions. For example, if in sociological survey No. 1, the respondent considers mathematics the most important of the sciences, he will be asked if he feels confident in physics lessons; if he thinks otherwise, the second question will concern the demand humanities. The vertices of such a graph are the questions, and the edges are the answers.
2.3. Application of graph theory in solving problems
Graph theory is used to solve problems from many subject areas Keywords: mathematics, biology, informatics. We studied the principle of solving problems using graph theory and made up our own problems on the topic of research.
Task number 1.
Five classmates, at the reunion of graduates, shook hands. How many handshakes were made in total?
Solution: Denote classmates as graph vertices. Connect each vertex with lines to four other vertices. We get 10 lines, this is the handshake.
Answer: 10 handshakes (each line means one handshake).
Task number 2.
My grandmother in the village, near the house, grows 8 trees: poplar, oak, maple, apple, larch, birch, mountain ash and pine. Rowan is higher than larch, apple 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. In what order will the trees be arranged in height from highest to lowest?
Solution:
Trees are the vertices of a graph. We denote them by the first letter in the circle. Let's draw arrows from a low tree to a higher one. It is said that the mountain ash is higher than the larch, then we put the arrow from the larch to the mountain ash, the birch is lower than the poplar, then we put the arrow from the poplar to the birch, etc. We get a graph where it is clear that the lowest tree is maple, then apple, larch, mountain ash, pine, oak, birch and poplar.
Answer: maple, apple, larch, rowan, pine, oak, birch and poplar.
Task number 3.
Mom has 2 envelopes: regular and air, and 3 stamps: square, rectangular and triangular. In how many ways can Mom choose an envelope and a stamp to send a letter to Dad?
Answer: 6 ways
Task number 4.
Between settlements A, B, C, D, E roads are built. It is necessary to determine the length of the shortest path between points A and E. You can only move along the roads, the length of which is indicated in the figure.
Task number 5.
Three classmates - Maxim, Kirill and Vova decided to go in for sports and passed the selection of sports sections. It is known that 1 boy applied for the basketball section, and three wanted to play hockey. Maxim tried out only in 1 section, Kirill was selected for all three sections, and Vova in 2. Which of the boys was selected for which sports section?
Solution: To solve the problem, we use the graphs
Basketball Maxim
Football Kirill
Hockey Vova
Since to basketball there is only one arrow, then Cyril was taken to the section basketball. Then Cyril will not play hockey, which means in hockey section was selected by Maxim, who auditioned only for this section, then Vova will soccer player.
Task number 6.
Due to the illness of some teachers, the head teacher of the school is required to draw up a fragment of the school schedule for at least one day, taking into account the following circumstances:
1. The life safety teacher agrees to give only the last lesson;
2. The geography teacher can give either the second or the third lesson;
3. The mathematician is ready to give either only the first or only the second lesson;
4. A physics teacher can give either the first, or the second, or the third lesson, but only in one class.
What schedule can the head teacher of the school draw up so that it satisfies all teachers?
Solution: This problem can be solved by sorting through all possible options, but it's easier if you draw a graph.
1. 1) physics 2. 1) mathematics 3. 1) mathematics
2) mathematics 2) physics 2) geography
3) geography 3) geography 3) physics
4) OBZH 4) OBZH 4) OBZH
Conclusion
In this research work, the theory of graphs was studied in detail, the hypothesis was proved that the study of graphs can help in solving logical problems, in addition, the theory of graphs in different areas science and compiled their 7 tasks.
The use of graphs in teaching students to find solutions to problems allows you to improve the graphic skills of students and connect reasoning special language a finite set of points, some of which are connected by lines. All this contributes to the work of teaching students to think.
Efficiency learning activities on the development of thinking largely depends on the degree of creative activity of students in solving mathematical problems. Therefore, mathematical tasks and exercises are needed that would intensify the mental activity of schoolchildren.
The application of tasks and the use of elements of graph theory in extracurricular activities at school is precisely aimed at enhancing the mental activity of students. We believe that the practical material on our research can be useful in extracurricular classes in mathematics.
Thus, the purpose of the research work is achieved, the tasks are solved. In the future, we plan to continue studying the theory of graphs and develop our own routes, for example, with the help of a graph, create an excursion route for the school bus of ZATO Aleksandrovsk to museums and memorable places in Murmansk.
LIST OF USED LITERATURE
Berezina L. Yu. "Graphs and their application" - M .: "Enlightenment", 1979
Gardner M. "Mathematical leisure", M. "Mir", 1972
Gardner M. "Mathematical puzzles and entertainment", M. "Mir", 1971
Gorbachev A. "Collection of Olympiad problems" - M. MTsNMO, 2005
Zykov A. A. Fundamentals of graph theory. - M .: "University book", 2004. - S. 664
Kasatkin V. N. "Unusual problems of mathematics", Kyiv, "Radyan's school", 1987
Mathematical component / Editors-compilers N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M.: Foundation "Mathematical Etudes" 2015 - 151 p.
Melnikov O. I. "Entertaining problems in graph theory", Mn. TetraSystems, 2001
Melnikov O.I. Know-nothing in the country of graphs: A guide for students. Ed. 3rd, stereotypical. M.: KomKniga, 2007. - 160 p.
Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "Old entertaining problems", M. "Nauka", 1988
Ore O. "Graphs and their applications", M. "Mir", 1965
Harari F. Theory of Graphs / Translation from English. and foreword. V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2nd. - M.: Editorial URSS, 2003. - 296 p.
APPENDIX №1
Making the best itinerary for visiting the main attractions
Murmansk with the help of the graph.
The optimal route will be:
8. Kola bridge6. Park Lights of Murmansk7. Park Valley of Comfort 2. St. Nicholas Cathedral10. Five Corners Square5. Nuclear icebreaker Lenin9. Museum of the History of the Murmansk Shipping Company11. Sea trade port1. Marine Orthodox Church of the Savior on the Waters4. Monument to the cat Semyon3. Oceanarium.
GUIDE TO THE SIGHTS OF MURMANSK
APPENDIX №2
Sociological surveys No. 1, 2
