Various type of Graphs-I

Hello friends, welcome to my lecture on various types of Graphs. Let us first see why we need graph theory, many situations that occur in computer science, physical science, communication science, economics and many other areas can be analysed by using techniques found in a relatively new area of mathematics called graph theory. The graph can be used to represent almost any problem involving discrete arrangements of objects, where concern is not with the internal properties of these objects but with relationship among them. We begin with basic graph terminology and then we will discuss some important concepts in graph theory with many applications of graphs. Now, let us first define what we mean by a graph, a graph consist of two parts V equal to VG okay, whose elements are called vertices, points or nodes okay, a graph is G, this is graph is G. A graph G consist of two parts, a set V equal to VG whose elements are called vertices, points or nodes. A collection E equal to EG of unordered pairs of vertices called edges. We write G V, E when we want to emphasise the two parts of G. Let us consider the graph shown in this figure, okay. Here you can see that, there are four vertices in this is graph. Okay, A, B, C and D. Okay and A, B, C, D are joined by means of the edges e1, e1 is A, B, e4 that is A, C, e2 that is B, C, e3 that is C, D and B, D, that is e5 okay, so there are four vertices A, B, C, D and E. Okay, consist E is the set of edges, E consist of five edges e1, e2, e3, e4, e5, so this is a graph. Now, let us see what is a simple graph? A graph that has neither self-loops nor parallel edges okay are called a simple graph. So this graph is a simple graph, this graph is a simple graph, because it does not contain parallel edges okay, now are self-loops, what are simple parallel ages and loops. Let us see, we first define multigraph, in a multigraph, each vertex V is represented by a dot or a small circle and each edge E equal to u, v is represented by a curve which connects end points u and v, a graph is generally shown by drawing its diagram rather than by explicitly listing its vertices and edges. So, we have talked about parallel edges, what are parallel edges? All edges having the same pair of end vertices are called parallel edges. And self-loop is an edge having the same vertices is called a self-loop. Let us look at this figure, in this is a multigraph, you can see here there are four vertices A, B, C and D. Okay and the edges are e1. Okay, e1, which is A, B and then we have e2, e2 is B, C and then e3, e3 is C, D, e4, e4 is A, C, e5, e5 is A, C again, e6 B, D, e7 is D, D. So, you can see that this edge e7 has same end vertices okay, D, D same end vertices, so this is a self-loop and e4 and e5 edges have the same end vertices A, C. Okay, e4 and e5 have the same end vertices, so e4 and e5 are parallel edges, so this graph consist of parallel edges, e4 and e5 and self-loop e7 okay. Now, let us go to this diagram okay, here again we see that there are 1, 2, 3, 4, 5, 5 vertices okay, vertices are P1, P2, P3, P4, P5 okay and the set of edges is E equal to P1, P1, P1, P1 is a because P1, P1 means it has the same end vertices okay, so same, but this is here, so this is a self-loop, so this is a self-loop because this edge has same end vertices P1, P1 okay, now we have P2, P3. Okay, P2, P3 and we have P3, P2 okay, since here again the end vertices are same, these are parallel edges okay, so P2, P3 and P3, P2 are parallel edges okay and we have P2, P4, P2, P4, we have P4, P1 okay, P4, P1 here, P5, P4 okay, so this is a multigraph which consist of one self-loop and two parallel edges. A multigraph is said to be finite if both the set of vertices is finite and the set of edges is finite, now let us know that if there are only finite number of vertices in the graph that it must automatically having a finite number of edges because when the vertices are finite, when you join them you will have only finite number of edges, so the graph must be finite, so multigraph will be called finite if number of vertices are actually finite. Now trivial graph, a trivial graph is the graph with one vertex okay and no edges, so in the case of a trivial graph there is one vertex, no edges. The empty graph is the graph with no vertices and no edges okay. Isolated vertex, a vertex having no edge incident on it is called an isolated vertex. Let us look at this figure. Okay, this graph, so you see here we have five vertices okay, P1, P2, P3, P4, P5 okay, five vertices are there, edges are P2, P4 okay, P2, P3, P3, P5, P5, P4 and this P1, it has no edges incident on it, so this P1 is an isolated vertex because though there are no edges incident on it, so it is an isolated vertex. Now, let G equal to G V, E have five vertices okay, let G equal to G V,E have five vertices. Find the maximum number m of the edges in E if G is a graph okay, since to draw an edge you have to collect two vertices okay, so 5 C2, number of edges, if you take any two vertices okay, if you take any two vertices then you have number of edges will be 5 C2, in a graph, in a graph means a simple graph here okay, we have by graph here we means simple graph, where there are no loops and no parallel edges okay, so you take any two vertices to draw an edge okay, we will have number of edges 5 C2 , 5 C2 means 10. So when no self-loops and no parallel edges are there and we have five vertices, number of maximum, maximum number of edges could be 5 C2 okay, that is 10. Now G is a multigraph, if G is a multi-graph, then you can have any number of parallel edges, any number of self-loops okay, so there is no maximum number of edges in E. Okay, in the case of a multigraph. Now suppose e equal to u, v is an graph G. Okay, then u and v are endpoints of e, the vertex u is called adjacent to the vertex v and the edge e is said to be incident on u and v on v. Okay, so if you take u and v two points okay, the two vertices and this is an edge okay, then u and v are called adjacent to each other and e is said to be incident on u and v. Degree of a vertex okay, the degree of a vertex could be either even or odd and how do we define the degree? The degree of a vertex v in a graph written as degree v is equal to the number of edges which are incident on v or in other words the number of edges which contain v as an endpoint, the vertex v is said to be even or odd according as the degree of v is even or odd okay. Now let us see, we have, we see this example. Okay, we will consider this theorem first, the sum of degrees of the vertices of a graph is equal to twice the number of edges, this is because each edge is counted twice. Okay and counting the degree of the vertices of a graph G, so suppose you have a graph G and we have two vertices okay, u and v, this is the edge okay, then while counting the degree of u okay, this vertex, this edge will be counted while counting the degree of v, this edge again will be counted, so since each edge is counted twice in counting the degrees, degree of the vertices of a graph G. Therefore, the sum of degrees of the vertices of a graph is equal to twice the number of edges. Now, let us consider this graph. Okay, this graph G equal to G V, E in this figure describe G formally, so this, let us see how many, so in order to describe G V, E we need to know how many vertices are there and how many edges are there, so V equal to V, G, this denotes the vertices okay, vertices are a, b, c, d, e, these are the vertices and then we have E equal to E, G okay. So we have, now let us list the edges of this multigraph okay, so we have a, b okay, this is a, b, than we have b, c, we have taken this, we have taken this, then we have a, c, so we have considered this one and then we have b, e, then we have e, c and then we have c, d, we also have a, d okay, so we have 1, 2, 3, 4, 5, 6 and 7. Okay, seven edges are there okay, now degree of each vertex we have to find okay, so degree of a let us see, degree of a, now you see how many edges are incident on A. So one that is a, b, then a, c and then a, d 3 edges are incident on a, so degree of a equal to 3, degree of b, we have this edge b, a or you can say a, b and then we have e, b and then we have c, b okay, so 3 edges are incident on b and then we have degree of c, so we have a, c, incident on c. b, c and we have e, c. Okay and we have d, c also, so we have 4 and then we have degree of let us say d okay, so we have c, d incident on d, we have a, d incident on d, so degree of d is 2 okay and this one and this one. Now, they are incident on d and then we have degree of e, so how many edges are incident on e. b, e, and c, e. Okay, so we have 2 and sum of degrees of the vertices of this multigraph are 3 plus 3 6, 6 plus 4 10, 12, 14, sum of degrees is equal to 14 and the edges are 7, number of edges are, so you can see this is twice the number of edges, so this verifies the theorem which we have just now seen, the sum of the degrees of the vertices of a graph is equal to twice the number of edges. Now, let us consider the graph G when V, G equal to A, B, C, D, so in this graph, there are 4 vertices A, B, C and we have D. Okay, E,G, now this is the set of edges, so we have edges are A, B and we have B, C, we have B, D and we have C, D okay, so let us find the degree, so this is a multigraph okay and we have the degree and parity of, degree of each vertex, degree of A, there is only 1 edge incident on A, so we have 1, degree of B equal to, now 1, 2, 3. 3 edges are incident on B. So we have 3 degree of C, there are 2 edges, incident on C, so we have 2 and degree of D, there are 1, 2. 2 edges, incident on D, so we have 2, so total of sum of degrees equal to 4 plus 2 plus 2, that is 8 okay and edges are 1, 2, 3, 4 okay and number of edges are 4. Okay, so sum of degrees of the vertices of G is equal to twice the number of edges of G okay, so that verifies the theorem we have stated. Thank you very much for your attention.