Graph theory. Graph theory is an extensive independent branch of discrete mathematics

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 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, 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

Regularity 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 acquaint students with the concept of "Graph", the basic principles of its construction;

to form the ability to highlight relationships that connect objects;

develop attention, the ability to logical reasoning;

foster mutual assistance, the ability to work in a team

consolidation of acquired knowledge in practice

development of memory, attention;

development of independence;

education of cognitive activity.

Equipment:

• computer class equipped with modern technology, video projector, screen;
• computers with Windows XP OS, program Microsoft Office PowerPoint 2003;
• 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),		A V WITH A 3 V 4 WITH 3 4

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)

The number of vertices is called
graph order.
The number of edges is called
graph size.

Some terms-1

- Let R=(a,b) be one of the edges of the graph. Then
vertices a and b are called terminal
edge vertices;
- End vertices of the same edge
called neighboring;
- Two edges are called adjacent if they have
common end vertex;
- Two edges are called multiple if
the sets of their end vertices coincide;
- An edge is called a loop if its ends
match up.

Some terms-2

- The degree of a vertex V is denoted by deg(V)
is called the number of edges, for
of which this vertex is the end;
- A vertex is called isolated if
she is not the end for anyone
ribs;
- A vertex is called a leaf if it
is terminal for exactly one
ribs. For a sheet q, it is obvious that deg(q)=1.

Example:

deg(C)=4
H1,…H4 - Leaves

Another example:

Cities B and D are isolated
tops; Cities G and E are leaves.

Complete graph

A graph is called complete if any
two vertices are connected by an edge.
How many edges does a complete graph have
order n?
A complete graph of order n has the number of edges
equals Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Let's prove it...

Complete graph with two vertices
contains one edge - this is obvious.
Substitute n=2 into the formula n*(n-1)/2
We get:
n*(n-1)/2=1
The formula is correct for n=2

Assumption of induction

Let's assume the formula is true for
graph with k vertices.
Let us prove that this implies
validity of the formula for the graph
with (k+1) vertex.

Let's add one more vertex to the complete graph with K vertices.

And connect it with the first K
peaks...

We get:

We count how many ribs we got ...

K*(K-1)/2 + K
=
K*(K+1)/2
The last expression is obtained,
if in the formula n*(n-1)/2 instead of n
substitute K+1.

From the assumption of fairness
statement for n=k follows
validity of the statement at
n=k+1.
The theorem has been proven.

Examples of Complete Graphs

Important clarification

Pairs defining edges in an undirected graph are unordered (i.e.,
pairs (a,b) and (b,a) do not differ)

Directed graph

If the edges of the graph are the set
ordered pairs (i.e. (a,b) ≠ (b,a)),
The graph is said to be directed.
(or digraph)
How to Give Orientation to the Concept
visual meaning?
Very simple - the ribs are supplied
arrows (from beginning to end)!

Digraph example

Mixed Count

A mixed graph is a triple (V, E, A).
V is the set of vertices;
E is the set of undirected
ribs;
A is the set of directed edges.
By the way, directed edges
are called arcs.

Graph isomorphism

Let there be two graphs G1 and G2
If there is a one-to-one correspondence F
between the vertices of the graphs G1 and G2 , such that:
- if there is an edge (a,b) in the graph G1, then in the graph G2
there is an edge (F(a),F(b))
- if there is an edge (p,q) in the graph G2, then in the graph G1
there is an edge (F-1(p),F-1(q))
then the graphs G1 and G2 are called isomorphic, and
the correspondence F is an isomorphism.

Clarification

For digraphs and mixed graphs
correspondence F must preserve
arc orientation.

Necessary condition for isomorphism

Under what conditions between elements
two finite sets
set one-to-one
conformity?
Then and only then, the number of
elements are the same.
A necessary condition for isomorphism
graphs is the same number
peaks.

Is this condition sufficient?

No, because the vertices can be
connected in different ways.

Are these graphs isomorphic?

The number of vertices is the same -
necessary condition is met...

We are trying to build a correspondence F…

This is not an isomorphism: G1 has an edge (A, D),
and the images of these edges in G2 are not connected.

Another try...

And this is an isomorphism!

Are these graphs isomorphic?

Unfortunately no…

From a theoretical standpoint, two
isomorphic graph is one and the same
the same object (only, perhaps, differently depicted ...)

