Revision : Introduction to Graph Theory - Discrete Mathematics

Hinzugefügt: 2026-05-13

[00:00:00]Am I?

[00:00:02]>> Yes ma'am. Good morning ma'am.

[00:00:04]>> Yes ma'am. Good morning.

[00:00:06]>> Good morning.

[00:00:06]>> Good morning ma'am.

[00:00:08]>> Morning ma'am.

[00:00:09]>> How are you?

[00:00:13]>> Good ma'am.

[00:00:15]>> Good ma'am.

[00:00:15]>> Fine ma'am.

[00:00:17]>> Take care ma'am.

[00:00:18]>> Take care.

[00:00:20]So how was yesterday lecture? Are you getting?

[00:00:25]>> Yes.

[00:00:25]>> Yes ma'am.

[00:00:26]>> Yes ma'am.

[00:00:27]>> Yes ma'am.

[00:00:28]>> Yeah. all lectures I think uh motives or our lectures means you have to get in a very simpler way mean topics are tough maybe but uh you have to understand it's now it's actually topic top topics are very easy all terms are very easy if you think or understand nicely okay so I hope my PPT is visible graph theory >> yesterday we have started a new topic uh new unit of discrete mathematics that is a graph theory. Everyone is aware since childhood they are aware about the graphs but actually what is the means graphs and images or pictures. What is the difference? Difference is graphs is focused on the vertices and edges. If relationship suppose there are you can see this picture.

[00:01:22]If you see this picture there are 1 2 3 4 5 and 1 2 3 4 5 10 nodes. So if suppose there are 10 members in the family how the they uh that you are not in a family of very big family that is said to be a combined family. So how people are may related to each other maybe you are taking the topics of relation you have to explain first of all then you have to make these. So if you are talking about the taste of the family members, you are talking about the interest of the family members in the games. So how family members are interrelated to each other or so it will be shown by the edges. If you see these edges are not connected. So it means suppose this member of the family and that member of the family both are not having same type of interest or same types of hobby. So if you are giving the relationship name hobby. So ases are representing the relationship between two vertices whether they are related to not each other or not. Okay. So and vertices is specifically denoting some uh people place hobby in which you are interested. name of the persons or uh name of the cities, name of the places, name of the uh phenomena whatever you are doing there uh or you are drawing the graph for that you can give the name vertices and different different phenomenas are when related to each other then it will be shown by the by an edge. So we have seen graph is nothing but the collection of vertex set and edge set. Capital V is denoted by for vertex set and capital E for S set.

[00:03:08]Total number of edges, total number of vertices. Okay, I hope it is very clear here. We have discussed about the applications we have touched actually not completely I have discussed here. I cannot say completely it was covered. It will be discussed later. So we have discussed the concept of because you have to understand all the terms that involves in the graphs. So self loop and self loop and parallel or multiple ages.

[00:03:36]Parallelises means I think everyone is clear about the word parallel. So these are you can see the parallelises. These are the parallelises because starting and end point of vertices are same simple and multiple graph. If graph has no loop, no parallelises, simple graph otherwise multigraph, null graph, vetted graph, finite and infinite graph, adjgency or incidence that is not very much important you have to memorize or remember. If you understood then okay.

[00:04:06]So these terms are not for you.

[00:04:08]Adjacency and incidence for your uh uh means uh further learning the degree of that is very important. You have to understand if graph is given for any purpose. If you want to calculate degree of all the vertices you can calculate but you have to keep in mind you have to calculate loop twice. So we have calculated that also and different variety of vertex according to vertex the name of vertex and label directed graph. Yes we have touched the part directed graph. If directions are given and directions are given then what comes in the mind how to calculate degree of these vertices. So if you are going to calculate degree of vertices so you can see there some from this vertex some edges going from this vertex and some edges coming towards this vertex. So how to calculate degree? So there is a concept of in degree and outderee. In means incoming, outgoing means outgoing edges. That that is all about the edges.

[00:05:10]Edges. So in degree of vertices how to calculate the number of incoming edges towards that particular vertx in degree calculate outderee calculate the number of edges with vertx V as a or you can say number of outgoing edges from V. So towards V and from V that you have to keep in mind and you are going to calculate in degree and outderee very easily.

