6 Graph Theory PDF

6. Graph Theory ------------------------------------------------------------------------------------------------ Syllabus Introduction – Definition of a graph – sub graph – Isomorphism - walk, Paths and circuits – connectedness and components – Euler graphs. ---------------------------...

6. Graph Theory ------------------------------------------------------------------------------------------------ Syllabus Introduction – Definition of a graph – sub graph – Isomorphism - walk, Paths and circuits – connectedness and components – Euler graphs. ------------------------------------------------------------------------------------------------ 6.1 Introduction Definition of Graph A graph is a pictorial representation of any data in an organised manner. In graph theory, A graph G = (V, E) consists of a set V of vertices (also called nodes) and a set E of edges. Example: Suppose, a Graph G=(V,E), where Vertices, V={a,b,c,d} Edges, E={{a,b},{a,c},{b,c},{c,d}} Important Definitions If an edge connects to a vertex we say the edge is incident to the vertex and say the vertex is an endpoint of the edge. If an edge has only one endpoint then it is called a loop edge. Two vertices that are joined by an edge are called adjacent vertices. A pendant vertex is a vertex that is connected to exactly one other vertex by a single edge. Graph Theory | 1  A walk in a graph is a sequence of alternating vertices and edges v1 e1 v2 e2... vn en vn+1 with n ≥ 0. If v1 = vn+1 then the walk is closed. The length of the walk is the number of edges in the walk. A walk of length zero is a trivial walk. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices. A circuit is a closed trail and a trivial circuit has a single vertex and no edges. A trail or circuit is Eulerian if it uses every edge in the graph. A cycle is a nontrivial circuit in which the only repeated vertex is the first/last one. A simple graph is a graph with no loop edges or multiple edges. Edges in a simple graph may be specified by a set {vi, vj} of the two vertices that the edge makes adjacent. A directed graph is a graph in which the edges may only be traversed in one direction. Edges in a simple directed graph may be specified by an ordered pair (vi, vj) of the two vertices that the edge connects. The degree of a vertex is the number of edges incident to the vertex and is denoted deg(v). Σ𝑑(𝑣𝑖) = 3+5+1+1 = 10 = 2×|E| In any graph, sum of degrees of vertices is twice the number of edges. Σ𝑑(𝑣𝑖) = 2×|E| Q. Let G be a graph with 11 edges and minimum degree of any vertex is 2, then the maximum number of vertices graph can have? Solution: Let the no of vertices be x. d(vi) = 2×|E| 2+2+2……. x times ≤ 2 × 11 2x ≤ 22 x ≤ 11 Hence, Maximum 11 vertices we can have. 2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 2  In a directed graph, the in-degree of a vertex is the number of edges incident to the vertex and the out-degree of a vertex is the number of edges incident from the vertex. In-degree: In-degree of a vertex v1 = deg(v1) = 1 In-degree of a vertex v2 = deg(v2) = 1 In-degree of a vertex v3 = deg(v3) = 1 In-degree of a vertex v4 = deg(v4) = 5 In-degree of a vertex v5 = deg(v5) = 1 In-degree of a vertex v6 = deg(v6) = 0 Out-degree: Out-degree of a vertex v1 = deg(v1) = 2 Out-degree of a vertex v2 = deg(v2) = 3 Out-degree of a vertex v3 = deg(v3) = 2 Out-degree of a vertex v4 = deg(v4) = 0 Out-degree of a vertex v5 = deg(v5) = 2 Out-degree of a vertex v6 = deg(v6) = 0 6.2 Special Graphs MULTI GRAPH: If more than one line joining two vertices are allowed then the resulting object is called a multi graph. Lines joining the same points are called multiple lines. PSEUDO GRAPH: If an object contains multiple lines and loops then it is called a pseudo graph. Graph Theory | 3  NULL GRAPH (𝑁𝑛): A graph G whose edge set is empty is called a null graph or a totally disconnected graph. CYCLE GRAPH (𝐶𝑛): A cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. WHEEL GRAPH (𝑤𝑛): Wheel Graph is a graph that contains a cycle of order n-1 and for which every graph vertex in the cycle is connected to one other graph vertex known as the hub. The edges of a wheel which include the hub are called spokes. Some authors write 𝑤𝑛 to denote a wheel graph with n vertices (n ≥ 4); other authors instead use 𝑤𝑛 to denote a wheel graph with n + 1 vertices (n ≥ 3). REGULAR GRAPH: A graph G is said to be regular, if all its vertices have the same degree. In a graph, if the degree of each vertex is ‘k’, then the graph is called a ‘k-regular graph. In both the graphs, all the vertices have degree 2. They are called 2-Regular Graphs. 2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 4  COMPLETE GRAPH (𝐾𝑛): If a vertex is connected to all other vertices in a graph, then it is called a complete graph. NOTE: A complete graph with n vertices has 𝑛𝐶2 that is n*(n-1)/2 edges. BIPARTITE GRAPH: A simple graph G = (V, E) with vertex partition V = {V1, V2} is called a bipartite graph if every edge of E joins a vertex in V1 to a vertex in V2. In general, a Bipartite graph has two sets of vertices, let us say, V1 and V2, and if an edge is drawn, it should connect any vertex in set V1 to any vertex in set V2. In this graph, you can observe two sets of vertices − V1 and V2. Here, two edges named ‘ae’ and ‘bd’ are connecting the vertices of two sets V1 and V2. COMPLETE BIPARTITE GRAPH (𝐾𝑚,𝑛): A bipartite graph ‘G’, G = (V, E) with partition V = {V1, V2} is said to be a complete bipartite graph if every vertex in V1 is connected to every vertex of V2. Graph Theory | 5 6.3 Sub-Graph A graph H is a subgraph of a graph G if all vertices and edges in H are also in G. Deleting some vertices or edges (b) from the supergraph (a) leaves a subgraph (c). 6.4 Isomorphism A graph can exist in different forms having the same number of vertices, edges, and also the same edge connectivity. Such graphs are called isomorphic graphs. Isomorphic Graphs: Two graphs G1 and G2 are said to be isomorphic if − they are the same graph and drawn differently. 6.5 Walk, Paths and Circuits Walk – A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk. Edge and Vertices both can be repeated. Closed walk = A, B, C, D, E, C, A Open walk = A, B, C, D, E, C Trail – Trail is an open walk in which no edge is repeated. Vertex can be repeated. 2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 6 Here 1->3->8->6->3->2 is trail Also 1->3->8->6->3->2->1 will be a closed trail Circuit – Traversing a graph such that not an edge is repeated but vertex can be repeated and it is closed also i.e. it is a closed trail. Vertex can be repeated. Edge can not be repeated. Here 1->2->4->3->6->8->3->1 is a circuit. Circuit is a closed trail. These can have repeated vertices only. Path – It is a trail in which neither vertices nor edges are repeated i.e. if we traverse a graph such that we do not repeat a vertex and nor we repeat an edge. As path is also a trail, thus it is also an open walk. Vertex not repeated. Edge not repeated. Here 6->8->3->1->2->4 is a Path. Graph Theory | 7 6.6 connectedness and components A graph G is said to be connected if there exists a path between every pair of vertices. There should be at least one edge for every vertex in the graph. So that we can say that it is connected to some other vertex at the other side of the edge. Example: In the following graph, each vertex has its own edge connected to other edge. Hence it is a connected graph. In this example, there are two independent components, a-b-f-e and c-d, which are not connected to each other. Hence this is a disconnected graph. Cut Vertex: Let ‘G’ be a connected graph. A vertex V ∈ G is called a cut vertex of ‘G’, if ‘G-V’ (Delete ‘V’ from ‘G’) results in a disconnected graph. Example In the following graph, vertices ‘e’ and ‘c’ are the cut vertices. By removing ‘e’ or ‘c’, the graph will become a disconnected graph. 2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 8 Cut Edge (Bridge) Let ‘G’ be a connected graph. An edge ‘e’ ∈ G is called a cut edge if ‘G-e’ results in a disconnected graph. If removing an edge in a graph results into two or more graphs, then that edge is called a Cut Edge. Example In the following graph, the cut edge is [(c, e)] By removing the edge (c, e) from the graph, it becomes a disconnected graph. 6.7 Euler graphs If all the vertices of any connected graph have an even degree, then this type of graph will be known as the Euler graph. In other words, we can say that an Euler graph is a type of connected graph which have the Euler circuit. The simple example of Euler graph is described as follows: ------------------------------------------------------------------------------------------------- Graph Theory | 9  Practice Questions 1. a)Define : 4 (i) Graph (ii) Simple Graph (iii) null graph (iv) connected Graph. 2. What is a complete graph ? 3. Define isomorphic graphs. Give an example of the same. 4. A non-directed graph G has 8 edges. Find the number of vertices, if the degree of each vertex in G is 2. 5. Define an n-regular graph. 6. How many edges does a complete graph of 5 vertices have ? 7. Define regular graph. Find the number of edges of a 4-regular graph with 6 vertices. 8. Define diagraph. Also define indegree and outdegree of a diagraph. 9. Define a trail, a chain, cycle. ------------------------------------------------------------------------------------------------ 2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 10