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

Graph theory Irina Prosvirnina Definitions and examples Paths and cycles

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

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 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 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 sequence of a graph is the sequence of its vertex degrees arranged in non-decreasing order.

Definitions and examples

Definitions and examples

Definitions and examples

Definitions and examples

Definitions and examples

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 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 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 graphs with three, four and five vertices are illustrated in the figure.

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

Definitions and examples

Definitions and examples

Definitions and examples

Definitions and examples

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 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 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 Example 5 We can regard as a subgraph of .

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 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 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 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 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 Edge sequences are too general to be of very much use which is why we have defined paths.

Paths and cycles In a path we are not allowed to ‘travel along’ the same edge more than once.

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 The edge sequence or path is closed if we begin and end the ‘journey’ at the same place.

Paths and cycles

Paths and cycles

Paths and cycles

Paths and cycles

Paths and cycles

Paths and cycles

Paths and cycles

Paths and cycles The square of the adjacency matrix is

Paths and cycles

Paths and cycles

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

Paths and cycles The cub of the adjacency matrix is

Paths and cycles

Paths and cycles

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 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 Definition 7 A graph is connected if, given any pair of distinct vertices, there exists a path connecting them.

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

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