Paths (chains):

A path (chain) is a sequence
peaks:
a1, a2, … , an
where neighboring vertices ai and ai+1
connected by ribs.
The length of a path is the number of its components
ribs

Path examples:

(A, D, C) and (A, B, D) are paths. (A, B, C) is not the way.

The notion of a path for a digraph preserves
strength, but needs to be supplemented -
neighboring peaks in
sequences
a1, a2, … , an
must be connected by arcs.

Cycles

A cycle is a path whose initial and
end vertex match.
The length of a cycle is the number of its constituents
ribs.
A cycle is called simple if the edges in it
are not repeated.
A cycle is called elementary if it
simple and the vertices in it do not repeat.

Connectivity components

The vertices of an arbitrary graph can be
divided into classes such that for
any two vertices of the same class v1
and v2 there is a path from v1 to v2
These classes are called components
connectivity.
If the graph has exactly one component
connection, then the graph is called
connected.

Machine representation of graphs.

Adjacency matrix

- We enumerate the vertices of the graph G
consecutive integers from 1 to n;
- Build a square table n×n and
fill it with zeros;
- If there is an edge connecting
vertices i and j, then in positions (i,j) and (j,i)
put units;
- The resulting table is called
adjacency matrix of graph G.

Example

Some obvious properties of the adjacency matrix

- If a vertex is isolated, then its row and
column will be completely null;
- Number of units in a row (column)
equal to the degree of the corresponding
tops;
- For an undirected graph, the matrix
adjacency is symmetrical about
main diagonal;
- The loop corresponds to a unit standing on
main diagonal.

Generalization for a digraph

Adjacency matrix for digraph
can be built similar
way, but to take into account the order
vertices, you can do this:
If the arc comes from vertex j and
enters the vertex k, then at the position (j,k)
set adjacency matrices to 1, and in
position (k, j) set -1.

Incidence matrix

- We enumerate the vertices of the graph G
consecutive integers from 1 to
n;
- Build a rectangular table with
n rows and m columns (columns
correspond to the edges of the graph);
- If the j-th edge has a terminal
vertex k, then in position
(k,j) is set to one. In all
in other cases, it is set to zero.

Incidence matrix for a digraph

- If j-th arc comes from vertex k,
then position (k,j) is set to 1;
- If the j-th arc enters the vertex k, then
in position (k,j) put -1.
- In other cases, in position (k, j)
remains zero.

Since the columns of the matrix
incidences describe edges, then
each column may not contain
more than two non-zero elements

An example of an incidence matrix

List of ribs

Another way to represent a graph
– two-dimensional array (list of pairs).
The number of pairs is equal to the number of edges
(or arcs).

Edge list example

Comparison of different presentation methods

- The list of edges is the most compact, and
least incidence matrix
compact;
- The incidence matrix is ​​handy when
search for cycles;
- Adjacency matrix easier
the rest are in use.

Graph traversal

The traversal of a graph is the enumeration of it.
vertices such that each vertex
viewed once.

Agreement-1

Before performing a search for a graph
with n vertices, create an array Chk
of n elements and fill it
zeros.
If Chk[i] = 0, then i-th vertex more
not viewed.

Agreement-2

Let's get the data structure
(repository), in which we will
memorize vertices in the process
bypass. Storage Interface
should provide three functions:
- Bring the top;
- Extract top;
- Check whether the storage is empty;

Agreement-3

When vertex j is placed in
repository, it is marked as
viewed (i.e. installed
Chk[j]=1)

Bypass Algorithm-1

1) We take an arbitrary initial vertex,
print it and put it in storage;

3) Take vertex Z from storage;
4) If there is a vertex Q associated with Z and not
checked, then we return Z to the storage,
store Q, print Q;
5) Go to step 2

Bypass algorithm-2

1) We take an arbitrary initial vertex and
we put it in storage;
2) Is the storage empty? If YES - the end;
3) Take vertex Z from storage, print and
delete from storage;
4) We put in storage all the vertices,
associated with Z and not yet marked;
5) Go to step 2

What data structures are suitable as storage?

- Stack (PUSH - bring; POP - remove)
- Queue (ENQUE - enter; DEQUE -
extract)
Both structures allow checking
data availability.

Algorithm-1 combined with stack
is called depth traversal
Algorithm-2 combined with a queue
is called breadth-first

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 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 3 Among 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