Презентация Graph theory irina prosvirnina. Definitions and examples. Paths and cycles онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Graph theory irina prosvirnina. Definitions and examples. Paths and cycles абсолютно бесплатно. Урок-презентация на эту тему содержит всего 68 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:68 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:3.38 MB
- Просмотров:72
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Graph theory
Irina Prosvirnina
Definitions and examples
Paths and cycles
№2 слайд
Содержание слайда: Definitions and examples
Although generally regarded as one of the more modern branches of mathematics, graph theory actually dates back to 1736.
In that year Leonhard Euler published the first paper on what is now called graph theory. In the paper, Euler developed a theory which solved the so-called Knigsberg Bridge problem.
№3 слайд
Содержание слайда: Definitions and examples
Euler (1707 – 1783) was born in Switzerland and spent most of his long life in Russia (St Petersburg) and Prussia (Berlin).
He was the most prolific mathematician of all time, his collected works filling more than 70 volumes.
№4 слайд
Содержание слайда: Definitions and examples
Like many of the very great mathematicians of his era, Euler contributed to almost every branch of pure and applied mathematics.
He is also responsible, more than any other person, for much of the mathematical notation in use today.
№5 слайд
Содержание слайда: Definitions and examples
What is a ‘graph’? Intuitively, a graph is simply a collection of points, called ‘vertices’, and a collection of lines, called ‘edges’, each of which joins either a pair of points or a single point to itself.
A familiar example, which serves as a useful analogy, is a road map which shows towns as vertices and the roads joining them as edges.
№6 слайд
Содержание слайда: Definitions and examples
Definition 1
An undirected graph comprises:
a finite non-empty set of vertices,
a finite set E of edges, and
a function : E such that, for every edge , is a one- or two-element subset of .
The edge e is said to join the element(s) of .
An undirected graph is simple if there are no loops and each pair of distinct vertices is joined by a unique edge.
№7 слайд
Содержание слайда: Definitions and examples
№8 слайд
Содержание слайда: Definitions and examples
We should emphasize that a graph and a diagram representing it are not the same thing.
A given graph may be represented by two diagrams which appear very different.
For instance, the two diagrams in the figure represent the same graph as can be observed by writing down the function
: E
№9 слайд
Содержание слайда: Definitions and examples
Definition 2
A pair of vertices and are adjacent if there exists an edge joining them. In this case we say both and are incident to and also that is incident to and to .
The edges {, , , } are adjacent if they have at least one vertex in common.
№10 слайд
Содержание слайда: Definitions and examples
Definition 2
The degree or valency, deg(), of a vertex is the number of edges which are incident to . (Unless stated otherwise, a loop joining to itself counts two towards the degree of .)
A graph in which every vertex has the same degree is called regular (with degree ) or simply -regular.
№11 слайд
Содержание слайда: Definitions and examples
Definition 2
The degree sequence of a graph is the sequence of its vertex degrees arranged in non-decreasing order.
№12 слайд
Содержание слайда: Definitions and examples
№13 слайд
Содержание слайда: Definitions and examples
№14 слайд
Содержание слайда: Definitions and examples
№15 слайд
Содержание слайда: Definitions and examples
№16 слайд
Содержание слайда: Definitions and examples
№17 слайд
Содержание слайда: Definitions and examples
Definition 3
A null graph (or totally disconnected graph) is one whose edge set is empty. (Pictorially, a null graph is just a collection of points.)
A complete graph is a simple graph in which every pair of distinct vertices is joined by an edge.
A bipartite graph is a graph where the vertex set has a partition such that every edge joins a vertex of to a vertex of .
A complete bipartite graph is a bipartite graph such that every vertex of is joined to every vertex of by a unique edge.
№18 слайд
Содержание слайда: Definitions and examples
Example 1
Since a complete graph is simple there are no loops and each pair of distinct vertices is joined by a unique edge. Clearly a complete graph is uniquely specified by the number of its vertices.
№19 слайд
Содержание слайда: Definitions and examples
Example 1
The complete graph with vertices can be described as follows.
It has vertex set and edge set with the function given by .
The graph is clearly regular with degree , since every vertex is connected, by a unique edge, to each of the other vertices.
№20 слайд
Содержание слайда: Definitions and examples
Example 1
The complete graphs with three, four and five vertices are illustrated in the figure.
№21 слайд
Содержание слайда: Definitions and examples
Example 2
Let be a bipartite graph where the vertex set has the partition .
Note that need not be simple. All that is required is that each edge must join a vertex of to a vertex of . Given and , there may be more than one edge joining them or no edge joining them.
Clearly, though, there are no loops in .
№22 слайд
Содержание слайда: Definitions and examples
Example 2
A complete bipartite graph is completely specified by and ||. The complete bipartite graph on and vertices, denoted , has and . It is necessarily simple.
№23 слайд
Содержание слайда: Definitions and examples
Example 2
The figure shows two bipartite graphs. In each case the vertices of are indicated by full circles and the vertices of by crosses. The graph in (b) is the complete bipartite graph, .
№24 слайд
Содержание слайда: Definitions and examples
Definition 4
Let be a graph with vertex set . The adjacency matrix of is the matrix such that is the number of distinct edges joining and .
№25 слайд
Содержание слайда: Definitions and examples
The adjacency matrix is necessarily symmetric as the number of edges joining and is the same as the number joining and .
The degree of vertex is easily determined from the adjacency matrix.
If there are no loops at then its degree is the sum of the entries in the th column (or th row) of the matrix.
Since every loop counts twice in the degree, when summing the entries in the th column (or th row) the diagonal element must be doubled to obtain the degree of .
№26 слайд
Содержание слайда: Definitions and examples
№27 слайд
Содержание слайда: Definitions and examples
№28 слайд
Содержание слайда: Definitions and examples
№29 слайд
Содержание слайда: Definitions and examples
№30 слайд
Содержание слайда: Definitions and examples
№31 слайд
Содержание слайда: Definitions and examples
Example 3
The null graph with vertices has the zero matrix as its adjacency matrix, since there are no edges whatsoever.
№32 слайд
Содержание слайда: Definitions and examples
Example 4
A complete graph has adjacency matrix with zeros along the leading diagonal (since there are no loops) and ones everywhere else (since every vertex is joined to every other by a unique edge).
№33 слайд
Содержание слайда: Definitions and examples
Definition 5
A graph is a subgraph of the graph , denoted , if , and , for every edge of .
The condition that , for every edge of , just means that the edges of the subgraph must join the same vertices as they do in . Intuitively, is a subgraph of if we can obtain a diagram for by erasing some of the vertices and/or edges from a diagram of . Of course, if we erase a vertex we must also erase all edges incident to it.
№34 слайд
Содержание слайда: Definitions and examples
Example 5
We can regard as a subgraph of .
№35 слайд
Содержание слайда: Paths and cycles
Using the analogy of a road map, we can consider various types of ‘journeys’ in a graph.
For instance, if the graph actually represents a network of roads connecting various towns, one question we might ask is: is there a journey, beginning and ending at the same town, which visits every other town just once without traversing the same road more than once?
As usual, we begin with some definitions.
№36 слайд
Содержание слайда: Paths and cycles
Definition 6
An edge sequence of length in a graph is a sequence of (not necessarily distinct) edges such that and are adjacent for . The edge sequence determines a sequence of vertices (again, not necessarily distinct) where (). We say is the initial vertex and the final vertex of the edge sequence.
№37 слайд
Содержание слайда: Paths and cycles
Definition 6
A path is an edge sequence in which all the edges are distinct. If in addition all the vertices are distinct (except possibly ) the path is called simple.
№38 слайд
Содержание слайда: Paths and cycles
Definition 6
An edge sequence is closed if . A closed simple path containing at least one edge is called a cycle or a circuit.
№39 слайд
Содержание слайда: Paths and cycles
An edge sequence is any finite sequence of edges which can be traced on the diagram of the graph without removing pen from paper. It may repeat edges, go round loops several times, etc.
№40 слайд
Содержание слайда: Paths and cycles
Edge sequences are too general to be of very much use which is why we have defined paths.
№41 слайд
Содержание слайда: Paths and cycles
In a path we are not allowed to ‘travel along’ the same edge more than once.
№42 слайд
Содержание слайда: Paths and cycles
If, in addition, we do not ‘visit’ the same vertex more than once (which rules out loops), then the path is simple.
№43 слайд
Содержание слайда: Paths and cycles
The edge sequence or path is closed if we begin and end the ‘journey’ at the same place.
№44 слайд
Содержание слайда: Paths and cycles
№45 слайд
Содержание слайда: Paths and cycles
№46 слайд
Содержание слайда: Paths and cycles
№47 слайд
Содержание слайда: Paths and cycles
№48 слайд
Содержание слайда: Paths and cycles
№49 слайд
Содержание слайда: Paths and cycles
№50 слайд
Содержание слайда: Paths and cycles
№51 слайд
Содержание слайда: Paths and cycles
The square of the adjacency matrix is
№52 слайд
Содержание слайда: Paths and cycles
№53 слайд
Содержание слайда: Paths and cycles
№54 слайд
Содержание слайда: ? In the -entry represents the number of edge sequences of length joining and .
The - entry of is obtained by ‘multiplying’ the th row and the th column of . We express this as
.
The th term in this sum, is the product of the number of edges connecting and with the number of edges connecting and ; in other words the number of edge sequences of length 2 joining and via .
Summing over all gives the total number of length 2 edge sequences connecting and .
№55 слайд
Содержание слайда: Paths and cycles
The cub of the adjacency matrix is
№56 слайд
Содержание слайда: Paths and cycles
№57 слайд
Содержание слайда: Paths and cycles
№58 слайд
Содержание слайда: Paths and cycles
Theorem 1
Let be a graph with vertex set and adjacency matrix .
The - entry of is the number of edge sequences of length joining and .
Proof
The following theorem can be prove by induction. The inductive step is similar to the argument used above.
№59 слайд
Содержание слайда: Paths and cycles
In an intuitively obvious sense, some graphs are ‘all in one piece’ and others are made up of several pieces.
We can use paths to make this idea more precise.
№60 слайд
Содержание слайда: Paths and cycles
Definition 7
A graph is connected if, given any pair of distinct vertices, there exists a path connecting them.
№61 слайд
Содержание слайда: Paths and cycles
An arbitrary graph naturally splits up into a number of connected subgraphs, called its (connected) components.
The components can be defined formally as maximal connected subgraphs.
№62 слайд
Содержание слайда: Paths and cycles
This means that is a component of if it is a connected subgraph of and it is not itself a proper subgraph of any other connected subgraph of .
This second condition is what we mean by the term maximal; it says that if is a connected subgraph such that , then so there is no connected subgraph of which is ‘bigger’ than .
№63 слайд
Содержание слайда: Paths and cycles
The components of a graph are just its connected ‘pieces’.
In particular, a connected graph has only one component.
Decomposing a graph into its components can be very useful.
It is usually simpler to prove results about connected graphs and properties of arbitrary graphs can frequently then be deduced by considering each component in turn.
№64 слайд
Содержание слайда: Paths and cycles
There is an alternative way of defining the components of a graph .
Define a relation on by
if and only if and can be joined by a path in .
Provided we allow the empty path with no edges, it is easily seen that is an equivalence relation.
№65 слайд
Содержание слайда: Paths and cycles
if and only if and can be joined by a path in .
? is an equivalence relation.
The only difficulty is in proving transitivity.
If is a path from to and is a path from to , then the edge sequence ‘ followed by ’ is an edge sequence from to , but it may not be a path as and may have edges in common.
If this is the case the edge sequence needs to be modified by omitting some edges to give the required path from to
№66 слайд
Содержание слайда: Paths and cycles
if and only if and can be joined by a path in .
Let be the partition of the vertex set by the equivalence classes of .
We can now form subgraphs with vertex and whose edges are those of which joint two vertices of .
These subgraphs are the components of .
№67 слайд
Содержание слайда: Paths and cycles
№68 слайд
Содержание слайда: Paths and cycles
Example 7
Frequently it is clear from a diagram of how many components it has. Sometimes, however, we need to examine the diagram more closely. For instance, both graphs illustrated in the figure have two components, although this is not instantly apparent for the graph (b).
Скачать все slide презентации Graph theory irina prosvirnina. Definitions and examples. Paths and cycles одним архивом:
