Graph theory. Graph theory is an extensive independent branch of discrete mathematics. Used in the design of computer networks, pipelines, - presentation. Graphs Graphs and their use presentation

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. ? Using Graphs Graphs Simplify Decision Making math problems, puzzles, tasks for ingenuity. 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

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

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.

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
tops...

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 enough?

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 the j-th arc comes from the 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 the i-th vertex is still
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

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 Between settlements A, B, C, D, E, F roads are built, 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. Length of the shortest route A-B-C-E-F equals 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