Presentation on the topic "graphs". Graph theory. Graph theory is an extensive independent branch of discrete mathematics. Used in the design of computer networks, pipelines, - presentation Necessary conditions for isomorphism

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 (for example, a subway map, a family tree, a tree of folders and directories, etc.)

Slide 3

Types (examples) of graphs:

In a regular (undirected) graph, 2 vertices can be connected by only one edge. 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 that characterizes the connection between the corresponding vertices (a digraph with labeled edges).

Slide 7

Solving a problem modeled by a loaded graph or network usually 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 each edge has not a number, but other information characterizing the connection between the corresponding vertices.

Slide 9

Multigraph 2 vertices connected by 2 or more edges (multiple edges)

Slide 10

Loop in a graph (an edge connects a vertex to itself)

Slide 11

The concept of degree of a vertex in a graph is the number of edges emerging from one vertex

Slide 12

GRAPH PROPERTIES:

1) For any graph, the sum of the degrees of the 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 given 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 (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 chain that is a cyclic route4) A simple chain is a chain that passes through each of its vertices exactly 1 time5) A simple cycle is a cycle that is a simple chain6) Connected vertices are vertices (for example, A and B), for of 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 it is possible to identify the so-called connected components (i.e., sets of vertices connected by the edges of the original graph, each of which is a connected graph). 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 vertices of the graph. For each of the cases listed below, draw a graph and determine all degrees of the vertices a) vertices x y are connected by an edge if and only if (x-y)/3 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|

Korobova Anastasia, student gr. 14-PGS-48D

Nowadays, 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 with several points drawn, some of which are connected by lines. First of all, it is worth saying that the counts that will be discussed have nothing to do with the aristocrats of bygone times. Our “graphs” are rooted in the Greek word “grapho,” which means “I write.” The same root is in the words “graph”, “biography”.

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 encountered:

in physics - when constructing electrical circuits

in chemistry and biology - when studying the molecules of their chains

in history – when compiling family trees (pedigrees)

in geography - when drawing maps

in geometry - drawings of polygons, polyhedra, spatial figures

in economics – when solving problems of choosing the optimal path for freight transport flows (airline, metro, railway schemes)

Graph theory is used to solve problems in mathematical olympiads. Graphs make the conditions of the problem clear, simplify the solution, and reveal the similarity of the problems.

Nowadays in any branch of science and technology you come across graphs.

Download:

Preview:

To use presentation previews, create a Google account and log in to it: https://accounts.google.com


Slide captions:

Presentation on mathematics Topic: “Graphs” Completed by Student of group 14-PGS-48D Anastasia Korobova

