Graph Theory Part 1.pdf

Graph Theory 1 Graph Theory – An Introduction These are both graphs but not the sort we are interested in! 2 Where is Graph Theory Used? Graphs are used to represent: Timetabling – school timetables, university timetables Internet – vertices are webpages and edges are links Communication networks –...

Graph Theory 1 Graph Theory – An Introduction These are both graphs but not the sort we are interested in! 2 Where is Graph Theory Used? Graphs are used to represent: Timetabling – school timetables, university timetables Internet – vertices are webpages and edges are links Communication networks – mobile phone networks Electrical circuits – printed circuits boards (PCBs) Fluid and gas flow in pipelines Facebook – vertices are people, edges are friendships Road and rail networks – vertices are cities, edges are routes Airline flight routes – vertices are cities, edges are routes GPS to find the shortest route between two points 3 Social Networks and Graphs Almost all social networks, including Facebook, model users and their connections with their friends using graphs. 4 Basic Graph Theory Terminologies: Vertices and Edges A graph, G, is a mathematical structure which consists of: (i). a vertex set V = V(G) whose elements are called vertices of G. (ii). an edge set E = E(G). Edge is the line joining any two vertices. Such a graph is denoted G = { V(G) , E(G) }, or simply G = { V, E }. 5 Example Graph with 4 vertices and 5 edges: 1 d e f 2 4 h g 3 G = { V ( G ) , E ( G ) } = { { 1, 2, 3, 4 } , { d , e, f , g , h } } 6 Example The edge-endpoint function for the graph is given in the table: 1 d e f 2 4 h g 3 An undirected graph is a graph in which the edges have no orientation. For example, the edge { 1, 2 } is considered identical to the edge { 2, 1 }. 7 If X and Y are vertices of a graph, G, then X and Y are said to be adjacent if they are joined by an edge. An edge in a graph that joins two vertices is said to be incident to both vertices. 1 Vertices 1 and 2 are adjacent. d Vertices 1 and 3 are not adjacent. e f 2 4 h Edge d is incident to vertices 1 and 2. g 3 8 Two edges connecting the same vertices are called multiple or parallel edges. In the figure f and g are parallel edges. 1 d e f 2 4 h g 3 Graphs with parallel edges, are called multigraphs. 9 Degree of a Vertex The degree of a vertex is the number of edges “connected” to that vertex. A E B D Vertex A Degree 3 B C D E 3 2 4 2 C 10 Any vertex of degree zero is called an isolated vertex and a vertex of degree one is an end-vertex. Example Vertex 5 is an isolated vertex and Vertex 3 is an end-vertex. 1 d e f 2 4 g 5 3 11 A vertex is said to be even or odd according to whether its degree is an even or odd number. 1 d e f 2 4 h g 3 12 The Handshaking Lemma In any undirected graph, the sum of the vertex degrees is equal to twice the number of edges, i.e. (X) ( deg ) = 2 E(G ). XV G 13 Example: Find the total degree and number of edges in each of the following graphs. A A A B G B B E F E D C D C D C 14 Note: A corollary of the Handshaking Lemma states that the number of odd vertices in a graph must be even. 15 The degree sequence of an undirected graph G is a bracketed list of the degrees of all the vertices written in ascending order with repetition as necessary. Example The degree sequence of the graph in the diagram is ( 1, 2, 2, 3, 4 ). A E B D C 16 Connected Graphs A graph is said to be connected if it cannot be expressed as the union of two graphs. If a graph is not connected it is said to be disconnected. P A E B D Q R T C S 17 Example : Which of the following graphs are connected? C B F E A D B A C D B E A A B D C E C D 18 Cut-Points and Bridges A vertex is a cut-vertex, if removal of that vertex (and the edges through it) disconnects the graph. A cut-vertex is also called a cutpoint. An edge is a bridge (or isthmus) if removal of that edge disconnects the graph. 20 Example 21 Regular Graphs A graph G is regular if all vertices of G have the same degree. A regular graph where all vertices have degree k is referred to as a k-regular graph. 22 Complete Graphs A complete graph, denoted Kn , is a graph with n vertices all of which are adjacent to each other. The complete graph Kn is regular and each vertex has degree n - 1. 23 Cycle Graph A cycle graph, denoted Cn, is a graph of n vertices, { v0, v1,..., vn }, with n edges { v0, v1 }, { v1, v2 } ,... , { vn -1, v0} }. 24 Notes (i). In a cycle graph every vertex has degree 2. 25 Notes (i). In a cycle graph every vertex has degree 2. (ii). The graph C1 contains a self-loop and a loop contributes 2 to the degree of the vertex. 26 Notes (i). In a cycle graph every vertex has degree 2. (ii). The graph C1 contains a self-loop and a loop contributes 2 to the degree of the vertex. Hence, the vertex in C1 has degree 2 ensuring that the Handshaking Lemma holds. (iii). The graph C2 contains parallel edges. A graph that contains no loops or parallel edges is called a simple graph. 27 Bipartite Graphs A bipartite graph, is a graph whose vertices can be partitioned into two disjoint subsets V1 and V2, where no edge joins vertices that are in the same subset. 28 In the case where every vertex of V1 is joined to every vertex of V2 then G is called a complete bipartite graph. It is usually denoted Kr,s where r and s represent the number of vertices in V1 and V2 respectively. The complete bipartite graph K2,5. 29 Multigraphs A multigraph is a graph that allows the existence of loops and parallel (multiple) edges. A loop is an edge that links a vertex to itself. In the figure the edge (D, D) is a loop and connects vertex D to itself. 30 Walks, Trails & Paths A walk of length k on a graph G is an alternating sequence of vertices and edges. The length of a walk is the number of edges in the walk. Example A walk on the graph below is given by: 1, 5, 4, 3, 7, 1, 6 and has length, L = 6. 31 A walk is said to be closed if its first and last vertices are the same. A closed walk, of length 8, on the graph below is given by: 1, 5, 4, 3, 7, 1, 6, 5, 1. 32 A trail is a walk where all edges are distinct but vertices may be repeated. A trail on the graph below is given by: 1, 5, 4, 3, 7, 1, 6, 5. 33 A closed trail is called a circuit. A circuit on the graph is given by: 1, 2, 3, 1, 5, 4, 3, 7, 1. 34 A path is a trail in which all vertices are distinct. Hence, in a path neither vertices nor edges are repeated. A path on the graph below is given by: 1, 5, 4, 3, 7. 35 A closed path is called a cycle. A cycle on the graph below is given by: 1, 2, 3, 4, 5, 1. 36 All trails are walks and all paths are trails. In terms of set theory, Paths ⸦ Trails ⸦ Walks as shown below. WALKS TRAILS PATHS 37 As we have defined the term path we can provide an alternative definition for a graph to be connected. A graph is connected if given any two vertices u and v there is a path from to u to v. P A E B D Q R T C S 38 Eulerian and Hamiltonian Graphs Eulerian Graphs An Euler circuit on a graph, G, is a circuit (closed trail) that uses every edge of G exactly once. A graph is Eulerian if it has an Euler circuit. This graph is Eulerian. Euler circuit: 1253451 39 Theorem Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree. All vertices have even degree so the graph is Eulerian. Euler circuit: 1253451 40 Definition An Euler trail through a graph, G is an open trail that passes exactly once through each edge of G. We say that G is semi-Eulerian if it has an Euler trail. Note that every Eulerian graph is semi-Eulerian. 41 Corollary to Theorem A connected graph is semi-Eulerian if and only if there are 0 or 2 vertices of odd degree. Note that if a semi-Eulerian graph has two vertices of odd degree then any Euler trail must have one of them as its initial vertex and the other as its final vertex. 42 Semi-Eulerian Graph By the previous corollary as there are two vertices (1 and 5) of odd degree (i.e. degree 3) the graph is semi-Eulerian. 43 Non-Eulerian Graph As there are four vertices of odd degree the graph is non-Eulerian. 44 Eulerian Graphs - Summary 45 Example: Check if the following graphs are Eulerian or not. A B A C F B E D D C A B A B G E D E C D F C 46 IMPORTANT: A connected graph has an Euler circuit if the degree of every vertex is an even number. A B A C F B E D D No Euler Circuit C Euler Circuit: ABCDA A A B D G E E B D F C C Euler Circuit: ABECDEA Euler Circuit: ABCDECFEGFBGA 47 Hamiltonian Graphs A Hamiltonian cycle on a graph, G, is a cycle (closed path) that uses every vertex of G exactly once. Note that we do not need to use all the edges. A graph is Hamiltonian if it has a Hamiltonian cycle. Hamiltonian cycle: 12341 We do not need to use all the edges. 48 Semi-Hamiltonian Graph A trail that passes exactly once through each vertex of G and is not closed is called a Hamiltonian trail. We say that G is semiHamiltonian. Note that every Hamiltonian graph is semi-Hamiltonian. Hamiltonian trail : 2143 49 Non-Hamiltonian Graph 50 Example: Check whether the following graphs are Hamiltonian or nor. A B P D C T P Q Q R S Q P R U T V X W V S R U T S 51 A B P D C T Hamiltonian cycle: ABCDA P Q R S No Hamiltonian cycle Q Q P R U T V X W V S R Hamiltonian cycle: PQRSVUTP U T No Hamiltonian cycle S 52 53