[00:05:35]Nothing tough here. Okay. So that was the yesterday's topic. Now we have to see if any student is facing problem to calculate these points and whatever degree or so at the class end of this class we can discuss. Okay. So that topic is not related to this. So we can see here the concept of complete graph.

[00:05:56]How we can say a graph is a complete graph. So very uh clearly if degree of each vertex students degree of each vertex is n minus one when graph total number of vertices is n. Okay in a simple graph simple graph means no parales no loop. Okay keep in mind no paralleges no loop and this graph vertices how many vertices n vertices.

[00:06:25]So what you have to check if degree of each vertex is n minus one. So graph is set to be the complete graph. Once again just imagine I'm not showing anything.

[00:06:35]If graph have eight number of vertices and each vertex vertex 1 2 3 4. If each vertex degree is seven with n vertices eight vertices 7 seven degree of each vertex then that graph is will be the category of complete graph. Okay. If n number of vertices are five and each vertex suppose there are vertx okay okay five vertex all five vertices are having four four degree all equal so that type of graph is said to be the complete graph okay we'll see an example this is a graph yes any graph any type of vertex and collection of edges set to be a graph yes how many vertices two n is equal to two here. So what should be the degree of each vertex? Only two vertex is here. So degree of each vertex is 2 minus one that is 1 and 1. It is a complete graph everyone according my definition.

[00:07:38]Yes, it is a complete graph and specific name for complete graph in books are given that is K1 K2 like this. So two vertices complete graph. So K2 name of this graph is K2.

[00:07:51]Once again everyone see this is a graph.

[00:07:55]Yes, this is a graph. How many vertices?

[00:07:57]N is equal to three. For being a complete graph n minus one degree of each vertex. Degree concept everyone clear who left yesterday class. Degrees means where direction is not given. How many wedges passing through this node?

[00:08:13]So degree is two. How many edges passing through this node? degree is 2. So you can see n is equal to n was three and degree of each vertx vertice vertex was 2 3 - 1 3 - 1 so this is a complete graph with three vertices the specific name is k3 okay now students how many vertices here four n is equal to four here this is a complete graph or Not we have to check degree of all vertices. 1 2 3. Degree of v_sub1 is three. 1 2 3. Degree of v_sub3 is three.

[00:08:56]1 2 3. Degree of v. V3 is three. V4 is three. So this is a category of complete graph. This is a special kind of graph. Complete graph. And you can say this is K4.

[00:09:15]Again check everyone. 1 2 3 4 five vertices. Degree of V1 is 1 2 3 4.

[00:09:22]Everyone can check. If I'm wrong, let me know. Degree of all five vertices, I can see there are four four. So, this is a complete graph.

[00:09:34]Everyone clear? Ma'am for the second vertice >> here.

[00:09:40]1 2 3.

[00:09:42]>> Ma'am, >> sorry.

[00:09:47]>> Ma'am, V1, V1, V5 and V3 has four vertices and rest of all have three vertices.

[00:09:56]>> Okay. Okay. Okay. I think I have missed one edge. This >> Yes, ma'am.

[00:10:00]>> Yes, ma'am.

[00:10:01]>> Sorry. Sorry.

[00:10:04]>> Thank you, >> ma'am. This definition of >> Yes ma'am ma'am this definition of complete graph is only for an undirected graph right.

[00:10:13]>> Huh right that is written here simple graph as well as simple graph means unirected graph. So some top down terms are for undirected graph where direction is not g some definitions will be for directed graph.

[00:10:29]>> Okay.

[00:10:29]>> Okay. Because that time if we cannot talk about degree we have to talk for in degree out degree and that will make it complicated.

[00:10:38]Okay.

[00:10:40]So if I'm using degree word so it means degree here is for unirected and if I am specifying in degree of degree so it is so that I have made actually in the in class here you can see this is the only with one direction degree of this k1 how many number of vertices >> vortexes = 1 and the um n minus one means zero here. So degree of this is so this is name is K1 is it okay everyone?

[00:11:16]K2 K3 K4 K5. Yeah I I was trying here to make K5. So there so that is the concept of complete graph at least note down the word complete graph everyone and topic is clear I will upload video no need to note down just focus here regular graph. And now everyone when I will tell you any other type of graph you have to find out differences that I told earlier that means complete graph and regular graph.

[00:11:46]So that concept or solid. So I told you now complete graph now switch to the regular graph. What is the definition?

