🗊Презентация Graph theory irina prosvirnina. Definitions and examples. Paths and cycles

Категория: Математика
Нажмите для полного просмотра!
Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №1Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №2Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №3Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №4Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №5Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №6Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №7Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №8Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №9Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №10Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №11Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №12Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №13Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №14Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №15Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №16Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №17Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №18Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №19Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №20Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №21Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №22Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №23Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №24Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №25Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №26Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №27Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №28Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №29Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №30Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №31Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №32Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №33Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №34Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №35Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №36Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №37Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №38Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №39Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №40Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №41Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №42Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №43Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №44Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №45Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №46Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №47Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №48Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №49Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №50Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №51Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №52Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №53Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №54Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №55Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №56Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №57Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №58Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №59Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №60Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №61Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №62Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №63Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №64Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №65Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №66Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №67Graph theory irina prosvirnina. Definitions and examples. Paths and cycles, слайд №68
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Graph theory irina prosvirnina. Definitions and examples. Paths and cycles. Доклад-сообщение содержит 68 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Graph theory Irina Prosvirnina Definitions and examples Paths and cycles
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
Definitions and examples

Слайд 13


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 14


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 15


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 16


Definitions and examples
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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, .
Описание слайда:
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 .
Описание слайда:
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 .
Описание слайда:
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
Описание слайда:
Definitions and examples

Слайд 27


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 28


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 29


Definitions and examples
Описание слайда:
Definitions and examples

Слайд 30


Definitions and examples
Описание слайда:
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.
Описание слайда:
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).
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
Paths and cycles

Слайд 45


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 46


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 47


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 48


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 49


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 50


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 51


Paths and cycles The square of the adjacency matrix is
Описание слайда:
Paths and cycles The square of the adjacency matrix is

Слайд 52


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 53


Paths and cycles
Описание слайда:
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 .
Описание слайда:
? 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
Описание слайда:
Paths and cycles The cub of the adjacency matrix is

Слайд 56


Paths and cycles
Описание слайда:
Paths and cycles

Слайд 57


Paths and cycles
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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 .
Описание слайда:
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
Описание слайда:
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).
Описание слайда:
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).

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию