Korobova Anastasia, student gr. 14-PGS-48D
In our time, it is important to study various methods, properties and non-standard applications. We will consider the application of the "Graph" method in the reality around us.
The word "graph" in mathematics means a picture where several points are drawn, some of which are connected by lines. First of all, it is worth saying that the counts, which will be discussed, have nothing to do with the aristocrats of the past. Our "graphs" are derived from the Greek word "grapho", which means "I write." The same root in the words "graph", "biography".
The first work on graph theory belongs to Leonhard Euler, and it appeared in 1736 in the publications of the St. Petersburg Academy of Sciences.
Counts meet:
in physics - in the construction of electrical circuits
in chemistry and biology - in the study of molecules of their chains
in history - when compiling family trees (pedigree)
in geography - in mapping
in geometry - drawings of polygons, polyhedra, spatial figures
in economics - when solving problems of choosing the optimal path for freight transport flows (airlines, metro, railways)
Graph theory is used in solving tasks of mathematical Olympiads. Graphs give visibility to the conditions of the problem, simplify the solution, and reveal the similarity of problems.
Now in any branch of science and technology you meet with graphs.
Download:
Preview:
To use the preview of presentations, create a Google account (account) and sign in: https://accounts.google.com
Slides captions:
Presentation in mathematics Topic: "Graphs" Completed by a student of the group 14-PGS-48D Korobova Anastasia
A graph is a figure consisting of points and lines connecting these points. The lines are called the edges of the graph, and the points are called the vertices. Vertices from which an even number of edges emerge are called even, an odd number are called odd. Examples of Graphs Graph Theory
Leonhard Euler (April 4, 1707, Basel, Switzerland - September 7, 1783, St. Petersburg, Russian Empire) was a Swiss, German and Russian mathematician who made a significant contribution to the development of mathematics, as well as mechanics, physics, astronomy and a number of applied sciences. Euler is the author of more than 800 papers on mathematical analysis, differential geometry, number theory, approximate calculations, celestial mechanics, mathematical physics, optics, ballistics, shipbuilding, music theory, etc.
A figure (graph) that can be drawn without lifting the pencil from the paper is called unicursal. Pattern 1. A graph that has only two odd vertices can be drawn without lifting the pencil from the paper, while the movement must start from one of these odd vertices and end at the second of them. (Fig. A) Pattern 2 . A graph with more than two odd vertices cannot be drawn with “one stroke” (Fig. B) Euler graphs B A
Pattern 3. If all the vertices of the graph are even, then without lifting the pencil from the paper, drawing along each edge only once, draw this graph. The movement can start from any vertex and end it at the same vertex.
For a long time, such a riddle has been spread among the inhabitants of Königsberg: how to pass through all the bridges (across the Pregolya River) without passing through any of them twice? Many tried to solve this problem, both theoretically and practically, during walks The problem of the Königsberg bridges.
This is a graph in which some edges may be directed and some may be undirected. Mixed Count
Weighted graph 1 2 4 2 3 A B C D E
A tree is any connected graph that does not have cycles. Trees Trees
This is a (multi)graph whose edges are assigned a direction. Directed edges are also called arcs. Directed graph
Counts meet:
Graph theory is used in solving tasks of mathematical Olympiads. Graphs give visibility to the conditions of the problem, simplify the solution, and reveal the similarity of problems. Now in any branch of science and technology you meet with graphs.
Thank you for your attention!
To view a presentation with pictures, design, and slides, download its file and open it in PowerPoint on your computer.
Text content of presentation slides: Graphs and their application in solving problems Contents What is a graphProperties of a graphHistory of the emergence of graphsThe problem of Koenigsberg bridgesApplication of graphsConclusions What is a graph In mathematics, the definition of a graph is given as follows: 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. Points are called graph vertices, and the connecting lines are edges. Edges of a graph Vertices of a graph Next What is a graph The number of edges coming out of a vertex of a graph is called the degree of the vertex. A vertex of a graph that has an odd degree is called odd, and a vertex of an even degree is called even. Odd degree Even degree content Properties of graphs In a graph, the sum of the degrees of all its vertices is an even number equal to twice the number of graph edges. The number of odd vertices of any graph is even. . Properties of graphs If in a graph with n vertices (n>2) exactly two vertices have the same degree, then in this graph there will always be either exactly one vertex of degree 0, or exactly one vertex of degree n-1. If a complete graph has n vertices, then the number of edges will be n(n-1)/2. Graph properties Complete graph Incomplete graph Graph properties Directed graph Undirected graph Isomorphic graphs The history of graphs The term "graph" first appeared in the book of the Hungarian mathematician D. Koenig in 1936, although the initial most important graph theorems date back to L. Euler. More The history of graphs The foundations of graph theory as a mathematical science were laid in 1736 by Leonhard Euler, considering the problem of Königsberg bridges. Today, this task has become a classic. Contents The Königsberg Bridges Problem The former Königsberg (now Kaliningrad) is located on the Pregel River. Within the city, the river washes two islands. Bridges were thrown from the coast to the islands. The old bridges have not been preserved, but there is a map of the city where they are depicted. Next Problem about Königsberg bridges Among the residents of Königsberg, the following problem was common: is it possible to pass over all the bridges and return to the starting point, having visited each bridge only once? Next Problem about Königsberg bridges It is impossible to pass through the Königsberg bridges observing the given conditions. Passing through all the bridges, provided that you need to visit each one once and return to the starting point of the journey, in the language of graph theory looks like the task of depicting a graph with a “one stroke”. more Problem of Königsberg bridges But, since the graph in this figure has four odd vertices, it is impossible to draw such a graph "in one stroke". Euler Graph A graph that can be drawn without lifting the pencil from the paper is called an Euler graph. Solving the problem of Königsberg bridges, Euler formulated the properties of a graph: The number of odd vertices (vertices to which an odd number of edges lead) must be even. There cannot be a graph that would have an odd number of odd vertices. If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex. A graph with more than two odd vertices cannot be drawn in one stroke. further Euler graph 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. further Euler graph A graph that has only two odd vertices can be drawn without lifting the pencil from the paper, and the movement must start from one of these odd vertices and end at the second of them. beyond the Euler graph A graph that has more than two odd vertices cannot be drawn with a single stroke. ? Application of graphs With the help of graphs, the solution of mathematical problems, puzzles, tasks of ingenuity is simplified. next Application of graphs Task:Arkady, Boris. Vladimir, Grigory and Dmitry shook hands at the meeting (each shook hands with each one once). How many handshakes were made in total? further Application of graphs Solution: A D C B D 1 2 3 4 5 6 7 8 9 10 further Application of columns In the state, the airline system is arranged in such a way that any city is connected by airlines to no more than three others, and from any city to any other You can travel with no more than one transfer. What is the maximum number of cities that this state can have? Application of graphs Let there be some city A. From it you can get to no more than three cities, and from each of them no more than two more (not counting A). Then there are no more than 1+3+6=10 cities in total. This means that there are no more than 10 cities in total. The example in the figure shows the existence of airlines. A Application of Graphs There is a 3x3 chessboard, in the upper two corners there are two black knights, in the lower two white ones (figure below). In 16 moves, put the white knights in the place of the black ones, and the black ones in the place of the white ones, and prove that it is impossible to do this in fewer moves. Application of graphs Expanding the graph of possible moves of the knights in a circle, we get that at the beginning the horses stood as in the figure below: Conclusion 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. Mathematics even has a special section, which is called: “Graph Theory”. content
Attached files
slide 2
A graph is a finite collection of vertices, some of which are connected by edges i.e. this is a collection of points, called vertices, and lines connecting some of the vertices, called edges or arcs, depending on the type of graph.
slide 3
Types (examples) of graphs:
An ordinary (undirected) graph 2 vertices can only be connected by one edge. The connecting lines are called edges. (adjacent vertices are 2 vertices connected by an edge)
slide 4
A directed graph (digraph) is a graph in which the direction is indicated on the lines connecting the vertices (the connecting lines are called arcs)
slide 5
A loaded graph is a graph that has a number next to each edge that characterizes the connection between the corresponding vertices (a graph with labeled edges).
slide 6
A network is a digraph with a number next to each edge characterizing the connection between the corresponding vertices (a digraph with labeled edges).
Slide 7
The solution of a problem modeled by a loaded graph or network, as a rule, comes down to finding an optimal route in one sense or another, leading from one vertex to another.
Slide 8
A semantic graph is a graph or digraph in which, near each edge, not a number is affixed, but other information that characterizes the relationship between the corresponding vertices.
Slide 9
Multigraph 2 vertices connected by 2 or more edges (multiple edges)
Slide 10
A loop in a graph (an edge connects a vertex to itself)
slide 11
The concept of the degree of a graph vertex is the number of edges coming out of one vertex
slide 12
PROPERTIES OF GRAPHS:
1) For any graph, the sum of degrees of vertices is equal to twice the number of edges 2) For any graph, the number of vertices of odd degree is always even (analogous to the problem: at any time the number of people who have made an odd number of handshakes is even) 3) In any graph there is at least 2 vertices having the same degree.
slide 13
1) A route on a graph is a sequence of edges in which the end of one edge serves as the beginning of the next one (a cyclic route - if the end of the last edge of the sequence coincides with the beginning of the 1st edge) 2) A chain is a route in which each edge contains at most one times3) A cycle is a path that is a cyclic route4) A simple path is a path that goes through each of its vertices exactly 1 time5) A simple loop is a cycle that is a simple path6) Connected vertices are vertices (for example, A and B), which there is a chain starting at A and ending at B7) A connected graph is a graph in which any 2 vertices are connected. If the graph is disconnected, then the so-called connected components (i.e., sets of vertices connected by edges of the original graph, each of which is a connected graph) can be distinguished in it. One and the same graph can be depicted in different ways.
Slide 14
Example 1
V=(1,2,3,4,5,6,7,8,9,10) is the set of graph vertices. For each of the following cases, draw a graph and determine all degrees of vertices a) vertices x y are connected by an edge if and only if (x-y)/3 is an integer b) vertices x y are connected by an edge if and only if x+y=9 c ) vertices x y are connected by an edge if and only if x+y is contained in the set V=(1,2,3,4,5,6,7,8,9,10) d) vertices x y are connected by an edge if and only if when |x-y|
Equipment:
- computer class equipped with modern technology, video projector, screen;
- computers with Windows XP, Microsoft Office 2003 PowerPoint program;
- whiteboard equipment (lesson topic, new terms). Handout.
Lesson plan.
II. Presentation of new material. (10 min.)
III. Fixing the material. Practical work. (15-20 min.)
IV. Summing up the lesson. (2 min)
V. Homework.
I. Organizational moment. Knowledge update.
Hello! Our lesson is called "Graphs". We will get acquainted with the concept of “Graphs”, learn how to depict them and solve problems on this topic.
II Presentation of new material.
The first work on graph theory belongs to Leonhard Euler (1736), although the term "graph" was first introduced in 1936 by the Hungarian mathematician Denesh Koenig. Graphs were called schemes consisting of points and segments of straight lines or curves connecting these points (examples of graphs are shown in Figure 1)
With the help of graphs, the solution of problems formulated in various fields of knowledge was often simplified: in automation, electronics, physics, chemistry, etc. With the help of graphs, diagrams of roads, gas pipelines, heat and power networks are depicted. Graphs help in solving mathematical and economic problems.
Graph - (from the Greek grapho - I write) is a means of visual representation of the elements of the object of connections between them. These are wonderful mathematical objects, with their help you can solve a lot of different, outwardly dissimilar problems.
A graph is some information model
A graph consists of vertices or nodes connected by arcs or segments - edges. The line can be directed, i.e., have an arrow (arc), if not directed - an edge. Two vertices connected by an arc or edge are called adjacent.
Examples of graphs (Slide 4, 5, 6)
Task 1 (Slide 7):
A space communication has been established between the nine planets of the solar system. Regular rockets fly on the following routes:
Earth - Mercury; Pluto - Venus; Earth - Pluto; Pluto - Mercury; Mercury - Venus; Uranus - Neptune; Neptune - Saturn; Saturn - Jupiter; Jupiter - Mars; Mars - Uranus.
Is it possible to fly on regular rockets from Earth to Mars?
Solution: Let's draw a diagram of the condition: we will depict the planets with dots, and the routes of the rockets with lines.
Now it is immediately clear that it is impossible to fly from Earth to Mars.
Two vertices connected by an arc or edge are called adjacent. Each edge or arc is associated with a number. The number can indicate the distance between settlements, the time of transition from one peak to another, etc.
Task 2 (slide 9) - the solution is at the blackboard. Masha came to the zoo and wants to see as many animals as possible. Which path should she take? Yellow, red, green?
Task 3 (11 slide) - the solution is at the blackboard. Five football teams A, B, C, D, E must play matches with each other. Already played A with B, C, D; B c A, C, D. how many matches have been played so far? How much is left to play?
Graph representation (Slide 12)
The graph can be represented as a list of arcs (AB; 7), graphically or using a table.
| Arc Lists | Graphic form | tabular form | ||||||||||||||||
| (AB; 7), |  |
|
III. Consolidation of materials: students are invited to divide into groups and complete tasks. Working in a small group, students discuss models based on the theoretical knowledge gained at the beginning of the lesson. Thus, repetition and consolidation of the material is achieved.
Task 2 (Slide 13)
IV. Lesson summary
Guys, what new words did you learn today? (Count, graph vertex, graph edges.)
What can the vertices of a graph represent? (Cities; objects that are; connected.)
What do the edges of the graph mean (Paths, movements, directions)
Give an example of where in life we can meet them?
How are graphs displayed?
V. Homework. (Slide 15)
1 slide
2 slide
For the first time, the foundations of graph theory appeared in the works of Leonhard Euler (1707-1783; Swiss, German and Russian mathematician), in which he described the solution of puzzles and mathematical entertainment problems. Graph theory began with Euler's solution of the problem of the seven bridges of Königsberg.
3 slide
For a long time, such a riddle has been spread among the inhabitants of Königsberg: how to pass through all the bridges (across the Pregolya River) without passing through any of them twice? Many tried to solve this problem both theoretically and practically during walks. But no one has been able to do this, but no one has been able to prove that it is even theoretically impossible. On a simplified diagram, parts of the city (graph) correspond to bridges with lines (arcs of the graph), and parts of the city correspond to points of connection of lines (vertices of the graph). In the course of reasoning, Euler came to the following conclusions: It is impossible to pass over all the bridges without passing through any of them twice.
4 slide
There are 4 blood types. When blood is transfused from one person to another, not all groups are compatible. But it is known that the same groups can be transfused from person to person, i.e. 1 - 1, 2 - 2, etc. And also group 1 can be transfused to all other groups, groups 2 and 3 only to group 4. A task.
5 slide
6 slide
Graphs A graph is an information model presented in graphical form. A graph is a set of vertices (nodes) connected by edges. A graph with six vertices and seven edges. Vertices are called adjacent if they are connected by an edge.
7 slide
Directed Graphs - Digraphs Each edge has one direction. Such edges are called arcs. Directed graph
8 slide
Weighted Graph This is a graph whose edges or arcs are assigned numeric values (they can represent, for example, the distance between cities or the cost of transportation). The weight of a graph is equal to the sum of the weights of its edges. The table (it is called the weight matrix) corresponds to the graph. 1 2 4 2 3 A B C D E
9 slide
Task Roads are built between settlements A, B, C, D, E, F, the length of which is shown in the table. (The absence of a number in the table means that there is no direct road between the points). Determine the length of the shortest path between points A and F (assuming that you can only move along the constructed roads). 1) 9 2) 10 3) 11 4) 12
10 slide
1. 2. 3. 4. 5. The length of the shortest path A-B-C-E-F is 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2