[00:11:55]If each vertex of a graph has the same degree as every other vertex. The graph is regular graph. Now you will say yes complete graph is a regular graph right but there was only one condition extra total number of vertices n then degree of each vertex should be n minus one but here is no restriction okay don't know how many total number of vertices but degree of each vertex should be same all vertices having the same number of degree so that type of be degree that will set to be the that degree regular graph means you can see 1 2 3 4 5 number of vertices that's it here I'm not going to search 5 - 1 degree of each vertex is 4 4 no here I am just going to check how many vertices are vertices are having how many degrees so this vertex have degree two number of this vertex have degree two this vertx have degree two this vertex have degree two this vertx So all vertices have same degree and what is the degree? Degree is two. So this is set to be the two regular. So only just by seeing name you can identify degree of that particular graph was two. That's why two regular graph name is there. So this is a two regular graph. Agree everyone. Now check for three regular. This is three regular or not. So here 1 2 3 four. four number of vertices in this particular graph.

[00:13:31]I'm not concerned with n minus one degree. I'm going to check 1 2 3 1 2 3 1 2 3 1 2 3. All vertices have same number of degree. So here this is a three regular graph. Maybe it is a complete graph or what I'm just checking for regular graph concerned. 1 2 3 4 5 6 7 8 number of vertices.

[00:13:56]Okay. Degree of each vertex is 1 2 3 4.

[00:14:01]Four 1 2 3 4. Four edges passing through this node. 1 2 3 4. So this type of graph is the example of regular graph.

[00:14:11]And four degrees. So four regular graph.

[00:14:23]I hope no doubts here. Very simple terms I'm taking here. Now complement of graph just try to understand the very simple specific meaning of complement of graph means complement of that means something you have and complement means you don't have that particular thing. So let G be a graph. Now we have to understand G be a graph. So you have to imagine some nodes and edges. The graph complement of the graph G is the graph whose vertex set will be the same. Vertx set same and in which vertices are adjacent as the vertex set of G. Both vertex set will be common and in which vortices are adjacent if and only if they are not adjacent in G. So student I hope I hope you are not understood. Yeah, this is my graph. Okay, try to understand from my this example. Okay, vertices are here. Suppose this is E1.

[00:15:23]This is E2. This is E3. This is E4. This is E5 and E6 in this graph. So in this graph, this graph name is G. And now suppose I need to find a complement at that graph. So there also vertices will be same 1 2 3 4 5 where whatever V_sub_1, V_sub_2, V_3, V4 and V5. There also in the complemented graph vertices will be the same. But one more thing if E1 and E1 is present here between V_sub_1 and V_sub_2 that should not be definitely not in G complement that graph for each and every edges it is uh implied. Okay, it implies for each and every ages suppose E1, E2, E3, E4, 5 are present between these these these nodes.

[00:16:21]So between those those nodes, it should not be present in G component. Let try to make it clear. Suppose this is a graph. Okay, very simple. One and four edge. Okay, between 1 and two, yes, there is an edge. Between two and three, age is there. Between three and four, A is there. But in G complement where edges are present in between the vertices in those vertices edges should not be present in the G complement. It can be denoted by G complement or G bar some books. So here student vertices are same vertex set are same here V is having 1 2 3 4. This is the name of vertices and edge set is what? Suppose this is E1. This is E2. you you can give otherwise you can write the age name 1 2 age a name 2 3 a name 1 4 like that so set is E1 E2 and E3 1 2 and now you can see in the G complement 1 2 3 4 between 1 and two edges are not present okay between two and three edges S is not present between three and four A is not present but wherever edges were not present there we can see the edges So between two and four S's were not present. S was not present. I can see between two and four between 1 and three. Understood clearly. If you understood please try to note at least one or two words so that after one month if you see your notes or okay it's okay if you again you are going to watch video. So that is a very simple concept.

[00:18:01]Wherever edges were not present where you have to put edges.

[00:18:06]Again see this is a graph H and you can note down the vertices. Same vertices should be in the H complement but ases were not between 1 and two you can put between two and between five and four you can put between 1 and four edges were not edge was not there. So you can put between uh three and five you cannot see edge you can put otherwise remove all the edges.

[00:18:38]I hope pencil will work nicely here for complement of a graph.

[00:18:44]Okay student got it.

[00:18:48]Got it.

[00:18:48]>> Yes ma'am.

[00:18:50]>> Yes ma'am ma'am.

[00:18:52]>> Good.

[00:18:54]Now try to understand. Now topic is going to be a little little bit complex.

[00:18:59]Bipartite graph. Bipartite graph. Try to understand the meaning of the graph.

[00:19:04]Bipartite. All graphs have their own meaning. Okay. What is the meaning of bipartite? Pi means two. Partite mean partitions. Okay. So let G E B comma E be a graph. Okay. Vertex at S. G be a bipartite graph. If it vertex at B can be listen G be a bipartite graph. If it vertex at V can be partitioned into two non empty disjoint subsets that is very important non- empty vertices disjoint disjoint means I think students you have read subsets or sets disjoint v_sub_1 and v_sub_2 are disjoint if they don't have any common element right got it so disjoint subsets v_sub_1 and v_sub_2 such that each edge has one end in v_sub_1 and one end in v_sub_2 okay try to understand a g a bipartite graph if it's vertx set v suppose this is a vertex set v it can be partitioned into two non- empty disjoint subsets v_sub_1 and v_sub_2 so two part dis divide such that each a has one end in v_sub_1 and one end in v_sub_2 mean next graph it's got one end be aes how many aes in the graph so total number of aes in the graph so one end comes from v_sub_1 and other end should come from v_sub_2 like that so you have to do partition like this if edges are there so edges one end v1 say Okay. And second end should come from V_sub_2. So this is E1 suppose. Got it?

[00:21:03]So if G a graph then we can divide the vertex here into two disjoint subsets.

[00:21:11]Disjoint mean there should no common vertices.

[00:21:15]Okay. Each edge this is a graph G. Okay. Vertex at V is equal to suppose I given giving the name this is A B C D E F G. So what is a vertex at A B C D E F G and uh I'm going to say this is a bipartite graph because I'm able to partition V into two non- empty disjointed subset V_sub1 and V_sub_2. So v_sub_1 I can see a comma b comma c and v_sub_2 d e f and g and student this is disjoint disjoint here because there is no common vertices all together right and each edge how many edges is 1 2 3 4 s each edge so even is a s and what is the even end points means initial and no ter terminal terminal in point A D right what is the edge E2 suppose I am giving the name E2 is B G what is the name of E3 E3 I given the name here so end points of E3 is C and F okay what is E for end points that is C and E any other one >> there are five pages actually >> five I think DF F I missed.

[00:22:49]Yes. E5. So student what is the meaning of this definition? I am able to divide the vertx set into two partitions such that all ed is one end of is is come from V_sub_1 and other is come from V_sub_2. A B C D A B C One end from V_sub_1 and other end of this edge is from V_sub_2.

[00:23:17]Try to understand is it clear everyone this is the bipartite and it is very complex if you're going to read different different books follow any book one book >> ma'am >> yes >> can bipartite graphs be directional >> directional uh means what you can say directional is there so then you have to see check direction so here direction doesn't matter >> okay Okay, I'm talking about only the edge. Okay, so here for definition, purpose, direction not matter matter here. Okay, everyone got it? I am writing whatever I have written. Now if you will write this thing and after 1 month if you are during your exam you'll see then that time definition otherwise most of the student used to be uh confused for my experience I'm telling you.

[00:24:13]Okay. So note down this and then you will get clear if you are reading after sometimes also. So now next example is suppose this is and try to make you clear with this example student to yourself make you clear V is actually here 1 2 3 4 but it has been partition into V_sub_1 and V_sub_2 Go.

[00:25:09]I'm making some graph. Check. This is bipartite. Yes >> ma'am. So only a onepoint graph will be a graph which can never be bipartite.

[00:25:20]Every all other graph >> this graph you are saying.

[00:25:23]>> Yes ma'am.

[00:25:25]>> Ma'am all the other graphs are always going to be bipartite.

[00:25:30]>> Yes. Because there is actually definition is not fulfilling.

[00:25:33]>> Yes ma'am.

[00:25:34]>> Good question. So now students if you are agree with uh this graph if not agree then you ask me otherwise I'm drawing one more because this is a important important point of view because uh you can get to check this is a bipartite or not.

[00:25:55]So there should be no confusion.

[00:25:59]I hope my graph is correct.

[00:26:27]check student vortex set of this graph.

[00:26:56]This is a biparted graph or not.

[00:27:00]If age is there you have to check one end of that age should come from v_sub_1 other is suppose name is given v_sub1 v_sub1 this is small v_sub1 and v_sub_2 you understand like this so v_sub_1 and v_sub_2 here so here v_sub_1 v_sub_2 v_ub3 v5 v4 from aes you can find vortex at V6 and then you can check your definition.

[00:27:33]So V_sub1 have these number of element V_sub_1 comma V3 comma V5 and V2 V4 V6 V7.

[00:27:43]So from vertex edges I can find now I can I'm going to write v_sub_1 v_ub3 comma v5 [snorts] and v_sub_2 v_ub_2 v4 v6 and you can check v7 okay so check v_sub_1 v_sub_2 edge is there v_ub3 v6 V6 edge is there. V5 V7 edge is there and V3 V7 edge is there.

[00:28:25]V5 V4 age is there and both are coming from one vortex from one end is coming from other vortex set. Right student everyone. Now for this you can check suppose v_sub_1 is here 1 2 3 I'm not able to see screen if anyone is typing something because I am full screen I have done full screen here 4a 5 so now you can check it is bipartite or not I'm telling you my method 1 4 means one is coming from here and 1 14 age is there now see other age 1 five if I'm guessing this is correct vertic then it is okay 1 5 so 1 and five. 2 and five. 2 and five.

[00:29:11]3 and four. If edges are there then it should come from first and second one.

[00:29:18]So three and four. Yes. Three is here and four is here. So this is the example of bipartite crown.

[00:29:27]Got it everyone?

[00:29:30]>> Yes ma'am.

[00:29:30]>> Yes ma'am. Yes ma'am.

[00:29:32]>> Everyone.

[00:29:33]Now >> yes. One thing you have to notice is notice there is no condition means all vertices all vertices are connected from each other from v_sub_1 and v_sub_2 1 2 3 uh vertices are in v_sub1 everyone listen why I'm telling you because it depends on it is for next definition that I am going to tell you this is a bipartite graph yes because vertices are coming from first and uh edges of uh each edges are from first vertex set and second vertex set end vertices. Okay.

[00:30:13]Now you can see here one and five are connected. Three and four are connected but it is not mandatory here. All edges of all vertices of this vertex set should be connect to all vertices of this means two and four are not connected. Three and five are not connected. Three and five is not connected. So this type of conditions will be going to apply for complete biapartite graph because a complete bipartite graph is a bipartite graph with bipartition v_sub_1 and v_sub_2 in which each vertx set of v_sub_1 each that is important each vertex of v_sub_1 is should be connected to an by an to each vertex of v_sub_2 means for bi complete bipartite graph I'm just giving you example It should be connected from here also.

[00:31:10]It should be connected from here also.

[00:31:12]It should be connected means all vertices should be connected. So means it should be one should be connected to four and five. Two should be connected to four and five. Three should be connected to four and five. Like this type of example demands complete bipartite graph. Yeah.

[00:31:32]See example of complete bipartite graph and complete word is there. So it is denoted by K33 K34 one vertx set uh number of vertices and other vertic set number of vertices you can see here. So student for complete bipartite graph if you see vertx set here v_sub_1 v_sub_2 v3 uh 1 2 3 4 5 6 1 is connected to four one is connect should be connected to five one should be connected to six important definition two should be connected to four two should be connected to five two should be connected to six by an edge. Okay.

[00:32:12]Three should be connected to four. Three should be connected to five. Three should be connected to six by an H. And same for one. You can see if it is there that is the not example of only bipartite. This is a complete bipartite graph. Here you can see some edges means here 1 2. So 1 4 was present there. But 1 3 was also present. And here 2 3 was present and 2 4 is also present. Right?

[00:32:44]So you can say this is a complete bipartite if this is possible. And here also you can see this is pres connected to this but not connected to other one.

[00:32:53]But all definitions will follow here.

[00:32:57]You can see here 1 2 3 first vortex set 4 5 6 7 second vertex set. And u you can see one is connected to all other vertices present in second vortex set.

[00:33:11]Two is connected to you can check student if anything is doubtful.

[00:33:19]So all vortex set should be connected to each and every uh second vertic set elements. So that type of complete bverile graph is denoted by k ma n. M is the first vortex set um number of element and uh second N is the second vertx set element.

