A graph is a finite set of vertices V and a set of edges R connecting pairs of vertices, G=(V,R). The cardinalities of the sets V and R are equal to N and M. The set of edges may be empty. Examples of vertices are objects of any nature (settlements, computer networks). Examples of edges are roads, sides, lines.
Vertices connected by an edge are called adjacent. Edges that have a common vertex are also called adjacent. An edge and any of its two vertices are called incident. The degree of a vertex is the number of edges incident to it. Each graph can be represented on the plane by a set of points corresponding to vertices, which are connected by lines corresponding to edges.
A graph path is a sequence of vertices and edges. A route is closed (cyclic) if the start and end vertices are the same. A route is a simple path if all vertices and edges are distinct. A graph is connected if every vertex is reachable from any other. Vertices that do not have incident edges are called isolated.
Incident Matrix
Communication Lists
List of ribs
Adjacency matrix of a connected weighted undirected graph of a graph
Construction of a spanning connected tree of minimum weight. Kruskal's algorithm All edges are removed from the graph, and a spanning subgraph is obtained, where all vertices are isolated. Each vertex is placed in a singleton subset. The edges are sorted in ascending order of weights. The edges are sequentially, in ascending order of their weights, included in the spanning tree.
There are 4 cases: 1) both vertices of the included edge belong to one-element subsets, then they are combined into a new, connected subset; 2) one of the vertices belongs to a connected subset, and the other does not, then we include the second in the subset to which the first belongs; 3) both vertices belong to different connected subsets, then we combine the subsets; 4) Both vertices belong to the same connected subset, then we exclude this edge.
An example of building a spanning tree of minimum weight for the graph GG Performed actions Set of vertices Graph 1 Build a spanning subgraph with isolated and vertices We get 5 singleton subsets: (V 1 ), (V 2 ), (V 3 ), (V 4 ), (V 5 ) 2Find the edge of minimum weight (R 15) and add it to the spanning subgraph Form a connected subset of vertices: (V 1,V 5 ). Save subsets (V 2 ), (V 3 ), (V 4 )
Performed actions Set of verticesGraph 3Among the remaining ones, find the edge of minimum weight (R 45) and add it to the spanning subgraph. Add the vertex to the connected subset: (V 1,V 5, V 4 ). We save the subsets (V 2 ), (V 3 ) 4Among the remaining ones, find the edge of minimum weight (R 23) and add it to the spanning subgraph Form a new connected subset of vertices: (V 2,V 3 ). We keep the first connected subset (V 1,V 5, V 4 ).
Performed actions Set of verticesGraph 5Among the remaining ones, find the edge of minimum weight (R 25) and add it to the spanning subgraph. Combine the subsets into one connected subset (V 1,V 5, V 4,V 2,V 3 ). 6The rest of the edges are not included in the graph, because all their vertices already belong to the same connected set.
Performed actions Set of verticesGraph 7A graph has been obtained, which: is a spanning graph (all vertices are included); connected (all vertices can be connected by routes); tree (no cycles); has a minimum weight. 8The resulting spanning tree has a minimum weight: R 12 +R 25 +R 15 +R 45 = =80 9 The cyclic number of graph G is γ=m-n+1=8-5+1=4, which corresponds to the number of edges not into a tree.
Declaring variables Two five-element integer arrays X and Y for storing graph vertex coordinates Integer two-dimensional array R for storing weights of graph edges Integer variables i, n and k for cycle counters Integer variable S for storing the sum of weights of tree edges of minimum weight
Generation of random coordinates of 5 graph vertices (loop over i). Computing edge weights. Outputting the adjacency matrix of a weighted digraph (nested loops in n and in k) Outputting the adjacency matrix of a weighted undirected graph – half of the elements of the initial matrix (initial value k=n+1) Program body
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 given 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
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!