Project research work "graph theory". Research work on the topic "Graphs"1.ppt - Research work on the topic "Graphs" This year I took part in the distance Olympiad in mathematics. It proposed the following task
Nomination "Fatherland's Glorious Sons"
Topic: “Alexey Petrovich Chulkov - Hero of the Soviet Union”
Galiullin Ravil
MBOU "Yukhmachinskaya secondary school named after Hero of the Soviet Union Aleksey Petrovich Chulkov"
7th grade student
Moskvina G.A.
1. Introduction.
2. Main part
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 references used
1. Introduction
The Great Patriotic War is one of the most terrible trials that befell our people. The severity and bloodshed of the war left a big imprint on people's minds. Patriotism has always been a national character trait in the Russian state.
Every town and village has its own heroes who glorified our country. Unfortunately, recently it has been said that the younger generation has begun to forget about the exploits of our grandfathers and great-grandfathers. And all around there are information surges, 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 subsequent generations.
Memory of the past... No, this is not just a property of human consciousness, its ability to preserve traces of the past.
Memory is the link between the past and the future. No matter how many years have passed, no matter how many centuries have passed, we must remember with gratitude those who saved the world from the brown plague, and our people from destruction. And don't let history be rewritten.
Now, when in the West, in the former Soviet republics of the Baltic states and in Ukraine, the exploits of Red Army soldiers are put on a par with service on the side of the Nazis, and monuments are erected to SS men, we must remember again and again those who laid down their lives on the altar of the Fatherland.
Objective of the project: study the military path and feat of the Hero of the Soviet Union, whose name our school bears.
Tasks:- get acquainted with the algorithm for working on the project;
Study all available literature and media publications 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, born in the village of Yukhmachi, Tatar Autonomous Soviet Socialist Republic.
Hero of the Soviet Union Alexey Petrovich Chulkov is our fellow countryman, our school in the village of Yukhmachi bears his name. Who is he, how did he live, what did he dream about, why was he awarded the title of Hero of the Soviet Union?
More than 70 years have passed since the end of the Great Patriotic War. 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 did they manage to do so much that they were nominated for the highest award of the Motherland? Why did they sacrifice themselves? Didn't they really want to survive?
The topic of my research work: The fate of my fellow countryman.
I decided to cover this question 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 became acquainted with the algorithm for conducting research work, studied local history literature, looked through the available literature, Internet materials, and the memories of a colleague.
Significance of the study: this material can be used in history lessons, during extracurricular activities dedicated to memorable dates and anniversaries, and museum lessons.
2. Main part
2.1. Life and feat of A.P. Chulkova
Chulkov Alexey Petrovich was born on April 30, 1908 in the village of Yukhmachi of the Russian Empire, now the Alkeevsky district of Tatarstan, into a working-class family. Russian by nationality. In 1920, after being wounded at the front, his father dies. Four children were left orphans. The eldest Sergei, even earlier, left for Karabanovo, to visit 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. A great famine began. Lyosha gets a job as a farm laborer for a kulak, tending his flock for meager food. One day the owner beat Lesha. And the boy, having said goodbye to his mother and sisters, decides to go to his brother in Karabanovo. Money for travel and food - not a penny. With a gang of the same street children, Lyosha makes his way towards Moscow. At the station in Kostroma we were caught in another raid. So Alexey ended up in the Kostroma orphanage, where he completed the remaining two classes and, with a certificate of completion of primary school, arrived at the age of 14 and came to Karabanovo
Since 1925 - resident of the village of Karabanovo (now a city) in the Vladimir region. Here Alexey worked at the weaving factory of the 3rd International from 1927 to 1933. Here at the factory he met his future wife Vera. With whom Alexei Petrovich had four sons.
Member of the CPSU(b)/CPSU since 1931. Graduated from the workers' faculty and 1st year of the Moscow Pedagogical Institute. Worked in Moscow.
Drafted into the Red Army in 1933, he graduated from the Lugansk Military Aviation School in 1934. He made his first combat missions during the Soviet-Finnish War of 1939-1940, and 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 instructor Alexei Chulkov were highly appreciated by the command. He was awarded the Order of the Red Banner and was given the military rank of battalion commissar.
In the battles of the Great Patriotic War from the first days. By November 1942, the deputy squadron commander for political affairs of the 751st Air Regiment, Major Alexey Chulkov, made 114 combat missions to bomb military-industrial facilities deep behind enemy lines and his troops on the front line.
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 in the Kaluga area.
In 2004, a book by Vasily Vasilyevich Reshetnikov, Hero of the Soviet Union, Colonel General, was published.
During the war, he was a pilot of the 751st regiment of the 17th long-range bomber air division. In 1942 he fought in the squadron, of which Chulkov was the commissar. He repeatedly flew under his leadership on combat missions. Vasily Vasilyevich remembers his commissar this way: 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 commissar of the Uruta squadron, the entire regiment revered him as their commissar, causing involuntary jealousy among others, including the regimental, but non-flying political workers.
This is a subtle thing - authority, especially commissar authority. The criteria for official position do not work here at all, even if they successfully provide the entire complex of external signs of veneration. In the fixed price of respect, only the moral and intellectual scale of an individual is quoted. Precisely individuals, not positions. In war, deeds were valued, and even if the word was a living one, not a dead, official one.
Alexey Petrovich was far from being a textbook commissar - he was outwardly completely unassuming, and certainly not tribune-like. He was more famous as an excellent combat pilot, and, as I remember, he did not fool anyone with reports or edifications. He was given a strong natural mind, a kind soul and a strong fighting spirit. He went through the Soviet-Finnish war, like a faithful soldier of his Fatherland, and did not hesitate on the first day of the Great Patriotic War. Now the count of his combat missions was in his second hundred. He flew along with us, like an ordinary ship commander, but he liked to take off first, or maybe he didn’t like it, not seeing any tactical advantages in it, but he apparently considered the place in front of the squadron his own.
Chulkov, after the bombing of the Orsha airfield, was already walking home and was half an hour away from his own people, when suddenly they came under fire, a shell hit the right engine. It began to smoke, gurgled, coughed, and had to be turned off. The propeller, unfortunately, continued to rotate, sliding became inevitable, and the car began to decline slightly. There was very little altitude left to the front line, but Alexey Petrovich and his constant navigator Grigory Chumash along the way found a base for our fighters in the Kaluga region and decided to land on the move.
At night, such airfields do not operate and do not even have night landing facilities, but the duty “T” lights were on, and Alexey Petrovich made a successful landing along the landing strip, perhaps with some overshoot. The airfield was tiny, for camouflage it was furnished with haystacks and models of animals, and when the plane was at the very edge of it, the radio gunners, seeing this “rural landscape,” shouted in one voice: “False airfield!” Alexey Petrovich gave in to the scream, and although the next moment Chumash shouted: “Sit down!” - It was too late. The left engine pulled the car further at full throttle, but it was unable to regain the lost speed and altitude, and even with one landing gear not retracted. While turning around, outside the airfield, the plane hit the pine trees with its wing, fell to the ground and caught fire. The flames from the tanks crawled towards the pilot cabin. Chulkov was wounded and could not get up himself. It burned there. Radio operator Dyakov also died in the fire. Overcoming the pain from bruises and abrasions, shooter Glazunov climbed out through the turret ring, but was unable to get through the fire to the commander. Grisha Chumash was thrown out of his broken navigator's shell and during the fall he broke his leg in two places. He crawled away from the fire, bandaged his bleeding wounds with scraps of linen and began to wait for help. She came from the airfield. After numerous operations, the leg was noticeably shortened, and I had to say goodbye to flying work.
This is how our legendary commissar died.
In just over a year of the war, he made 119 combat missions, 111 of them at night.
Bombed Berlin and other cities and military installations in Germany. Carrying out 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, during the formation of the regiment, the order was read out. There are these words:
For boundless devotion to the Motherland, for the good organization of the combat work of the squadron, for personal courage and heroism in battle, despising death, battalion commissar Chulkov is worthy of the highest government award of the title of “Hero of the Soviet Union” with the presentation of the Order of Lenin and the Gold Star medal - Posthumously
He was buried in the city of Kaluga.
Awards
By Decree of the Presidium of the Supreme Soviet of the USSR of December 31, 1942 For the feat and excellent performance of combat missions of the command, Major Alexei Petrovich Chulkov was posthumously awarded the title of Hero of the Soviet Union.
Awarded two Orders of Lenin and two Orders of the Red Banner.
From the award list:
Major Chulkov works as deputy commander of the air squadron 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 foreman Kozlovsky and the air gunner senior sergeant Dyakov.
He has been in the active army since the first days of World War II. During this period, he carried out 114 combat sorties, 111 of them at night and all with excellent performance of the combat mission. He flew to bomb enemy military-industrial facilities and political centers deep in the rear: Berlin - 2 times, Budapest - 1 time, Danzig - 1 time, Koenigsberg - 1 time, Warsaw - 2 times.
For the excellent performance of 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 carried out 55 combat missions. While working as a military commissar of an air squadron, he established himself as an educator of personnel in the spirit of devotion to the Motherland and hatred of the enemy. His squadron flew 951 sorties against the enemy during combat operations. Comrade Chulkov, by his personal example, inspires subordinate personnel to achieve heroic deeds. Disciplined, demanding of himself and his subordinates. He enjoys well-deserved authority among the personnel. He is devoted to the cause of Lenin's party and the socialist Motherland.
For the excellent performance of the command’s combat missions to defeat German fascism and the courage and heroism displayed, 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
General of Aviation GOLOVANOV
Divisional Commissioner 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
A street in the city of Karabanovo, Vladimir region, bears the name of the Hero.
In 2004, V.V. Reshetnikov’s book, “What Was, Was,” was published, which talks about Chulkov.
Documentary story “The Winged Commissar” by Yu.N. Khudova
In 2000, our school was named after the Countryman Hero.
The director of our school is a relative of Chulkov Alexey Petrovich Chulkov Petr Alexandrovich. It is largely thanks to his activities that 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. Served in the Republic of Afghanistan, commander of a security platoon of a separate motorized rifle escort. He and his comrades accompanied convoys of KAMAZ trucks with cargo. One day the column came under fire, and Pyotr Alexandrovich was wounded.
Chulkov Pyotr Aleksandrovich was awarded: the star “Participant in the Afghan War”, the order badge “Warrior – Internationalist”, the medal “From the Grateful Afghan People”, the Certificate of the Presidium of the Supreme Soviet of the USSR “For Courage and Military Valor”.
He is distinguished by modesty, responsibility, rigor, and elegance. He is a talented leader and organizer of teaching and student teams. Under his leadership, the school is one of the best schools in the area.
Exhibition in the school museum of the village of Yukhmachi
Victory Park in Kazan
Monument dedicated to Chulkov A.P. in the village of Yukhmachi, in the Hero’s Homeland.
V.V. Reshetnikov with granddaughter A.P. Chulkova 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, of bloody battles. A.P. Chulkov became a Hero for a reason, he was a real person, raised by his family, his Motherland.
Work on materials about the Hero contributed to the determination of spiritual guidelines, moral values, universal human priorities, and the formation of patriotic consciousness as one of the most important values and foundations of spiritual and moral unity.
And the need to participate in the affairs of the Russian schoolchildren movement, of which I am a member, becomes clear. This is a public-state children's and youth organization, formed by the decision of the constituent meeting 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. RDS works in the following areas: - military-patriotic - “Youth Army”
Personal development
Civic activism (volunteering, search work, studying history, local history)
Information and media.
4. References:
1.V.V. Reshetnikov “What happened, what happened”, M., 2004.
2. Yu.N. Khudov "Winged Commissar"
3. Materials from the school museum of the village of Yukhmachi
4. Photo from the personal archive of Chulkov P.A.
5.http://ru.wikipedia.org
Participant Application Form
Republican project competition “Glorious pages of history.
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 RT, Alkeevsky district, Yukhmachi village
Nomination "Glorious Sons of the Fatherland"
First name, last name 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 Aleksey Petrovich Chulkov"Yukhmachi village, st. Shkolnaya, house 10 a
Phone number 89276781352
E-mail [email protected]
Teacher's full name (in full) Moskvina Galina Alexandrovna
Teacher's contact phone number 89270389187
Consent to the processing of personal data
I, Shubina Tatyana Nikolaevna, passport 9200097914
, issued ATC of the Aircraft Construction District of Kazan, 01.11.2002__________________________________________________________
(when, by whom)
RT, Alkeevsky district, Yukhmachi village, st. School 4.
____________________________________________________________________________________________________________________
I consent to the processing of my child’s personal data Galiullin Ravil Rashitovich
RT, Alkeevsky district, Yukhmachi village, st. School 4.
operator of the Ministry of Education and Science of the Republic of Tatarstan to participate in the competition.
List of personal data for the processing of which consent is given: last name, first name, patronymic, school, class, home address, date of birth, telephone number, email address, 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, and destruction of personal data.
With this statement, I authorize the following personal data of my child to be considered publicly available, including on the Internet: last name, first name, class, school, preschool, the result of the final stage of the competition, as well as the publication in the public domain of a scanned copy of the work.
Processing of personal data is carried out in accordance with the norms of the Federal Law of the Russian Federation dated July 27, 2006 No. 152-FZ “On Personal Data”.
This Agreement comes into force from the date of its signing and is valid for 3 years.
______________________ _____________________________ (personal signature, date)
Third city scientific
student conference
Computer Science and Mathematics
Research
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 subjects contain various types of tasks, 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 district library;
e) are readers of both libraries?
3. Each student in the class learns either English or French, or both. 25 people study English, 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. There are 52 children in the kindergarten. 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 these 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, a child’s drawing of a person (Fig. 6) is a graph with a maximum connectivity of 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 of a large number of varieties 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 of different types are included in the graph restrictions. 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
To view the presentation with pictures, design and slides, download its file and open it in PowerPoint on your computer.
Text content of presentation slides: Research work Graphs around us. Completed by: Elena Abrosimova, student of class 8 “A” of MAOU Domodedovo Secondary School No. 2 Supervisor: Genkina N.V.
Find out the features of the application of graph theory in solving mathematical, logical and practical problems. The purpose of the research work:
Study graph theory; Solve problems using graphs; Consider the application of graph theory in various fields of science; Create routes and tasks using graph theory; Find out whether 7th grade students have knowledge about graphs. Tasks:
Graph-?
Leonhard Euler The first to develop graph theory was the German and Russian mathematician Leonhard Euler (1707-1783). There is no science that is not related to mathematics
The Koenigsberg Bridges Problem
Let's imagine the problem in the form of a graph where islands and shores are points, and bridges are edges.
Tasks. No. 1 Boys of class 10 “B” Andrey, Vitya, Seryozha, Valera, Dima shook hands when they met (each shook hands with each other once). How many handshakes were done?
No. 2 The problem of rearranging four knights. Write an algorithm for replacing yellow knights with red knights and red knights with yellow knights.
Graph theory in various fields of science. Graph theory in various fields of science. Own developments Route through Domodedovo churches.
Bus route for pensioners.
Task No. 1.
Answer:
Task No. 2.
Route along the Petersburg Palace Bridges. Study:
“Graphs and their application” L. Yu. Berezin. “The most famous scientist” ed. Kaleidoscope “Kvant” “Leonard Euler” V. Tikhomirov “Topology of graphs” V. Boltyansky “Modern school encyclopedia. Mathematics. Geometry" ed. "Moscow Olma Media Group" Graph (mathematics) - Wikipedia ru.wikipedia.org Graphs. Application of graphs to problem solving festival.1september.ru GRAPHS sernam.ruGraphs | Social network of educators nsportal.ruGraphs / Mathematics studzona.comGraphs and their application in solving problems sch216.narod.ruGraphs 0zd.ruSources: Thank you for your attention.
Municipal autonomous educational institution
Domodedovo secondary school No. 2
Research work.
"Counts around us."
Completed by: E. S. Abrosimova, student of 8th grade.
Head: mathematics teacher N.V. Genkina
year 2014.
Plan:
Introduction.
Hypothesis.
Relevance of the topic.
Theory.
Practical application.
Own developments.
Study.
Conclusion.
Introduction:
Graph theory interested me because of its ability to help solve various puzzles, mathematical and logical problems. Since I was preparing for the Mathematical Olympiad, graph theory was an integral part of my preparation. Having delved deeper into this topic, I decided to understand where else graphs are found in our lives.
Hypothesis:
Studying graph theory can help in solving various puzzles, math and logic problems.
Relevance of the topic:
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.
Theory:
Graph theory is a branch of mathematics that studies the properties of graphs. In mathematical theory, a graph is a collection of a non-empty set of vertices and sets of pairs of vertices (connections between vertices). Mathematical graphs with the noble title “count” are connected by a common origin from the Latin word “graphio” - I write. A graph is called complete if every two distinct vertices are connected by one and only one edge.
Objects are represented as vertices, or nodes, of a graph, and connections are represented as arcs, or edges. For different application areas, types of graphs may differ in directionality, restrictions on the number of connections, and additional data about vertices or edges. The degree of a vertex is the number of edges in the graph to which this vertex belongs.
When depicting graphs in drawings, the following notation system is most often used: the vertices of the graph are depicted as dots or, when specifying the meaning of the vertex, rectangles, ovals, etc., where the meaning of the vertex is revealed inside the figure (graphs of flowcharts of algorithms). If there is an edge between the vertices, then the corresponding points (figures) are connected by a segment or arc. In the case of a directed graph, arcs are replaced by arrows, or the direction of an edge is explicitly indicated. There is also a planar graph - this is a graph that can be depicted in a picture without intersection. If a graph does not contain cycles (paths to traverse edges and vertices once and return to the original vertex), it is usually called a “tree.” Important types of trees in graph theory are binary trees, where each vertex has one incoming edge and exactly two outgoing ones, or is finite - having no outgoing edges. Basic concepts of graph theory. A graph route is a sequence of alternating vertices and edges. A closed route is a route in which the starting and ending vertices coincide. A simple chain is a route in which all edges and vertices are different. A connected graph is a graph in which each vertex is reachable from any other.
The terminology of graph theory is still not strictly defined.
The first to develop graph theory was the German and Russian mathematician Leonhard Euler (1707-1783). Which is known for its ancient problem about the Königsberg bridges, which it solved in 1736. Euler was a mathematician and mechanic who made fundamental contributions to the development of these sciences. L. Euler's whole life was connected with scientific activity and not only related to graphs. He said: “There is no science that is not connected with mathematics.” He spent almost half his life in Russia, where he made a significant contribution to the development of Russian science. Subsequently, Koenig (1774-1833), Hamilton (1805-1865), and modern mathematicians C. Berge, O. Ore, A. Zykov worked on graphs.
Problem about the Königsberg bridges.
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 Koenigsbergers offered visitors the following task: to cross all the bridges and return to the starting point, and each bridge had to be visited only once.
This map can be associated with an undirected graph - this is an ordered pair for which certain conditions are met, where the vertices will be parts of the city, and the edges will be bridges connecting these parts to each other. Euler proved that the problem has no solution. In Kaliningrad (Konigsberg) they remember Euler's problem. And that is why a graph that can be drawn without lifting the pencil from the paper is called Eulerian, and such contours form the so-called unicursal graphs.
Theorem: for a unicursal graph, the number of vertices of odd index is zero or two.
Proof: Indeed, if a graph is unicursal, then it has a beginning and an end to its traversal. The remaining vertices have an even index, since with each entrance to such a vertex there is also an exit. If the beginning and end do not coincide, then they are the only vertices of the odd index. The beginning has one more output than input, and the end has one more input than output. If the beginning coincides with the end, then there are no vertices with an odd index. CTD.
Properties of a graph (Euler): If all the vertices of a 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.
Practical application:
Graphs are wonderful mathematical objects; with their help you can solve a lot of different, outwardly dissimilar problems.
Vitya, Kolya, Petya, Seryozha and Maxim gathered in the gym. Each of the boys only knows the other two. Who knows whom?
Solution: Let's build a graph.
Answer: Vitya knows Kolya and Seryozha, Seryozha knows Vitya and Petya, Petya knows Seryozha and Maxim, Maxim knows Petya and Kolya, Kolya knows Petya and Maxim.
Boys of grade 10 “b” Andrey, Vitya, Seryozha, Valera, Dima shook hands when they met (each shook the other’s hand once). How many handshakes were done? Solution: Let each of the five young people correspond to a certain point on the plane, named by the first letter of his name, and let the handshake produced be a segment or part of a curve connecting specific points - names.
If you count the number of edges of the graph shown in the figure, then this number will be equal to the number of handshakes completed between five young people. There are 10 of them.
Four knights rearrangement problem. Write an algorithm for replacing yellow knights with red knights and red knights with yellow knights. The knight moves in one move with the letter “L” in a horizontal or vertical position. The knight can jump over other pieces standing in its way, but can only move onto empty squares.
Solution. We associate a point on the plane with each cell of the board, and if one can get from one cell to another by moving a knight, then we connect the corresponding points with a line, and we get a graph.
Writing an algorithm for rearranging knights becomes obvious.
Hackenbush Manor.
This wonderful game was invented by mathematician John Conway. The game uses a picture of “Hackenbush Manor” (see below). In one move, the player erases any one segment of the picture, limited by dots or one dot if the segment is a loop. If, after deleting this line, some of the lines are not connected to the frame, then they will also be deleted. The figure shows an example where the line highlighted in green is deleted, and along with it the smoke lines highlighted in red are deleted. The player who removes the last element of the picture wins.
Task:
Try to draw each of the following seven shapes in one stroke. Remember the requirements: draw all the lines of a given figure without lifting the pen from the paper, without making any extra strokes and without drawing a single line twice.
Task:
Is it possible to bypass all given rooms by going through each door exactly once and go outside through room 1 or 10? Which room should you start with?
Solution:
1) Let the rooms be the vertices of the graph, and the doors be the edges. Let's check the degrees of the vertices:
2)Only two vertices have an odd degree. You can start moving from room 10 and end in room 8, or vice versa.
3) But to go outside (from room 10), you need to start from room 8. In this case, we will go through all the doors once and end up in room 10, but we will find ourselves inside the room, and not outside:
Using similar reasoning, you can solve any problems with labyrinths, entrances and exits, dungeons, etc.
Graph theory has become an accessible tool for solving questions related to a wide range of problems:
in the study of automata and logical circuits,
In chemistry and biology,
In natural history,
In the design of integrated circuits and control circuits,
In history.
Own developments:
After studying the material, I decided on my own, with the help of a graph, to create an excursion route for a school bus around Domodedovo churches. Here's what I got. One of the objectives of creating such a route was the condition that one cannot drive along the same road twice. This condition can be met based on Euler’s theorem, that is, construct a graph containing no more than 2 odd vertices.
Social bus route for pensioners. The goal of this route is that you cannot drive on the same road twice. This condition can be met based on Euler’s theorem, that is, construct a graph containing no more than 2 odd vertices.
I was also inspired by solving interesting problems, so I created my own.
Task:
It was a lesson. During the lesson, Masha passed a note to Katya. How to make a graph so that the note reaches Polina. Under the conditions that the note cannot be passed diagonally, and that the graph does not intersect with the route (graph) of the teacher.
Task:
The shepherd brought 8 sheep to the meadow. After some time, a wolf appeared and pretended to be a sheep. How can a shepherd identify a wolf if each sheep only knows two others?
Answer:
Task:
How to get around the Palace Bridges without crossing any bridge twice. One of the objectives of creating such a route was the condition that one cannot drive along the same road twice. This condition can be satisfied based on Euler's theorem.
After making the maps and problems, I decided to do some research and understand how other people use the science of graphs.
A study on the knowledge of graph theory among 7th grade students:
QUESTIONS:
Have you played the game draw a figure by numbers?
lefttop00
Have you played the game of drawing an envelope with one stroke?
Did you do this based on some scientific knowledge or trial and error?
Did you know that there is a whole science called “graphs” that helps solve the above problems?
Would you like to take a closer look at graph theory?
Conclusion:
After I did this research work, I studied graph theory in more detail, proved my hypothesis: “Studying graph theory can help in solving various puzzles, mathematical and logical problems,” examined graph theory in different fields of science and made my own route and your three tasks. But while doing this work, I noticed that many people actually use this science, although they do not have the slightest idea about it. I've learned a lot, but there's still a lot to work on.
Bibliography
L. Yu. Berezina “Graphs and their application: A popular book for schoolchildren and teachers.” Ed. Stereotype. - M.: Book house "LIBROKOM", 2013. - 152 p.
"The most famous learned man." Ed. Kaleidoscope "Kvanta"
V. Tikhomirov “Leonard Euler” (To the 300th anniversary of his birth). Ed. "Quantum"
V. Boltyansky “Graph Topology”. Ed. "Quantum"
“Modern school encyclopedia. Mathematics. Geometry". Ed. A.A. Kuznetsova and M.V. Ryzhakova. Ed. "M.: Olma Media Group", 2010. – 816 p.
Digital Resources:
wikipedia.orgfestival.1september.rusernam.runsportal.rustudzona.comsch216.narod.ru0zd.ru
Completed by: Mukhina Anna, student of grade 9A
Head: Kolchanova G.R.
mathematic teacher
The graph method is very important and widely
The graph method is very important and widely
used in various fields of science and
human life activity.
human life activity.
Solving many mathematical problems
simplifies if you can use
graphs. Representing data as a graph
gives them clarity and simplicity.
are also simplified, acquired
persuasiveness if you use graphs.
Many mathematical proofs
Goal: consider solving problems with
using "Graph", consider
“Graphs” using examples of algorithms and
family trees
Tasks:
Study popular scientific literature on
Analyze the results of the conducted
this issue.
experiments
A graph is a system that can be viewed intuitively
like many circles and many connecting them. Mugs
are called vertices of the graph, lines with arrows - arcs,
without arrows - edges.
The beginning of graph theory dates back to 1736, when L. Euler decided
the “Konigsberg bridge problem”, popular at that time.
The term “graph” was first introduced 200 years later (in 1936) by D. Koenig.
Mathematical graphs with the noble title “count” are connected by a common
Graphs are computer program algorithms, network diagrams
construction, where the vertices are events indicating the completion of work on
some area, and the edges connecting these vertices are works that
possible to start upon the completion of one event and must be completed for
doing the following.
origin from the Latin word “graphio” - I write. Typical graphs
are airline diagrams that are often posted at airports, diagrams
metro, and on geographical maps - images of railways.
The selected points of the graph are called its vertices, and the lines connecting them
- ribs.
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 to several different
ribs and return to the same vertex.
The city of Königsberg is located on
banks of the Pregel River and two
islands. Various parts of the city
were connected by seven bridges. By
on Sundays the townspeople performed
walks around the city. Question: is it possible
should I take a walk like this?
so that when you leave the house,
go back by going to
exactly once on each bridge.
Bridges over the Pregel River
located as in the picture.
Consider the graph corresponding
bridge diagram
To answer the problem question,
it is enough to find out, at least from
one vertex comes out even
number of bridges.
You can’t, while walking around the city,
cross all the bridges once and
go back.
Consider the problem of finding an exit
from a labyrinth whose corridors are not
occurs, for example, when wandering
must be on one
level. Similar situation
in caves or catacombs.
Court
The picture shows an interesting
example of a maze in Hampton Gardens
Let’s construct a corresponding
graph. The corridors of the labyrinth are
edges of the graph, and intersections, dead ends,
inputs and outputs are vertices.
Now you can clearly see that in the center
the labyrinth can be reached by following
And, accordingly, leave the center
the following peaks:
1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.
maze along the route:
13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.
We will look at the graphs in more detail on two
examples:
Algorithms
Family trees