[00:33:52]Okay, I want to give you one more example for complete bipartite graph.

[00:33:57]Students are going to check I'm correct or not.

[00:34:24]Yeah, my graph is now complete. Everyone check this is a complete bipartite graph or no not.

[00:34:42]I think the way I am making this graph you can understand this is a complete graph hyped graph.

[00:34:57]So two more examples uh for complete bipart graph.

[00:35:04]A very interesting example. I like this example.

[00:35:09]This is like a star, a ring.

[00:35:14]This is K15. I know I think you can understand why K15 one set that is having a very single element. Another set is a so this is a K15 example of complete bipartite ground.

[00:35:36]Can I proceed to next topic made it?

[00:35:42]>> Yes ma'am.

[00:35:43]>> Yes ma'am.

[00:35:44]>> Good.

[00:35:45]>> Yes ma'am.

[00:35:47]>> So now very simple set theory definition of union and intersection of two. If you are learning graph theory so you should know maybe somewhere you can get g. If there are two graphs G1 and V1 just G1 and G2 and with vertices set B1 B2 edge sets B1 and E1 and E2. So what do you understand by union of two graphs? Union of two graphs means you are going to take union of these vertices set and those edges sets. Okay. So that will be the and name of another graph is mean a new graph is going to be created. Okay. with the help of G1 and G2 means we are going to merge. So we are merging V_sub1 and vertices set and edges sets. So that is new graph G3 is going to be created and vertex set with V1 U union V_sub_2 union everyone is knowing the set theory that's why I'm not put in this topic because if you are running set theory why I'm going for 9 10th 11th 12th revision so in prerequisites I put here set theory knowledge like that so means here com take all the vertx set and take all the edges in the union so that is the example of union of two graphs. And now what is the meaning of intersection of two graphs? Means this is like a intersection of two sets. So intersection of means G1 and G2. Vert.

[00:37:14]What sets intersection meanx common that you have to take in the new graph that is the G1 intersection G2. It is denoted by G4. Okay.

[00:37:27]So and which those edges if common are in G1 as well as in G2 then you have to take in the intersection. Intersection means common thing always uh get definition with name. So if there are two graphs G and H. So students here G union H is formed by using this definition. Now you are you try to get how this has been formed with my definition what I given and G intersection H this is a new graph G3 as I given the name and this is a new graph G4 and it has been formed by using the set theory definition union and intersection it is very easy okay try to get you can see here vertx set 1 2 3 4 5 in Edge same vortex set okay 1 2 3 5 edge set E here you have to give the name E1 E2 E3 or I think don't give name otherwise it will be confusing to here student you can see here five is present there you have to put all thing you have to consider whatever in G and whatever in H all points all phenomena you have to consider when you are creating G union H5 is present there it should be here one two is present here and here common though you have to take those you have to take also common things but you have to take another thing also if you see uh 2 4 is here 2 4 you have to take if you see here 43 is connected you have to see nothing you have to leave here everything you have to consider so whatever in G1 1 whatever in G2 you have to consider for G1 union G2 and 1 14 is there 25 is here not present and 25 is present here so then you have to take 25 H are you getting because for union you have to consider for G properties a number of edges as well as number of edges of H you can see vertices are same here you can see G intersection H common things only common ages. First of all make vertex vertices five common five is here 1 15 is not there. So no common edges 1 two is present here 1 12 is present here. Yes you can take one two because 1 2 is common for edge 1 2 is edge. 1 4 age is here. 1 4 age is here. You can take here. 2 3 age is here. 2 3 is not here.

[00:40:16]So you can't take 3 4 age is here. 3 4 A is common here. So you can take 2 4 is not anything else. Um nothing. Yes. 2 4 I have not mentioned here. So you can see only common as I have considered here and all the vertex union or intersection vertices are common. So you can take and student if in the case if both are having dissimilar edges vertices mean number of vertices suppose six for that type of example. So here you have to include six but in vertex set it will be not common. So you should not include six. Are you getting my point? Intersection means vertex set intersection and s set intersection. So here both aes are same. So I have taken.

[00:41:09]Got it. Can I proceed to next topic?

[00:41:12]Anyone?

[00:41:14]>> Yes ma'am.

[00:41:14]>> Yes ma'am.

[00:41:16]>> Yes ma'am.

[00:41:18]>> More examples but I will upload. I think topic is clear.

[00:41:22]What is the time?

[00:41:25]Yeah we have time.

[00:41:29]Representing graph in computer memory.

[00:41:31]Okay I'm able to prepare graph with my pen and paper. So how we are going to read everyone and then we are going to the way how to feed the these graphs in our computer memory. So there is a standard way of maintaining graph in the memory of computer. This is called sequential representation of graph means by using adjacency matrix concept. We have to understand the adjacency matrix concept like zero and one and then we are going to use we have we are going to feed these graph in our computer. we can feed up these graphs in our computer memory. So graph with m vertices and nes that is one uh things also I want to tell you here matrices and why we are because if we are only giving the data we are giving input to the computer memory. So that is okay when graphs are very simple means not complicated. But suppose there is a 100 of vertices and 100 of edges and 200 of edges then how you are going to give inputs to by using programming that time you have to convert these graph into the form of in the form of matrices that form is known as adjacency or adjacency matrix of that particular graph. Okay. And when and if m vertices and n is our graph and graph is dense. So matrix will be of order n² that is the definition but I think I will not focus here. I will because we have less time. So we'll focus how to create uh different type of matrices. So there are two matrices we can create for uses of computer. One is the adjacency matrix and another is a incident matrix.

[00:43:20]Adjacency matrix are based on the uh just listen adjacency matrix based on the adjacent edges like if edges are adjacent to two vertices so number will come one if not adjacent number is zero I everyone is knowing computer understand only the length zero and one binary number that's why this structure you can see so here adjacency matrix of graph let G is a graph with vertx set and s set n vertx prices. Okay. So an n cross n matrix so n cross n I'm creating here square matrix is an adjacy matrix of the graph if and only if a i j is one for i j belongs to e. Why? What is the meaning? matrix 2a 3 but the second row third column.

[00:44:15]Okay. So one present when two three edge will be there in the edge set. Are you getting student? But if you are not going with definition it's okay. Just listen to me. If edges is there between two end point so there you have to write suppose two and three. So two and three have edges have edge you have to mention one there in the matrix. If suppose there is an one in and two and four have an edge you have to mention that one three and four. So here three here four here three and here four. So three and four don't have an edge. So you have to mention uh beside that zero. So one for yes edge edge is present zero for ed is not present. That is very very simple.

[00:45:03]Try to understand this is a graph. Okay.

[00:45:06]number of vertices you can see. So what we have to do we have to create a square matrix. Okay. So square matrix how many nodes 1 2 3 4 up to 9 1 2 3 4 9 you have to write here in row row wise and as well as for column wise. So here you can see one and two between one and two vertex is there. See student if loop were was present here then we can put one and one there is a one edge that is a loop okay for loop we can put zero here so this definition is applicable for multigraph also so here between 1 and two is present so one and two a will be present as well as for two and one also so because one and two direction is not here So 1 and two as is present here.

[00:46:01]Between 1 and two, one is present here.

[00:46:03]So between two and one also you put one.

[00:46:07]Concentrate student only for 1 minute you are going to learn. So 2 and 3 is present there. So 2 and 3 and 3 and two.

[00:46:14]Two before that you have to put one.

[00:46:17]Three and two one is here and 2 and 3 1 is there. In the same way 3 4 and 4 1 3 4 and 4 3 I think you got it. 2 6 1 is present here 6 and two you also put one so one for is present zero for is absence clear everyone I don't think everything I need to uh mention here everything >> yes ma'am >> good not getting more right only just listening because in tutorial you will do so okay I'm giving you a concept see how I created This this is a graph and I have created this adjacency matrix for this particular graph.

[00:47:10]Is it okay?

[00:47:37]Actually this will be converted into one. This is showing only number of bases one. But when we are putting uh uh in computer memory this data we have to convert into the one only for presence and absence. But three is counting here because if you put any programming here to convert. So they will uh the that programming will convert into three because three times of between a and b suppose here a b c d a b c d. Okay. So this is three showing here between D and A there are three number of A's because you have put all the programming you have created means A and B if A is there so it should count one. So like that. So it is we are counting manually. So we are going to count three here. Okay. But A is there present between A and B. So computer will count one here because A and B between A and B one is present there like that. loop for loop also if computer will if I'll start counting so I will count because one age is from here A and D so where is A and D not here for C I'm looking for yeah C and D so for C to C to C also student you can see for loop I I wanted to tell you one example for loop also so C to C only between B to B 0 is there between A to A 0 is there Between D to D zero is there but between C to C this is the C and this is a C there is a one because C is having loop. I hope you got it >> ma'am. So the uh >> in exam you have to do like this.

[00:49:23]>> Uh ma'am so the statement that is written above it's wrong >> where >> ma'am the diagonal entries of an adjacency matrix are zero.

[00:49:34]This a graph has no this is not wrong. I am saying if uh okay I have not read the diagonal entries of an adjacence matrix are zero when the graph will will have no s with both end the same okay that is but I will explain better I don't have example of that >> ma'am for the loop uh we count two times right >> loop if from C to C I am counting here ed ages between two C and D and A is there so we'll count one so here I'm telling you loop or loop loop is loop is here at C to C and age is there is it so that's why one is present here got it >> so ma'am do we have uh when we have an exam or a question do we need to enter three or whatever are the number of you have to do this because we are doing manually that's why I'm telling you in exam you have to do like this >> okay >> okay but in programming when you will do now it will be converted into zero and one only that is a later part okay now you student you can check for this I will upload at least uh up to this topic I will upload by today what is the meaning of incidence matrix of a graph graph incident mark is showing how many times that particular edge has been incident on that particular vortex that is between vertices and edges. So if you see you what you have to do for incidence matrix if vertices whatever vortex sets elements are there you have to mention here and if from v_sub_1 e1 is pass passing then you have to put one here from v_sub1 e2 is passing then you have to mention one here. So this type of incidence matrix also you can create here for this purpose.

[00:51:47]E3 from V_sub1 E3 is create creating or E3 is passing. No. So it is zero here.

[00:51:54]From V_sub1 E4 is passing. No. So zero here. E5 E6 like this. From V_sub_2 you can see E3, E6 and E4. E3 E6 and E4. And for others rest of the vertices zero. Like that. This is the concept of incidence matrix. So it is showing the incident of edges on the particular vertex. That is the name here. If you you want to know how many edges are incident on the vertices so then you can see the incidence matrix.

[00:52:35]students. Got it? And please create this E1, E2, E3, E4, E5, E6.

[00:52:52]Okay. E7. Up to E7.

[00:52:58]We have time 5 minutes.

[00:53:02]2 minutes. So student can you uh solve this problem? Just note down or click the picture. I have some more pictures for your example uh for your exercise.

[00:53:14]Incidence matrix of the given graph. So you have to find you have to show the incidence of the edges on the particular vortex.

[00:53:23]These example also you can take for your problem solving.

[00:53:28]Ma'am, so an incidence matrix does not have to be a square matrix but an adjacency one has to.

[00:53:36]>> Yes, because here any vertx can have number of uh what you can say number of incident of edges, right? That is the reason, >> right?

[00:53:46]>> Okay. Thank you.

[00:53:48]and student uh I think in tutorial se uh tutorial class I heard one student uh was curious about to find determinant of higher order matrix right so actually I want to take your matlab class uh when you are free because this is the time when I can take so that is very easy to find to write matrix or it is very easy to uh find the determinant or inverse of any matrix that is a within a second you are going to get student.

[00:54:24]So I want to show you here uh when one day uh we get time and I will complete matrix portion with matlab also.

[00:54:37]Okay. So how matrix is created and if within a second if you see so you can get inverse of that particular matrix also. So see how I think my screen is visible.

[00:54:51]>> So how fast I'm creating the matrix and how fast I'm getting the inverse of the matrix. If you want determinant of that matrix whatever 3 + 3 or 100 + 100 but maybe u little bit determinant of this matrix A is I have shown here also. So minus 36 or adjint of that matrix if you want to find. So everything uh you can calculate maybe if I forgot any formula.

[00:55:17]So for adjint whatever is there. Okay. So I have I think anything else I need to for adjint. So that is means by using a software you can solve matrix and you can check your result also. That is very simple. So that's why MATLAB is available here. That's why I'm telling you here. So student till uh whatever topics are there you have to revise and then you have to come in the next class because maybe I can use any topic.

[00:55:47]So so many topics are there some formulas are there for uh graph theory and it will take this week full or maybe next week.

[00:56:00]So be ready for nest.