A graph is a figure consisting of points and lines connecting these points. The lines are called edges of the graph, and the points are called vertices. Vertices from which an even number of edges emerge are called even, and an odd number are called odd. Graph Examples 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 significant contributions 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 works 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 with 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. (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 you can draw this graph without lifting your pencil from the paper, moving along each edge only once. The movement can start from any vertex and end at the same vertex.

The following riddle has long been common among the residents of Königsberg: how to cross all the bridges (across the Pregolya River) without passing over 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 can be directed and some edges can be undirected. Mixed graph

Weighted graph 1 2 4 2 3 A B C D E

A tree is any connected graph that has no cycles. Trees Trees

This is a (multi) graph whose edges are assigned a direction. Directed edges are also called arcs. Directed graph

Counts encountered:

Graph theory is used to solve problems in mathematical olympiads. Graphs make the conditions of the problem clear, simplify the solution, and reveal the similarity of the problems. Nowadays in any branch of science and technology you come across graphs.

Thank you for your attention!


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: Graphs and their application in solving problems Contents What is a graph Properties of a graph History of the emergence of graphs The problem of the Königsberg bridges Application of graphs Conclusions 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. The points are called the vertices of the graph, and the connecting lines are edges. Edges of a graph Vertices of a graph Next What is a graph The number of edges emerging from 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 that has an even degree is called even. Odd degree Even degree contents 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 edges of the graph. The number of odd vertices of any graph is even. In any graph with n vertices, where n≥2, there are always two vertices with the same degrees . Properties of graphs If in a graph with n vertices (n>2) exactly two vertices have the same degree, then in this graph there is always 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 equal to n(n-1)/2. Properties of a graph Complete graph Incomplete graph Properties of a graph Directed graph Undirected graph Isomorphic graphs History of graphs The term “graph” first appeared in the book of the Hungarian mathematician D. Koenig in 1936, although the initial most important theorems about graphs go back to L. Euler. Further History of the emergence of graphs The foundations of graph theory as a mathematical science were laid in 1736 by Leonhard Euler, considering the problem of the Königsberg bridges. Today this task has become a classic one. contents Problem about the Königsberg bridges Former Königsberg (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. Next The problem about the Königsberg bridges The following problem was widespread among the residents of Königsberg: is it possible to walk across all the bridges and return to the starting point, visiting each bridge only once? Further Problem about the Königsberg bridges It is impossible to walk across the Königsberg bridges while observing the given conditions. Walking across all 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 “one stroke.” further The problem of the Königsberg bridges But, since the graph in this figure has four odd vertices, it is impossible to draw such a graph “with one stroke”. contents Euler graph A graph that can be drawn without lifting the pencil from the paper is called an Euler graph. Solving the problem of the Königsberg bridges, Euler formulated the properties of the graph: The number of odd vertices (vertices to which an odd number of edges lead) of the graph must be even. There cannot be a graph that has an odd number of odd vertices. If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex. A graph with more than two odd vertices cannot be drawn with one stroke. further Euler graph If all the vertices of the graph are even, then you can draw this graph without lifting the pencil from the paper (“with one stroke”), passing along each edge only once. The movement can start from any vertex and end at the same vertex. further Euler graph A graph with 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. further Euler graph A graph with more than two odd vertices cannot be drawn with “one stroke”. ? Using graphs Using graphs, solving mathematical problems, puzzles, and ingenuity problems is simplified. further Application of graphs Problem: Arkady, Boris. Vladimir, Grigory and Dmitry shook hands when they met (each shook hands with each other once). How many handshakes were done? further Application of graphs Solution: A D C B D 1 2 3 4 5 6 7 8 9 10 further Application of graphs In the state, the airline system is designed 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 by making no more than one change. What is the maximum number of cities there can be in this state? Application of graphs Let there be a certain city A. From it you can reach no more than three cities, and from each of them no more than two more (not counting A). Then the total number of cities is no more than 1+3+6=10. 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 ones there are two white ones (picture below). In 16 moves, put white knights in place of black ones, and black knights in place of white ones, and prove that it is impossible to do this in fewer moves. Application of graphs Having expanded the graph of possible moves of knights into a circle, we find that at the beginning the knights stood as in the figure below: Conclusion Graphs are wonderful mathematical objects, with the help of which you can solve mathematical, economic and logical problems. You can also solve various puzzles and simplify the conditions of problems in physics, chemistry, electronics, and automation. Graphs are used in the compilation of maps and family trees. There is even a special section in mathematics called “Graph Theory”. content


Attached files

1 slide

2 slide

The foundations of graph theory first appeared in the works of Leonhard Euler (1707-1783; Swiss, German and Russian mathematician), in which he described solving puzzles and mathematical entertainment problems. Graph theory began with Euler's solution to the problem of the seven bridges of Königsberg.

3 slide

The following riddle has long been common among the residents of Königsberg: how to cross all the bridges (across the Pregolya River) without passing over any of them twice? Many have tried to solve this problem both theoretically and practically during walks. But no one succeeded, but they also failed to prove that it was even theoretically impossible. In a simplified diagram of parts of a city (graph), bridges correspond to lines (arcs of the graph), and parts of the city correspond to points connecting lines (vertices of the graph). In the course of his reasoning, Euler came to the following conclusions: It is impossible to cross all the bridges without passing over any of them twice.

4 slide

There are 4 blood groups. When blood is transfused from one person to another, not all groups are compatible. But it is known that identical groups can be transferred 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. 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 numerical values ​​(they can indicate, 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 (called a weight matrix) has a corresponding graph. 1 2 4 2 3 A B C D E

Slide 9

Problem Roads have been 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 points). Determine the length of the shortest path between points A and F (assuming that travel can only be done on constructed roads). 1) 9 2) 10 3) 11 4) 12

10 slide

1. 2. 3. 4. 5. The length of the shortest route 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

 

It might be useful to read: