This session epitomizes the brutal efficiency of elite technical education, transforming profound mathematical concepts into a high-speed manual for academic survival. It is a masterclass in producing disciplined problem-solvers rather than fostering genuine creative inquiry.
Install our extension to search inside any video instantly.
Maths 1 - Rivision session 1 - LiveAdded:
3. So this will be 27 by 3 and 1 by 3.
So this is going to give you 26x3.
So this was a pretty simple question.
Let's try a slightly different one, a slightly more complicated one. This one.
Give this one a try. It shouldn't take very long though.
Ma'am, please scroll down. Scroll up.
>> It should be to the power x² + c.
>> What we did here is >> you have a doubt in the previous question or this one that will be that we'll be attempting now.
>> No, we discussed right this one.
>> This one.
Just a second.
Yeah, it's fine now.
>> So for this one, let's do this one now.
So this is just simple substitution method. You have to substitute x² = t or any other variable. So uh if your x² is d then 2x if you differentiate both these sides with respect to t you have 2x here and dt by dx here right. So simply you can just write 2x dx on this side and dt on that side.
So that will give you 2x dx. Now you have this thing here 2x dx and you can replace 2x dx with dt. So this entire then becomes e to the power t and then 2x dx is just dt. So this thing so in place of x² we have t now and in place of 2x dx we have dt now. So this integration now become this is a simple integration which we all know the integral of e to the power t is just d to the power t.
And then you can have so because everything was given in terms of x. So you need the answer in terms of x right this will be e to the power x² and a constant is always there. So this should be the answer.
While integrating a constant is always involved. So this should be the answer.
Okay. Then coming to the next question.
This is the next question. Give this one a try.
X sin X + cos X + C.
So let's do this one. Here you have X cos X. you have to use integration by parts. So integration by parts the formula for that is if you have ux dx dx this gives you just u then integral of v with respect to x then integral derivative of u with respect to x and integral of v with respect to x and this entire thing with respect to x.
Right?
This is it. So let's have this as and the order for u is this. You have to use this thing highlight. So because uh so u function has to be considered this one this is a trigonometric function and this is an arithmetic function. So you should be considering x as you can also see that this if you derate x with respect to x you just get one. So okay just simply follow this line for u function for choosing u.
So this should be your u function. This should be v. So this is going to give you so integration of x cos x then will be x as it is integration of cos x then the dativeative of x. So it's dx by dx and then integral of cos x with respect to x and then dx right and this will be x sin x minus 1 here and then integration of cos x with respect to x. So it will be x time is going to give you x sin x is already here and then the integration of this thing is minus of cos x right so it will be plus cos x and the constant is always included at the end. So this should be the answer x sin x + cos x + c.
So it's this should be the right answer.
It should be zero ma'am.
>> Yes, >> we can split it into two parts like minus pi to 0 then 0 to pi >> and it's too >> odd function. So >> you can do it this way or you can just simply integrate it. So one way is to integrate the usual way that you do integrate and then use the limits and the other one is uh using the odd even functions thing.
So uh if you have something like if you have a function where your f of x is equals to f of minus x if this thing is equals to f of x with a negative side then this means if you have the integral of such function from let's say min -1 to 1 you have this function then you can write this as -1 to 0 fx not writing dx here so uh this thing so this function is just going to be 0 to 1 fx and this is going to be so you can instead of this you can just write this as 0 to 1 f of - x right and this is just minus f ofx this is integration of minus fx from 0 to 1 this is one so you have basically it's just This as can >> ma'am your voice is breaking >> minus sin x would become like x >> if you have a function. Okay, let's well let's we'll have a look at this function later. If this function is a function like this, we'll come to that one later. But before that, if you have a function where if you substitute x in place of minus x, then if it's equal to this, for example, let's say you have x cube. Now, if your function is x cub, if I'll replace x with a minus x, I'd have - x, which is equals to this thing - x, right? So this function is a function of this form right where if you replace x with a negative x you will get minus of fx. This is minus this is fx and this is >> ma'am your voice is breaking.
>> Okay. Is it better now?
No ma'am still breaking. I mean sometimes uh it happens in between.
>> Okay.
So try to be >> ma'am again it's breaking.
Okay, >> basically the f(x) is odd here. So uh it will result to zero by the property.
You can wait so much later. We try to figure something out, but now I can't do anything. It's connectivity issue on my end, I guess.
>> It's okay, ma'am. You can continue with it.
>> Oh, is it fine now?
>> Yes, ma'am. It's better now.
>> Okay. So, what we were discussing here is if you have a function of this form, if you have a function and example of these functions are one is obviously sinx. Sinx is a function.
Examples of such functions.
examples where your f ofx f of minus x is the same as minus of f_sub_x. So such examples are sin x then you have x then you have x cq or in fact any power any odd power of x x to the power 2 n + 1 then uh uh do we have uh more functions like we have a lot of functions like that I can't think of both functions >> cos x also >> no cos x is not function not such function not >> yeah x cos x works right so x cos x is also one such function where you have - x so if you replace it this is your fx then your f of min - x will be f of - x will be min - x and cos of - x and cos of - x is just cos x so it will be - x cos x which is the same as minus of f_sub_x. So this is also one such function x cos x.
Then you can have in similar way in this manner you can have x² sin x2 that also works. You can have sin x cos x2 that also works.
So these are the functions where such things where this condition holds. So if you have a function like that and in fact the question that you have your x plus sin pix function. If you have something like if I replace x with a minus x I'll have minus x plus sin of pi and minus x here. So it will just be minus of pix.
If I replace x with a minus x, this is what I'm going to get. Right? If this is f(x), then your f of min - x is this.
So your f of min - x is actually minus x or you'll have here you'll have minus of x - sin p<unk> x and this is just - x + sin pix and this entire thing is just fx right so this is f_sub_x minus of fx so f of min - x is minus of fx and we've just checked just seen this thing here that if your f of min - x is minus f of x that means in this rule is in general it's not from minus1 to 1 it's from if you have a function of this form so if you have to generalize it you can have minus a here and a here right obviously you'll have to take a greater than zero because if your a is less than zero then I I can't write three and minus 3 I can't write the limits as this Right?
So your a is greater than zero. That's understood. If that happens then the integration of fx provided your fx is one such function is of this form. f of min - x is the same as minus fx.
Then and these are also called odd functions because it's you can remember it from here. The odd powers are of this form.
So you can these are also called odd functions.
So if your a is greater than zero, you can break this thing from minus a to minus a to 0 and then 0 to a and this thing from so this then becomes if I'll replace c this is what we're doing here is what we've done from this step to this step is instead of x I have substituted x minus t in place of x. So if I do this thing, I'll have x = minus t and then my dx will be equal to minus of dt. Right? So here I'll have minus d minus dt from where have we done this thing? From minus a to zero, right? Just give me a minute.
Yes. So if you then you'll have this thing because we've replaced x with the variable minus t. So this is what's going to change and because your dx is equals to minus dt. So you're going to have a negative sign here.
Right?
We have replaced minus t x with minus t.
So dx will be minus dt. And this limit is also going to change then when you do these things.
So if your x is I'm explaining why this this is just a direct formula if you replace this is a direct thing that you should know but I'm just explaining how it's how do you get it if you have fx from minus a to zero you can simply write f of minus x from 0 to a this is an identity but if if you don't want to use this identity directly and you want to know how we get to this identity then I'm explaining that part here which x is minus t you will have dx= to minus dt and then you'll have to change the limits as well right so for x = minus a when x is minus a because you've replaced x with minus t that means your minus t is minus a and your t is just a right so you'll have t is equals to a and when your x is equals to zero your t will be zero right so this limit will be from 0 to 8. That's how things change here.
So, and then you can just instead of now we know that this function is an odd function. So we can replace this thing with a minus sign here. So you have wait one extra negative here minus a to zero.
Just one second.
Using the substitution method here, right?
So this will be instead of x we have substituted minus t.
So we'll have f of minus t here. Then instead of dx we'll have minus of dt. That will give me minus here and a dt here.
And from here you'll have okay yeah you have the limits as when you have x = to minus a here you'll have t = to a. So this is a and when you have x= to0 here you have t= to0 here.
So this will be it. And now if you change the things here this is an identity now right that if you have a to0 fx dx and if you change the limits here from 0 to a fx dx then a negative sign gets introduced here right this is an identity so we'll make use of this identity here which gives plus instead of now if I interchange these two if I do zero here a here then a negative sign gets introduced that means I'll have one more negative here this negative negative is going to become positive and here you will have this That means you'll have min - x from 0 to a and we know that we can take this one out, right? This is also a this is also a. So we can take this negative sign out because it's an odd function. So you'll have 0 to a f of x with a negative sign here plus 0 to a f of x.
So this will just be zero.
So we've done every uh reason every uh yeah every reason why what we're doing why we are doing and how do we get these identities or if you want to skip this substitution part what you can do is we as we did previously you can just replace this is also one of the identities if you have f of minus x from let's say zero or from anything to anything let's say from a to b and this can simply be written as f of x from b to a that's fine you can do this thing instead of doing all the substitution substituting x is equals to minus d and all of that you can just simply do this thing use this identity And the alternate way is obviously the usual way we do integration and all. So if you're not comfortable using this method, you can just simply integrate this function this function which isn't very difficult either. But there's no point, right? If you integrate, do you want me to do it the other way as well?
The usual way, this one?
>> No, ma'am.
Okay, that's a simple integration integration of sin pix and integration of x. This will be x² by 2. Then this will be cos pix with a negative sign and then a pi here.
That's it. And then you have to apply the limits from minus p<unk> to pi.
That's what you have to do if you're doing it the useful way. Ma'am the previous thing that you said the last thing that you said of integration 0 to a and how we can change the limits by applying minus sign yeah that's is that only applicable when we have zero and a constant or it's applicable for any limits >> this is applicable this one >> yes that one >> you're talking about yeah you'll have to have zero right because what's what's happening here is let's say you have a limit you have limits from 1 to two and if you have fx Then how do you introduce the negative negative numbers here? The idea is that if you have zero here then some part of it is here on this side on positive side and some part of it is on the negative side so they get cancelled.
That's the idea. But if you don't have the negative side at all if you have everything on the positive side from one to two or if you have everything on the negative side from minus2 to let's say minus3 then they'll have the same sign right?
>> The sign doesn't change. So nothing gets cancelled then you'll have to have zero in middle and in fact this is only applicable. So your identity in short becomes a short identity will be if you have - a to a f of x dx then this becomes if if your function this becomes zero.
If f is odd that means your f of minus x is the same as f of Okay.
>> Minus f_sub_x. And this becomes 2 * integration of f_sub_x from 0 to a. If f of min - x is the same as fx those are even even functions like cos x like x² right? So if you have a function like that then this is what your integration becomes. integrate it from 0 to a and then uh multiply it with two. So you'll get the answer. This is the identity in short.
>> Okay.
>> Okay.
Let's do this question.
The question is visible, right?
Give this one a try.
ma'am. Uh it should be 5x2 minus e to the power e to the power minus1 and uh we can take the absolute value of this.
>> Let's see. Let's see what's the answer.
So you have been given two functions.
One is one is f(x) e to the power minus x and g(x) as 1 by 1x + 2. Now our problem is let's say you have a curve.
This is your curve and this is your curve. Let's say and you have to find the area between these two curves. Let's say this is this is just let's say this is the curve ax and this is the curve bx. We have to find the area enclosed between these two curves from let's say a to b from here to here. That means from here to here that means you have to find this area right. So how are we going to do this? What we do here is we know that if I do this thing integration of ax from a to b this is going to give me this area this quantity is going to give me this area this is ax so it's going to give me this entire area right and then if I have this thing integration of dx curves from A to B. Let's call this the green one. This is going to give me this area.
The area under B curves, right? So, it's going to give me this area. And if I subtract this, so if I'll subtract this green area from the blue area, I'm going to get the required area, which is this one. Right? The area between these two curves is the red one. And to get the red one, I'll have to subtract the blue area. From the blue area, I'll have to subtract the green area. That means from this one, I'll have to subtract this one. But what's crucial here is you should know which curve is above and which curve is below. Right? So if you have yeah you can take the mod that that also works.
So to avoid trying to find out one way is to actually figure out which curve is uh above and which curve is below.
That's one way. So if I already know that ax between a and b between a and b ax is above and bx is below. But after B if you after this point if you see right the interval also that also matters. After the in this interval your AX is above bx right sorry your bx is above this is bx curve this is above ax. So interval also matters.
So one way is to do ax if you already know that in this given interval where you have to find the area between these two curves. If you have to find the area between these two curves in the interval a to b and you already know that ax is greater than bx in this interval from a to b. Ax is greater than bx. That means ax is lying above bx then you can simply do ax minus bx and you don't have to worry about the signs. Right? But if instead I'll do bx minus ax in this particular interval then I'll get the negative of what's required.
So a negative sign will bother me for to avoid that negative sign. Let's say you do not know which curve lies above and which curve lies below. There will be cases when you wouldn't be able to figure out the which curves lying above and which curves lying below. So in that case you can simply take ax minus dx take the integral and then just take the mod right. So if ax were actually lying above dx then this entire quantity will be positive. mod of this quantity will again be positive. But if that's not true, if ax is below bx, then this area will be negative and the mod will again give you something positive which is required, right?
If you have to find the area between two things, area is always positive, right?
So you want the quantity to be positive.
So to make sure your quantity is positive, you can simply put a mod sign.
And you don't need the mod sign by the way if you already know which curve lies up. which curve lies below.
So for your simplicity because we do not actually need to figure out which curve lies above. If you want to we can tell that to actually we do that too. But let's just do it the simple way first right what's simple for you. So you have a curve fx you have a curve gx and what you can simply do is just do fx minus gx or gx minus fx whichever you like. Just do this thing and integrate it from 0 to 1. That's where you have to find the area, right? So from 0 to 1. Do this thing and then put a mod here. That's it.
So let's first find out the integral where f(x) is e to the power minus x.
g(x) is 1x + 2.
So take this integral from 0 to 1.
So this will be this integral will be e ^ min - x and a negative sign here. And then this thing will be minus of natural log of x + 2. Right? This will be it. And the limits are from 0 to 1.
So this is going to give you if I'll put one here I'll have e to the power minus one >> + 2 s t then we get dx = dt and we can do that uh dx by t then we get direct ln and uh we can convert them.
>> Are you talking about this one? Yeah, you can do it using substitution. But this one a little easy to use substitution, right? You you don't have to use that. If you if you just have to find x + 2 integral, then it's just instead of 1 by x, it's just x + 2, a constant added that changes nothing. So it's simply just natural log of x + 2.
But >> hello hello.
>> This as t then then you will take Can you hear me?
>> Yes. Yes.
>> Am I audible?
>> Okay. Then you have dx is equals to dt.
So you replace dx with dt and eventually you'll get the same thing right your t is x + 2. dx is dt. So you'll have 1x t dt which will be the same as natural log of t and this is the same as natural log of x + 2.
So going to give you the same >> also the limit will become 2 to 3.
>> Okay. If you will change let's say you have you have 0 to what do we have here?
You have 0 to one here then you'll change the limits here accordingly. You change the limits here and then you'll have something in then you'll have this here 0 to 1 and you're changing this entire thing that that's up to you. If you want to change the limits here, change the limits here and end the question here. If you don't want to change the limits, you can first integrate it with respect to t and then finally you can have your answer in terms of x and you can use the same limits here from 0 to 1. Right?
Is that okay?
So we have done this one.
We're skipping this entire t part because it's I mean using substitution in such small problems is not very advice but not something I'd advise. You don't need substitution here. Substitution is for like bigger problems where there's no alternate where you don't know things very clearly.
So this will be so if I substitute one here I'll have minus e ^ minus1 let's take minus format this will be e ^ minus 1 and then minus of e ^0 so this will be 1 and then here you have let's take the negative common from this entire thing because both of these terms have negative then this will be natural log of 1. So natural log of three minus natural log of 2.
So this will become - 1 by e + 1.
You can have a negative here. natural log of 3x 2 or you can take the negative here inside and then you'll have natural log of 2x3.
So let's see what our options is. Do we have options here? No.
Okay.
And you don't even need options here. So this Yeah. So this is simp this is your answer and you can use your calculator to find out what this value is. If it's a essay type question then you'll have to write the numerical value of your answer. So you can find the value of this right on your calculator or if it's an MSQ or MCQ then you will see option there. Your option could be 1 - 1 by e minus natural log of 3x2 or it could also be 1 - 1 by e plus natural log of 2x 3. So you'll have to simplify things according to that. That's it for now. This answer works fine.
>> Ma'am, can you uh scroll up a little bit uh to that uh diagram that graph >> and just one second, just one second. So you'll have and uh we talked about the mod sign here, right? So you can use the mod here if this quantity is already positive. So for that let's say you have been given options and it happens a lot of times this is a difficult quantity to actually know if it's positive or negative right you can't just look at this quantity and tell if it's positive and negative what we plan to do was if our answer was positive we leave it there if it was let's say if our answer was two then we'll leave it there if it was minus2 then we'll make it to two and that that will be the correct answer right because we're trying to find the area and area is never negative. But now we we don't know if this quantity is positive or negative. So what we do is we have if you have been given things in options.
Let's say you've been given things in options and this is one of the options and the negative of this is also one of the options. Let's say the other option is -1 + 1 by e plus natural log of 3x2 is exactly the negative of this. Right?
If these are two options then you'll have to pick one of these. One way is to find out the answer in your calculator.
Which one is positive? And whichever is positive will be the correct answer. The other way would be you have f(x) here.
So and you have to find the area from 0 to 1. So this is zero. This is one. Your f0 is what's f0. If I do zero here, I'll have one. Right? So f0 is one and your g 0 is half. That means at this point at zero point f lies above g right. So if your that means f lies here and g lies somewhere here. You don't even need to know how ex exactly how does it look like. You just need to know which graph is above at the point zero and which graph is below. Right?
So at zero your uh f lies above and g lies below at this point at x =0 and at one f of one is if I'll have one here I'll have e ^ minus 1 which is 1 by e and if I'll have one here g of 1 g of 1 is 1 by 3 which one do you think is better your E is 2.7 your three and you have three here. So 1x 2.7 basically and 1x3.
So 3 is greater than 2.7 and so that means this is greater than this. That means f1.
So what do we have from here? F0 is greater than g 0 and f_sub_1 is also greater than g1.
Now that means that f remains above g throughout this thing.
That's not the exact graph of f and g.
This is just for you people to understand. And that means you can simply assume that f of x minus g of x and then integral from 0 to 1 is going to give you the right answer.
And if you actually want to see how the graph looks like because these are pretty simple graphs, you should know it. So your e to the power minus x, the graph of e to the power minus x looks like this.
It looks like this.
If someone has a doubt in how does the graph of e to the power if they know how the graph of e to the power x looks like then you should know how e to the power minus x looks like graph before if you don't know we can explain that too if someone has a doubt in that we can explain that and 1x we know one the graph of 1x looks like this right so your 1x looks like this and we've already done this thing. This is just like shifting origins. If you have f(x) and your f(x) looks like this and let's say this. If your f(x) looks like this, then f of x + 2. So what has happened is x got shifted two units. Or if let's say you have x of if you have xus 2 that means x got shifted 2 units to the right side that means now you'll have originally this was at 0 0 now you have the same thing at y =0 and x = to 2 this will be this you'll have the same thing at the point here you had this at 0 0 now you'll have the same thing at 2 0 and your graph will Exactly.
That means this entire graph gets shifted to this point here like this.
Similarly, if you have we've done we've discussed this shifting of origin things a lot of times before, right? Does anyone have a doubt in how to shift the origins? So, if you have 1 x + 2 that means x - of -2 that means your graph should look like. So 1x -0 looks like this.
This so 1x - of 2 should look like this.
This is x = -2. And your graph is going to look like this. And this because we're only dealing we're doing the integration from 0 to 1. So we don't need this part. You can forget this one.
So this is your graph for 1x + 2. And the graph for e to the power minus x we already discussed it looks like e to the power x looks like this.
And e ^ minus x looks like this.
So this is going to look like this.
You just need to know which one lies above and which one lies below.
And which we have figured out using this thing using where we done that that thing this way. F at 0, G at 0 and F at 1 and G at 1. We have seen that f of 0 and f of 1 both are greater than g of 0 and g of 1 respectively. That means your f lies above g and your f was e to the power minus x right. So e to the power min - x lies above 1x + 2 between 0 and 1. Is this fine to all?
If anyone has a doubt in this graphing thing or anywhere in this question who can ask the final answer will come as 0.45. four five >> we don't have the final answer I have the answer as the solved you can you guys do have calculator in exams right you can use those calculators there that's not an issue >> and can you go to the graph part >> also if I if I may ask like >> if we have ln3 minus ln2 so we can also to compute ln3 separately and ln2 separately and then we can subtract that to find the value.
>> You can do that but why do you want to do that? Then you can simply do this thing. Why do you want to make it complicated and calculate this thing?
It's just going to take no time. That's it.
>> Sometimes they give the net type question.
Sorry, what >> that NAT type question? Yeah, for that that only I said if you have an an NAT type question where you have to write the exact answer in uh decimals and all then you can just simply find natural log of 3x2 instead of finding natural log of 3 minus natural log of 2 on the calculator right you can do whatever you can use the calculator whatever way you want whatever suits you that's fine Does anyone have a doubt in this question? Any other doubt in this one?
>> Ma'am, uh uh can you just uh go to that graph part? Uh not this one. Just a little left.
>> Not not here, ma'am. Just below the question initially you draw the graph, right?
>> This one.
>> Yes, ma'am. This one. Yeah. So uh like uh sometimes uh both of the function may lie uh below the x-axis I mean it may lie in the negative y-axis right in that case we will get negative area so if you take the absolute value of that >> no you won't get negative area is actually never negative if you've been asked to find the area these are two different things fx minus integral is a different thing area is different Right?
Integers can be negative. Your area is never negative. So if you'll have something, let's say you have this thing and you have to find this area, let's say, then what you do is you take this curves.
Okay? If you'll have this curve, if you'll find the area of if you'll take the let's say this is f and this is if you'll have the integral of f, you will have something negative. That that means you had you have this area but in negatives, right?
>> Yes, ma'am.
>> And the same happens with the g curves.
So how do you fix this thing? We know that we've gotten this area as negative and this area is negative as well. So one way to do it is just simply take G minus F. So what is it going to give you? It's going to give you this exact area that you require but in negative, right?
>> Yes ma'am. So just take and then you have to do the same thing because if you don't if this turn if this is a number that you can find out unlike this one here we had some complicated stuff which we couldn't calculate if it's a and you still cani find this out using your calculator. If this you don't have to go through this entire positive negative nonsense. You can just simply find out the value of this using your calculator.
If this is positive you're fine. If this is negative just change the sign there.
That's it. So if you have this as positive, you're good to go. That's your answer. If this is negative, then you and in this case, in this particular case that you're talking about, this is going to be negative. We all know, right?
>> Mhm. Yes, ma'am.
>> So you'll have to change the sign there.
That's it.
>> Okay. Okay. So maybe uh in uh in the concept of area under the curve uh there we can get some negative area, right? Let's say we are considering the area between minus1 to 0 of the graph x cq. In that case we'll be getting negative area >> xq looks like that you're talking about 0 to minus one right that's what I said when you take the integral of functions right >> let's say I have fx and I integrate this >> this integration can be negative now what does that mean that but your area cannot be negative right >> if you look at area is never never negative so this integral is if you get something negative. That means yeah like in x cube case you're going to get the area from here to here negative because it's lying on the negative side on the negative yaxis. So you get you'll get something negative you'll have to change the sign. If you if you been asked the area let's say this entire area is minus2. Then if you if you're asked the area you have to write two. If you've been asked the integral then it's minus2.
>> Okay. Okay. Okay. Okay. Uh just before uh this question we had a question like that right in that odd function. So >> this one this was not about area >> uh it was about integral only.
>> Yeah. This was simply about finding the integration.
>> Okay. Okay. Okay.
>> Okay.
>> If it were really about then you can't actually do we need to discuss this thing. If you have to find the area of x, let's say x is also an odd function, it looks looks like this, right? So if if you've been asked to find the area from here to here, the integral from here to here, if it's one and minus one, the integral gets cancelled because this is positive, this is negative. But if you've been find the if you've been asked to find the area, just find the area of this.
And because we know that both of these, yeah, just multiply with two.
>> The same that we do with functions, do the same here.
>> Okay. Then moving to the next. Does anyone have any further doubts in this question?
Okay.
And this is the next question from graphs here. You have to tell which of these graphs are trees.
Give it some time. And >> option D is a tree.
Other options are also trees here.
>> Check all of them.
>> Okay, let's do them one by one here.
>> A tree.
>> You have this thing. It might look like they're crossing each other, but if you will have this as this, you can have this at this, right? You can have this point here.
You can draw this one as simply this. So it's not it looks like it's crossing.
They're crossing each other and they're intersecting somewhere. But it's it's simply this graph and this graph is a tree, right? Tree is simply if you have forgotten the definition of tree, it's simply minimally connected graphs. So every vertex should be connected to other vertices. That means vertices should be connected with each other and it should be minimally connected. Now this is not a minimally connected graph.
If I'll join these two minimally connected means if I remove one more edge from here the graph should not be connected. Like in this case if I remove this edge now it's not connected. That's your minimally connected graph.
So this is minimally connected. So this is a tree. Then coming to the second option.
>> This is also a tree.
>> Let's see this is let's have this point there.
You're having let's mark these ones. A B C D E F.
So you'll have A F here.
then D here.
Then you will have B here, E here and C here. Right? So this is a connected graph. This graph is simply this.
And it is minimally connected. So it's a tree.
We can't remove any uh any edge further.
That would result in something in a graph that's not a tree.
So, >> show what? Show this thing. We have redrawn this one. That's it.
>> Okay.
>> So, this is a tree as well. Then coming to this next one, let's call this again as A, B, C, and D. It's not a tree because it's not connected.
>> Okay, let's Yeah, if you will draw this, you'll have see C is like this. If you have A, you have A connected to E. Then E connected to C.
So it's simply this A E C and then these ones A E C are in a line and D B F are in a line D B and F. So this graph is simply this and this is not connected.
So not a tree.
This option is incorrect. Then coming to the D1. You don't have to redraw this one. This is pretty clear. We don't need to draw we draw this one because we can see that every all all of the vertices they're connected and then uh you can't remove any edge. Any edge if you remove this will result in a graph that's not connected. So this has to be a tree.
Then coming to this E1 we need to remember this one. A B C D E S draw it here.
>> Ma'am B D C is a cycle. So from there we can say that it's not a tree.
>> Okay. Yeah, we can do that too.
Let me just draw this graph clearly here. So a is yeah if you already see a cycle then you don't need to draw this one. We have a cycle here. This I'm marking the cycle in green. So this is the cycle A B then B to C then C to E and then E to D.
So this is a cycle.
That's why this isn't a tree.
For tree what you need is it should be connected and it should be minimally connected. So whenever you see a tree what sorry whenever you see a cycle let's say you have this thing.
Whenever you see a cycle somewhere that means it cannot if you have a cycle in your graph that graph cannot be a tree right. trees uh when you yeah trees never have cycles and we've discussed this thing already that trees we we never see cycles in a tree to see cycles in a graph that means that's not a like this one so because this has a cycle here it cannot be a tree because tree means minimally connected graph this is obviously connected the problem is it's not minimally connected every graph with a cycle is never minimally connected if you remove this edge.
Let's say you have these three edges. If I'll remove this edge, it's still connected.
That that means it's not minimally connected. Or in simple words, if you look here, you don't even have to get into the cycles thing. If I'll remove this edge, if I'll remove this particular edge, it's still connected, right? This entire graph is still connected. That mean this entire thing is not minimally connected.
That's the problem.
That's why this is not not a coming to this one.
We can draw this as let's draw F here.
Let's call this A B C D E. So this will be a connected to that and they're connected in that order right? So this is A B C D E and then D is connected to B is connected to E and C.
It's connected to E. It's connected to C.
Uh one more vertex you have not named.
>> Yeah.
>> Two vertices you have not named. And the upper one >> A B C D E are in a line in a row. So we have them here. And then B is connected to G is one and A is connected to S.
and D is connected to some G.
So this looks like a minimally connected graph to me unless we miss something from here. This is the exact same thing as this, right? They're same.
So that means this is firstly this is connected. That's the first thing you have to check. And second thing you have to check whether removing one of these edges will result in a connected graph or not. If it does not if you remove any of the edge this one this one this one or this one anyone and it's not a connected graph anymore then it's a tree otherwise it's not a tree right it should be minimally connected so if I remove any of the edges from here it won't be connected anymore so that means this is a tree that mean this is also correct so these four of them are threes If two of them are not. Does anyone have a doubt in this one? Can you move to the next one? This is clear.
>> Yes, ma'am.
>> Okay.
Give this question a try.
Then the third option m - n + 1.
>> Okay, let's see.
>> And it should be given that uh like m should be greater than n minus one, right?
Let's see what should be given. We will come to that. Let's just give this question a read. It says how many edges must be removed from a connected graph.
So you have been given a graph with number of vertices is equals to n and number of edges equals to m. You have n number of edges n number of vertices.
And you've been asked to produce a spanning tree. So for you to have a tree uh and you've been asked how many let's say you have to remove t we've been asked how many edges should be removed right so let's say t needs to be removed t edges or t number of edges we're removing >> can we say that m should be equal to n minus one >> we'll see that just give me one cuz there would be n minus one edges.
>> Just give me a second and I'll be back.
Just one minute.
We're discussing this thing. We let's say we have the number of uh the number of edges is n sorry the number of vertices is n number of edges is n and then we have to find the number of edges to be removed and why why are we removing the the number of edges we want a spanning tree right so from a connected graph so if you have if you have a spanning tree we know let's say you have n vertices Let's say you have three vertices and if you want a or let's say four and if you want a spanning tree then the number of edges there would be n minus one right.
So if n vertices are there then your number of number of edges for minimum number of edges or actually number of edges in your tree or a spanning tree.
Spanning tree means a tree that covers.
Now this is also a tree, right? This is also a tree but it's not a spanning tree because it's leaving this vertex. So for that for a spanning tree you will need n minus one vert n minus one edges. So if you have n number of vertices like we have four vertices here the edges in your spanning tree will be n minus one and we have exactly three here. This is the spanning tree and it has the number of vertices is four. number of edges you can do it with five vertices to you have five vertices then you can also see this thing so there are five vertices now and the number of edges would be just this so this will be 1 2 3 4 no matter how you make the spanning three or if I'll remove this one then I'll have to draw this edge right then also you have 1 2 3 four four edges so with five vertices you'll have four edges with 10 vertices you'll have nine edges for your spanning tree.
So if there are n number of vertices in your graph then in the spanning tree for that graph you will have n minus one number of edges. Right? So your number of edges that you require are n minus one. And how many edges do I actually have? I have m number of edges but I only want n minus one edges. Right?
And that's what you've been asked. How many edges should I subtract? So that I have exactly n minus one number of edges. Right? So I'll have to subtract let's say I have to subtract t from here.
Then m minus t should be equal to n minus one. Now you can say because t is a variable that we have chosen. So there are no conditions on t.
Do we have conditions on m and n? So let's let's say you have m from here you get m if we first we have to find t here but if we first find m you will have n minus or n + t minus one. So obviously you' want that this quantity should be positive. So you'd want n plus t should be greater than one at least greater than or equals to yeah greater than one.
So okay let's we'll come to the constraints later. Let's first see what value of t are we going to get from here. So t you should get as m - n + 1. So these are the required number of edges that you need to remove.
Now let's come to the doubts that some people had.
Ma'am actually uh like initially uh I thought that m should be greater than n minus one uh but here in the question it is given that it is a connected graph.
So uh if it is connected then m should be like greater than or equal to n minus one otherwise it won't be connected.
>> Yeah. If you have if you have n number of vertices and you have to reach to n min sorry n number of edges and you have to reach to n minus one edges then obviously by reducing number of edges then n has to be greater than equals to n minus one right it's like that that's obvious.
>> Yes.
>> Although it should have been mentioned there that your n should be greater than equals to n minus one.
But that is then it makes the question pretty obvious the options it makes very simple.
So it gives you sort of a hint if this is given in the question.
>> Yes.
>> That this should be the answer.
It's like simply saying your this this should be greater than zero.
So maybe that's why it's not given in the question.
Yes, ma'am.
>> Okay, let's do this one. Give this one a try.
ma'am option four uh option D let's first draw the the suggestion here would be first try to draw the BFS tree for this thing because you're performing BFS here. So you should draw the tree first, right? So let's start with and you're starting your search from A. That means A is the first vertex. Then directly connect what do we do in BFS? We see the ones that are that directly have an edge with the starting vertex. So A has a direct edge with B and P.
>> Yes, ma'am. A is correct like this.
Okay, let's see which one of these is correct. A once your tree once you're done with the BS tree, all of the options will be clear. So A then you have B and E here on level on the next level. This is let's say first level then this will be the second one.
A D E and no other vertices. Then D is connected to C and E does not E needs not to be counted. We don't have to count E again. So C and then it's connected to F. That's it. Right? So you'll have C and F here and E is connected to then you have to check E first. You have to get done with every vertex in BFS. First you explore this. And when you're done exploring this, then you move to this first vertex. Explore this. Then move to this next vortex. Then explore this. Then come to this other level. Right? So E is directly connected to F is already done. C is already done. So you just have J here. So with E you just have J.
Then with C you have F is done. It's done, right? Yeah. All of these are done. So you're only left with D. You just have D here. And with F you don't have anything further to add because D is already mentioned in our tree and F is not connected to any other vertex which has not been mentioned so far. So this one ends here. Let's come to this cycle. Then J is >> here we can uh stop here right uh like we can see the options some of the options will disqualify till this step >> I don't think so >> I don't think some of them will get disqual let's see >> like option B and C will disqualify because >> okay that depends on the options you might have some options which might not get disqualified from maybe you'll have all the options which will not so it's better to just get done with the tree first and then come to the options.
That's a better way to do things. If something is getting disqualified from here, you obviously can can uh rule out those options. But let's let's first get done with the tree. That's an easier approach, right? With J >> J directly connected to E. E is already mentioned in the tree. Then you have H I G directly connected to J and K and P as well. So there are a lot lot of it's connected to four right >> five.
>> So it's okay. G H I P and K.
We have one more here. K. They're all on the same level. D is also on the same level as these ones. This is one level.
Then this is another level. Then this is another level. Then this is the next level.
Then starting with G. G has nothing. H has nothing. I has nothing. So these three just end here.
Then P has a lot to explore from here and K has a lot to so we have mentioned T first. So P then you have directly connected Q, R and T. So with P you have Q, R and T.
And with K you have O, L, N, and M and S is still left, right? So S is under all of these. You can write it under I'm writing it under this.
And let's do one more thing. Although we have to just make the tree. So we cannot have sites here. But because uh that you we have already discussed this thing.
BFS trees are not unique, right? So you can have more than one BFS tree. So let's just try to see all the possible.
Okay, some of the options might not even get ruled out from this thing because We have done it in a very particular way. Q is al S is also under R. It's also under T.
Then there are other vertices too that are all that are under a lot of other options. D is also under F.
F was also under E.
I'm drawing these ones for you to know that this is also if you will remove this one from here then F can come under E as well. If you remove this one then B can come under F as well and S can come under any of these instead of Q. So for other possibilities of BFS. Now let's check the options. The first option is A then E then B A E B then we have F F C D F C and because we have to get done with the level first and then we can move to the next level. So this level A then B E have to be next then C F and J have to be next in some order in this order or FJ C or F CJ in any order but you need to have them before moving to next vertices right so if you have here F C and then D before J and that's not right because before D you need to write A so this option is incorrect because of this.
There could be other mistakes as well but we have figured out the mistake here. We don't have to check after this point.
Then let let's come to B option. B option says A first then B E on the next level. Then C FJ on the next level then D G H D G H I T K. We want them on the same level. So D G H I K.
We have D, G, H, I, K, and we have L before P, which should not happen. We should have P first here, right? They're all on the same level. So P should come before O. You first get done with this level, which has G, H, I, T, K. Then you can move to the vertices on the next level. And they're not doing that. They first mention O, which is a mistake. You should have P here. In fact, D G H I P, right? So only P is missing here. So your fault is here. D G H I K. This is the mistake.
You should have P before O.
So this is incorrect as well.
Then let's move to the next option. It's a B.
Your next option is A then B E are fine.
Then C F J that's also fine. Then D G H I K P D G H I K P this D G H I K N P.
So this is also fine. If you see D H I K GP that's also fine. But you need to have all the vertices on the level covered first before moving to the next level. That's the idea.
So this is also fine. KP and then we have O L M N O L M N and QRT. We need to have O L M N QR T before S because S is on a different level than these seven. So these seven are here first and then S is at the end. That means this option is fine. C is fine.
Then let's come to the last option.
We have A. Then we have EB. I already mentioned that the order does not matter. Either you write A or you write E B E does not matter.
So this will this is A E B. Then you have J F C J F C that's also fine. Then next you have K P J KPG H I K P G H I K K P G H I and D.
So after these three C, F, J, we want these six, right? So we want D, G, H, I, P, P, K in some order. So we have we have them here.
D. We have D here. Then G, H, I, P, K.
That means they're all in this.
The ones on the same level are written together. That's the idea, right? Then the next level is this one. So we want QR T O L M L.
So from here you have L M N O and QR T.
They're written together, right? So it is A on the first level, then EB on the next one, then G F C on the next level, then KP GH on the next level. Then L M N O T R Q on the next level and then S on the last level because the this pattern is following here that means this option is also correct. D is also correct.
So we have these things here. Is this one clear to all? Can we move to the next question?
>> Yes ma'am.
Okay, the next one is this. Give this one a try.
Seven.
I don't think seven is possible here.
Let's let's see.
So we have we have to find the vertex cover. So for vertex cover let's take because these ones are connected to both the the outer ones they're also connected to three.
Okay. So let's start from the alternating ones here. This is one then because we don't need this one.
This is already for this uh this edge. We already have this thing. So let's take this one. Then we don't need to take this one. And then we take this one.
So these these three are covering these ones.
This edge is covered or this edge is covered. This edge is covered. This is also covered. This is covered. This is covered. This is covered.
This is covered. This is covered. And this is covered. So far all of these are covered. Then the left ones are these.
So we want uh this vertex to be included in the vertex cover as well. Then we okay let's not take this one for this one. No we will come to this edge later. Then let's take this one because there are no three edges here connected to this one and none of them has been covered so far. to this one.
Then the same goes to this one. So now we have 1 2 3 4 5 six. Six are already six vertices are already there in your vertex cover. And this covers these edges. This one, this one. Then this one.
This covers this edge.
This edge. And this edge.
And we're still left with some edges, right?
Which are the edges left? This one is left. This one is left.
And this one is also left.
This one's also left.
Then uh let's have this one too. This is going to cover this.
Oh, wait.
You can't have if you will. It's better to have this one. If instead of if instead of this if I have this one, it's going to cover two. This is covering.
Okay. This this was also covering two.
>> Yes ma'am. So, >> uh that's the same thing. Then let's take this one. This is covering two.
This one and this one. And okay, we forgot if if you're taking this one then this is also covered right?
>> Yes sir. Yes ma'am.
>> This is also covered.
These are the edges covered so far.
Right. And what are left? This one is left. This one is also left. Only two edges are left.
And no vertex is covering both of them.
Right?
It will take this one. This edge will be left. If we'll take this one, this edge will be left. Sorry, this one. This edge will be left. And if you'll take this one, this one will be left. So let's take we'll have to take two now. Let's take this one and this one. So you'll have this.
Sorry.
You have this covered and this covered too.
So, how many are these? This is 1 2 3 4 5 6 7 8.
>> Are we left with any more edges?
>> Um, nine. Uh, uh, it's not >> nine, I guess.
>> 4 5 6 1 2 3 4 5 6 7 8 9 Yeah, these are nine in number. 1 2 3 4 5 6 7 8 9 right.
>> But ma'am like uh how do you make sure that uh the answer the minimum is nine here?
>> How do we make sure you can you can't do it some other way right? If I'll have I don't want to erase everything which I've done. Let's do this thing here.
If you so first you what you when you're trying to figure out vertex cover your first aim should be trying to try to cover the vertices that have minimum edges from there right so if this has so any vertex here does not have more than three three edges that's what I can see this also has three edges some of them maybe only have two no they all have three right >> so yeah all of them have three that's fine so you you start with let's say you start with this one instance then you're only covering these three. You get to know only by trying to see which ones are getting covered. There's no hard and fast rule for it.
So what I'm trying to say is we don't have a formula for it or or a hard or fast rule that this is if you do this thing then you can make sure that this is the minimum number. Right? We don't have that rule. The one trick one thing that you should have in mind is that start with the vertex that is if you have something like this and it is connected to a lot of it has a lot of edges going out from there then you should choose this vertex for sure right because it's covering a lot of edges. So try to try to target the vertices that cover most edges like this all of them here are covering only three edges. So in this particular example that point is of no use but in most cases it is of use.
So you let's say you start with this one. Initially we started with these ones right the inner let's start with this one. Then there's no or let's say you start with this. You have these three covered.
You have these covered.
Then if I start with this one let's say if I start with this next then you will have this Then let's say I'm taking this one next.
Or if I right because all of these three are also not covered yet. So if I take this one, I'll have these vertices, these edges covered.
Now you have to be careful. Why? So far we will have to be careful because all of these when I started with this one I had three edges to move. Then I started with this one I had three edges to with this one I had three to cover. Now from this right that is what I was trying to say. The point was when you see now some of them have been covered but from the rest from the remaining ones from the ones that have not been covered so far the vertices that you choose the next one to be in your vertx cover that vertex should be the one that's connected to most edges. So most connected to most edges right now after this thing is this one. This vertex is connected to most. This is al this is only connected to this is also connected to most three and this is also connected to most. These four are the options you have, right? This one, this one, this one, and this one. All the others are only covering two edges. So there's no point choosing them now, right?
>> That won't be an optimal solution.
That's why it's not ideal.
So next up, you choose you take up this one because it's now you have the maximum options from this vertex. Three options. So this covers these edges.
Then next up you can choose out of now there's no point choosing this one because again you only have two choices from here two edges it's covering and this one whereas this one and this one is covering three edges. So you should take up this one next or you can take this one also.
But once you've chosen this one now all of the ones that are left look at the remaining ones the remaining vertices that you've not chosen yet for your vertex cover all of these are only connected to two. This is connected to two. By two I mean the ones the edges that are not covered yet out of those edges it's only connected to two. only connected to this is only connected to one. No, this is also connected to two.
This is only connected to one. This is also only connected to one.
So if I'll write the number here, this is this is connected to just one.
This is connected to just one. This is also left. This is also connected to just one. This is connected to two. This is also connected to just one. These have been covered.
This is also connected to just one.
This is connected to two. This is also connected to two. So out of these ones now, what are the ones that you should be choosing next? It should be this one.
>> Sorry to interrupt. How it is connected to two? The the last two.
>> Which one? Sorry.
How we are considering that this is connected with two is because it looks similar all three all three okay which are you talking about okay what we're doing here is these edges are already covered right so forget about these edges for now because I covered so why would you choose a vertex which is connected to this one let's start with this vertex out of the remaining edges what What you're trying to collect here is you're trying to make a set of vertices and you're trying to keep the vertices here that are connected to maximum number of edges. That's our aim, right?
Because you want to cover every edge. So idea is put the vertex in the set which is connected to maximum edges.
That's the idea. So if you already have this vertex, these vertices, God, these are not even numbered, right? So I can't put them in set. So these ones, the marked ones, this one, this one, this one, this one, this one are already in your vertex cover. The red marked ones are in your vertex cover, right? They're already in the vertx cover. But we need more vertices in the vertex cover. These are not enough. 1 2 3 4 five are not enough. We need more because this edge is left. This edge is also left. This edge is also left. So how should I choose those vertices? I should choose a vertex now which is connected to most edges that are not covered yet. Right?
So this one is only connected to one.
This is the only edge that it's covering. If I'll put a let's say if I put a CCTV here, it will only cover this edge. Right? Because this edge and this edge is also already covered. I don't need these two to be covered because they're already covered by these two cameas here. Right? And this camera, if I install a camera here, it will only cover this edge.
>> So this is going to cover one edge. Is it >> color? Color we do color poding kind of.
We can do like that >> color. What color?
>> Uh we do like when you see the camera we do the color u code. We do apply one and then positive and then negative two different color and then again uh apply another color then uh two vertex not be similar kind of. No, no, that's that's grass coloring problem. That is a different problem.
>> Vertx cover problem.
>> Why we are not this vertex the left the between in middle we are not considering that?
>> Are you talking about these?
>> Yeah. What are you talking about?
>> Yes sir. Left to right. This line the middle one.
>> This one. There are only two types of vertices on the outer one. The outer ones and the inner ones. Which vertices are you talking about?
>> The the outer one is going one to one.
The in the Yes, correct. Yes.
>> This one out of these they've already chosen these ones. This is chosen. This is chosen. This is chosen. Now out of the remaining ones, the remaining outer ones. This is that's what I'm saying.
This this particular vertex is only covering one edge. So if I install a CCD here, it's only going to cover this edge. But if I install, which ones are left? If I install one here, this is going to cover two, right?
This a CCTV here will cover two edges. A CCTV here is only going to cover one.
Let's first put the ones here.
>> But but the question is minimum vertex cover for G.
>> That's the algorithm to find. That's the easiest way to find. If you will do it randomly, let's choose this one. Let's choose this one. Then there's no point.
No, then you wouldn't be able to find minimum. You might if you will just randomly go about vertices. You might find the answer to be 10 or maybe 12 to ensure that it's the someone asked how do we know that it's the minimum vortex cover. I'm answering that question here. How do we ensure that this is the minimum vortex cover?
Okay, >> you have to find the optimal solution, right?
Optimal here means minimum number of vertices that cover all the edges. That will be your optimal solution. If that's your aim, then you should be choosing the vertex which is connected to most number of edges. That's the idea. That's the sole idea. That's it.
So, you keep picking the vertices that are connected to let's say if you have a graph like this.
So my first instinct should be if I have to find a vertx cover for this graph my first instinct should be choose this vertex because it is connected to one or let's say >> the top right >> to to make my to make my point more clear let me just do one more thing let's take an easy graph let's say I have this Now if I have to find a vertx cover the first vertex that should come to my mind to put in let's say this is v_sub_1 this is v_sub_2 this is v_sub3 this is v_sub4 and this is v5 the first vertex that will come to anyone's mind would be choose this vertex because it's connected it is covering the most number of edges right this one this one this one this one so first instinct would be put v1 in your vertex cover first then the next one will be now this edge is covered. This is covered. This is covered. This is covered. This is covered. So there is no point. Now the remaining ones are this one. This one.
This one. Which out of these is covering the maximum number of edges. So your next option should be either V4 or V3.
Right?
Because V3 is covering two edges out of the remaining ones. These three are these four are already covered. The remaining ones are V. This is left. This is left and this is left to cover. So out of these three, V3 is covering these two. V4 is covering these two. V5 is only covering one. V_sub2 is there's no point putting V5 next. So I should put either V3 or V4 next. Now if I have V3 next, these two are covered. That means the next one I can choose from V4 to V5.
V4 or V5. Anyone you can choose V4 or you can choose V_sub1, V3 and V5. That's also fine, right?
And you don't even need the cover. You just need the number of elements in the cover. And the number of elements are going to be three in this particular example that we've discussed. So the same thing we are doing here. We're trying to cover the vertices that are connected to most number of edges first to make sure that we trying we're find we get the right vertex cover that what we are actually finding is the vertex cover.
Right? So next you should take this one.
Either this one or this one or this one.
So let's take this one.
And by the way this is just this is just one. Why have I written two here?
This is covering just one, right?
One. Yeah, only one. So you should be picking from these two. Either this one or this one. So I'm choosing this one.
Next.
If I'll choose this one.
Now these two are covered.
Now look at the minimum.
This has nothing to cover. Now this is zero. This is also zero.
Nothing to cover from here. Nothing to cover from here. Now we have this as one. This is still one. This is still one. This still covers just one one edge. This still covers two edges. This still covers just one edge. These might change by the way. These numbers that we've written can change, right? This is still covering one edge. So our next should be this one. This vertex. So let's choose this one next.
So you'll have this edge covered. This edge covered.
And now we're left with now this number changes. This vertex has nothing to cover. So this gets removed. This still has this edge to cover. This still has this edge to cover and this has this edge to cover. And how many edges?
Now let's choose this one because all of these are just one one. So you can randomly choose any of these. Let's say I'm choosing this one.
If I choose this one, now this edge is covered.
This vertex has nothing to cover. Leave this. Now you're only left with this one. So the next one you should be choosing is this one.
this one so that you can cover this edge. Now this was the only remaining edge and this also got covered. Now you just found the numbers. It's 1 2 3 4 5 6 7 8 9. So the total numbers here are for your vortex cover. Number of elements in your vortex cover would be nine. Is this fine? Yes, ma'am. It's clear.
>> Okay.
Now let's do this question. This is of the class. So let one.
Even if you have even if you've been asked to find the minimum cost of the you can follow any algorithm no matter what your question says even if it says find using crucal's algorithm you can use prince because you just have to write the answer so let's start let's question using prus because that's comparatively simpler algorithm so first one will be this. So let's start from this one. This is the minimum edge, minimum weight edge. So this one we take.
Then next up we take one. Then after one we have this one to cover this edge. Next one.
>> Then after one two we have three. Right?
So but we cannot take this one because it's forming a cycle and we want a three. So we can't take this one. Not taking this. Then after three you have four.
Take this one. Then after this you have five.
This one. Then after five you have six.
Take this one. Then you have seven. But seven is forming a cycle. So don't take this one. Move to the next number.
Eight. Choose this one. Then this is again forming a cycle. 9 one. Next is this. Next minimum one is this. But it's forming a cycle. So don't take this one.
And this is again forming a cycle which means your tree has been covered. your you have found your tree minimum cost spanning tree so this is the required tree and you can check it confirm it by checking whether all the vertices have been covered or not so this this this all have been covered that's why this is your minimum the red marked one is your minimum cost >> if I start from f then uh it will be wrong I will get the wrong answer if I start from f because I >> if you're using algorithm >> if you are using algorithm then start with the minimum one. If you're using Prim's algorithm, you can use any vertex.
In Prim's algorithm, it does not matter what you choose at the first. But in Tuskar's algorithm, it does matter >> if because here it is not mentioned that which algorithm we need to use.
>> That's why we use the simpler one.
Truskll's algorithm is comparatively simpler compared to Prim's algorithm.
You just have to arrange these edges in ascending order and then choose them in such a manner that there's no cycle. So it's just easier if you've not that's my suggestion. If you want to do it prince way, we can do that >> ma'am. But we already have a dedicated question. Yeah.
>> Yeah. Uh uh so what I'm asking is for this question the spanning tree I mean this is the only spanning tree possible right cuz we have uh like unique >> yeah they're all all different numbers yeah all different weights so this is the unique one possible 1 2 3 four is also there three is not there right 1 2 4 5 what's the total Okay, let's just count it without writing.
>> 26.
>> It's 1 3. Okay, let's say 1 7 12 20 26, right? So, it's 26.
Uh, if this I hope this one is clear.
This is the Prim's algorithm, Crystal's algorithm is probably the simplest part of graph theory.
So let's move to the next one. This in this one it's been mentioned that you have to use prim's algorithm and because you have to write the order that's why it does matter that you do this question using prim's algorithm only.
So don't do it using algorithm. You'll get a different answer and that will be incorrect because you have to find the order here.
So the only type of questions where you can use your the the algorithm that you want are the ones where only minimum cost has been asked. If you've only been asked to find the minimum cost of a spanning tree, then you can use whichever algorithm you want. It doesn't matter what's mentioned in the question.
Use whatever you want. But only when you have to find minimum cost. Don't do it in any type of question. Like in this question, you you have to use Prim's algorithm. So let's first try to make the graph of this one.
So this is v_sub_1 v_sub_2 and this is also v_sub_1 v_sub2 v3.
So we have B1, V2, V3, V4, V5, V6 and V7.
So V1, we have an edge from V1 to V2, which is 24.
Then we have one from B1 to B3 V4.
Let me just write this down a little.
B3, V4, V5, V6, V7, 8, V1, V_sub_2, V3, V4, 5, 6 and 7. So from V_sub_1 we have till V2 we have 24 then 36 and 28.
with V5 we have let's make V5 here 36 then B7 28 Then next we have from B2 to V1 it's 20.
That's all we done. Then B4 32.
V2 to V4 it's 32.
Let's make this one here.
Then that's it. And then from B3 to B6, it's four.
3 to B6, it's 4.
And B3 to B7, it's 12.
And from V4 to V2, I think that's already done. And from V4 to V5, 8.
That's it. V4 to V5, we have eight.
>> Ma'am, sum up the weights as zero here.
>> 32.
So >> with sum of dates >> like what uh what is the meaning of this zero in the matrix >> you only have when you have zero here let's say you have that means there is when you have zero here that means there's no edge right >> no edge okay so this uh I mean this prim's algorithm is valid for negative weight graphs right RI's algorithm you don't have the concept of negative and all in minimum cost span entre we don't have negative rates there and when you have this is this is just the adjacency matrix. So whenever you have a zero in adjacency matrix like we used to have 0 and one but when we had no weights we had 0 and one entries right. So zero meant no edges no edge from this vertex to this vertex and one meant there is an edge from this vertex to this vertex. Right?
So we were discuss we were on the fourth vertex. Then fifth one we have no other edges. For sixth one we have from V6 to V7 20 V6 V7 this is 20 then from V7 that's it right so this is your three sorry this is your graph I hope we have not missed any weight let's just 1 2 3 4 5 6 7 8.
Let's just check here. How many entries are non zero here? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. All right. Here we have 16 non-zero entries and because it's a undirected graph so only eight eight edges will be there. Okay. So this is correct graphically.
Now let's come to uh if you start now in prim algorithm you have a vertx to start from right I we have discussed this in summary and your vertex to start from is >> half of number right ma'am if the number is there is a repeated number right >> yeah in unirected graphs your undirected graphs are like this right if you have an entry from B1 to V2 represent the same edge. That's why here you will see 16 entries but there are only eight edges.
It's an undirected graph that's why is that what you are asking?
>> Yes ma'am. How to check that my graph is correct?
>> You will check your graph is correct.
First you count the number of edges here. Here I counted there are eight number of edges in this graph. And here you will see 16 non-zero entries. So your non-zero entries in this one are 16. And because we already know that it's an undirected graph. So undirected in an undirected graph if you see 16 non-zero entries that's what I was discussing here. Let's say you have a 3 + 3 matrix. Right? So if you see if this entry is non zero what happens in graph?
This means you have an edge from v_sub_1 to v_ub_2, right? There's an edge from v_sub1 to v_sub_2. And because it's an undirected graph, if there's an edge from v_sub1 to v v2, it's counted as an edge from v_sub_2 to v_sub1 as well. So you will see if you have three here, you'll have three here as well. That's what happens in so that means if you see one non-zero entry here, one non-zero entry, if you see two non-zero entries in your everything else is zero. If this is your graph then that means in in this non-zero entries are true two right these two are non zero this is three and this is also three but the number of edges here is just one so for nondirected graph the number of edges is equal to the number of number of non-zero entries divided by two so in your adjacency matrix if you have two number of non-zero entries divided by two this is the number edges that you have in your graph. That's how you check it. Is that okay?
Okay.
So, we've made the graph correctly. Now, let's find the order starting from B1.
So, B1 is the first one. Obviously, we start from here.
Then the unlocked ones would be these ones. This gets unlocked. This gets unlocked. This gets unlocked, right? And you choose the minimum from these. So this will be the next vertex.
This is covered. And the next vertex is this. So your next vertex is V2.
Then from V2 this gets unlocked.
That's it.
And you have to choose the minimum from 1 second.
We are 32 here, right? 32. So this gets now this gets unlocked and you have to choose the minimum from the unlocked ones. So this is one, two and three. You have to choose the minimum from these three 28, 36 and 32. So the minimum one is this.
So next is this one.
So your next one should be V7.
And so far there's only one option which matches this order which is this one.
P1, V2 and B7. So only this matches the order that we have found so far. You don't have to do the entire thing. You can just take this one.
But if you really want to find the entire order, then how do you take the next vertex you have done till V7. So this gets unlocked and this gets unlocked. Now you have to choose the minimum from these the unlogged ones. So you have to choose the minimum from this one, this one, this one and this one. So the minimum is 12. The next one that gets unlocked is V3.
So we will have B3 next.
Then from V3 this gets unlocked.
So out of the unlocked ones that have not been covered so far. So it's this one, this one and this one. You have to choose the minimum. So the minimum is this four, right?
So this goes next.
V6 goes next.
And then again these ones are the unlocked ones because from V6 nothing gets unlocked. This was already unlocked. So you have the same edges 20 36 and 32. So you have to choose the minimum from these ones. There's no point choosing this one because V7 has already been covered. So you have to choose the minimum from these two. So this is 32 and 36. So the minimum is this.
So the next one in the order should be V4 and then this gets unlocked. Now all the edges are unlocked and nothing is left by the way. Only these two are left to choose the minimum from. So the minimum is this one.
The next that gets unlocked. There's only one left, right? Only V5 is left that gets unlocked next. So this is the order V1, V2, V7, V3. this order which is the same as this one and you could find this out only by doing till here because only this option matches this order.
Is this fine? Can we move to the next question?
>> Yes ma'am.
>> Okay, this one is the next question.
You have to use matrix multiplication to find a square from a1. This is a1. This is a square. And then you have to find the value of so let's say this is a square. You have to find the value of 2 alpha beta. So to find the value of this expression you need to find the value of this entry alpha and this entry beta.
And how do you get this entry is if this matrix is if I'm calling this matrix M then this entry is M12 which means first row multiplied with second column right?
So this row multiplied with this column.
>> So you get yeah because this entire column is just zero. So you're going to get zero. That means your alpha will be zero.
And for beta for this entry you have to multiply this is third row. This is if the matrix is m then b should be equal to 3 and 1 2 3 4 5 so it's 3 5 and the 3 fifth entry that means third row fifth column so it's this one >> third row fifth column multiply this with this this with this you have to you know how to multiply right multiplying matrices so this will be 0 0 0 1 and 0. Right? So this is when you multiply you will get this thing 0 + 0 + 0 + 1 + 0. This is just going to give you 1. And this beta entry will be equal to 1.
And you have to find 2 alpha plus beta which is just one. Right? Beta is 1, alpha is zero. So this should be one. Is this okay?
>> Yes.
>> If you want to recall the mult multiplication and addition in these matrix multiplication, how do you multiply and add entries? So if you have 0, multiply it with zero. This is in multiplication, it's just usual multiplication. 1 0 is also zero and 1 1 is 1.
But in addition, there's a there's a change. This is 0.
This is one.
This is one.
Or actually this is also one.
So all in all if you see if if you see while multiplying if you see 1 + 1 + 1 something like this this just means one.
Yeah. In matrix multiplication if you see something like this.
So this expression the value of this expression is just one ma'am.
>> Yeah >> ma'am the values will always be zero and one or it can be other constants.
You only when we multiply stuff why we multiply is what multiplication means is if you have a it's about the path right if you have a this means if you have a zero here that means and a one here that means you have from vertex one to vertex 2 there's an edge now what does this mean if in a square you have zero here and one here this means that You have a path from V_sub1 to V_sub_2 which involves other vertex 2. Right?
This is what it means. That means it's a it has a path from V1 to V2. If you have one here in a squared if a 1 2 entry of a square is one that means there is one vertex between v_sub1 and v_sub_2 and using that vortex you can connect v_sub1 and v_sub_2. So when you this is all about having a path a square is about having a path of order two from v_sub_1 to v_sub_2 or from if you have a² iig this means having a path of length two length two means this is a path of length two right this is a path of length three >> ma'am is this means >> exactly length two or like at most length two.
>> This is exactly two. This means exactly two. Do you have a path of length two from I to J? If you have it, you write one. If you don't have it, you write zero.
If we have a direct path uh >> from I to J let's say uh we have a direct path but uh not a path of length two then in that case will it be one or zero?
>> It should be zero.
>> It will be zero.
>> This is about path of path of length two. A cube is about path of length three. So that's the idea here. So you can only have zero and one. Someone was talking about having weights here.
>> Can you repeat repeat the line? How we get one? Multiply >> which line?
>> Uh after multiplying uh zero like how to multiply them >> multiply. Let's say, okay, let's say you have this thing. You have a matrix here.
You have 0 0 0 1 0 1 1 0. Let's say you have this thing.
And then you have to multiply. This is a and you have to find a square. So this will be 0 0 0 1 0 1 and 1 0 0. So first entry will be just zero because all the entries are zero here. Let's say you have to find a squared and two one entry of this. Two one entry means second row of this and first column of this. Right?
So this will be 1 * 0 this and this. So this is 1 0 this is 0 1 and this will be 1 1. So we know 1 * 0 is just 0. 0 * 1 is just 0. That's what I've written here. this entire thing and 1* 1 is one, right?
So this will just be one. Now let's say if instead you had if instead here you had one if you had this thing then you have one here then your answer would just be one. It's still one because 1 + 1 is one right here.
Is this okay?
>> So beta get one, right?
>> Sorry, what?
>> I'm talking about beta.
>> Yeah, beta here is one. It's one because for beta you have to multiply this row with this column.
So you'll get one. Beta will be one.
Beta is the 3/5th entry of this matrix.
Right? So you have to multiply third row and fifth column.
>> Okay. No.
>> Does anyone have any other doubt in this?
>> No ma'am.
>> Okay. Can we move to the next question?
>> Yes ma'am.
>> This is the next question. You have to use algorithm here.
So your dystra's algorithm is uh you have to start at starting what is always given to you and here it's given to the eight you have to start from here and you have to find uh you have to apply dystra's algorithm next. So how do we apply the dextra algorithm? This one obviously we do it using a table but we don't actually need a table here. If you want to make a table you can still make a table. A B C D E F but that's not needed because this one is just simpler.
You don't need a table here. Then you will write the distances here. So from A to A it's just zero. Then from A to B it's one. B A to C it's three and then 0 0. Others are at in at distance infinity. Right? So they'll be infinity infinity infinity. Then you will choose the minimum. So this one so you have to find the order right. So this one gets covered next. B gets covered next. So after a A is obviously the starting point. The next one that gets covered is we've already spoken we've already talked about this right that uh in our summary lectures that the minimum one you choose the minimum and then you fix it. That means after a the next vertex to be chosen is B. B gets fixed next. That order you have to find you have to find the order in which your vertices get fixed here. So A is there then B gets fixed.
So and then from B you have to find the immediate ones right this one this one and this one. So it will be one here you one the distance till B is now one. The distance till A is zero. From A to A it's zero. From A to B it's fixed one.
Now from B to E it will be 6 + this one already there. So it will be seven. So this distance till E will be 7. Then till E it will till D it will be 1 + 3 4.
Then till C it will be 1 + 2 3.
And this one has been fixed already.
Right? Or you can fix it here wherever you want. This does not matter.
So this has been fixed. So now you and this is still at distance infinity.
This is zero. So you have to choose the next minimum. The next minimum is C. So the next minimum that you choose is this C.
So first was A then B then C next minimum then you have to find the distance till C. From A to C the distance is three. It has been fixed.
Now from C you will have three. Here you have distance three. Here you have distance one. Here you have distance zero. Three you'll add four here. So it will be seven. And you only update when it's a better distance. Right? When it's a shorter distance. So you don't update it. It remains four.
Then that's it. You can you could only update D because only D is directly connected to C and you will not update it because you have a better option here. Four is smaller than seven. So no need to update. Keep it as four. 7 infinity 3 1 0. So to choose the minimum from these three, these two.
The next minimum is going to be four. So the next vertex to be chosen is D.
Then from D.
So it's going like this. From D you have directly connected once. D is already done, right? B is already done. So you don't need to >> ma'am from this one.
>> B we can go to D by this three path, right? That would cost uh less >> this one.
>> Yes ma'am.
>> How is it? B is already the distance till B. If you will take this route will be one. Now if you take this one it's three already and then there'll be more 1 2 4 and three.
>> No I am saying that A to B then B to D can't go like that B to C will be there uh there uh and from B to D that would cost us uh four 3 + 1.
>> That's all right. You don't have to. In fact, okay, you're talking about the path that this path this path is going to be shorter, >> right?
>> Yes, ma'am. Yes, ma'am.
>> That's fine. But we just need to know the order and this is going order has been asked, right? So, this this is going to be the order even when you take this one. And you're right. You should be taking this one instead of taking this path.
This is the path. But from this whole thing, you'll get this order.
So we are done till D right and then after D the distance is we change the distance. So till D we have distance how much is the distance till D? uh four >> okay and it does not even okay till distance till D is four right so it's four four here then from four this distance till F will be 4 + 1 5 this gets updated and then from uh this four from D to E it will be 4 + 4 8 and you already have seven a better option here so just keep it seven and you have to choose the minimum from these these two this time.
So the minimum is this one.
So the next in line is F.
And obvious the one that's left which is is that okay?
A B C D F E. That's the correct answer.
So if you been asked to find the order, this is what you have to do.
>> The answer is the number will be the value will be 11 is correct.
Value you don't need the value here.
>> Okay.
>> Okay. I decided according to the weightage of the vertex and I also got the same because I I'm always confused with this to choose you if you're doing it manually using just this and if you're not this table is also constructed using the weights only this is just a more systematic way and this graph is very simple what's happening here is you can clearly see that if I go from this path then the next that should that I should take what take is this one because this is also three this is also three so it doesn't matter if you go from A to C using this path that's also same if you directly go from A to C that also gives you the same value three then next you next you should be taking up is this one if you take this path this is a longer path if you take this one this is a shorter one + 3 so this is what you should be taking next this is 1 + 3 4 this is 1 + 6 That's what you're talking about, right?
That you've done it directly from the graphs without using this table. Is it?
>> But this this is not something that you should stick to because there might be complicated graphs in exam and you might not be able to do it using just this way.
This is not a sure short way that will give you the correct answer all the time. You might end up making mistakes doing this thing.
there there are always chances of slip ups in this this way that's why we have an algorithm to perform this thing right if you have a doubt in the algorithm I can explain that >> yes ma'am but >> I suggest >> u where that day also I was confused and uh to fix this how you are fixing this the the matrix This matrix is just distances. This is not even a matrix or anything. It's just distances written written here. So what we're doing here is we start with 0 1.
We start with a. You're doing the same thing. If you even if you'll do it manually, you'll do the same thing. What you'll do is you start from A and then you choose the minimum one. Minimum of 1 and three. That's how you decide that next up should be B. Right?
How did you decide that next up should be B? By looking at the minimum of one and three, right?
>> Yes. Yes.
>> That's what we do here in this algorithm. You choose the minimum. You write the distances. So this one is at distance 1, three, and all the others are a distance infinity. These ones are a distance infinity, right? And then you choose the minimum from here. And that's how you fix the distance. When do we fix the distance? When we find the minimum.
So if out of this row the minimum is one. this column the minimum is one you should fix the distance till B as one now this and that's what you were doing manually too right you chose this path and you said the distance for B is fixed now it's one right >> okay we need to fix that what is lesser than the I have the number >> yeah okay I'm not sure what you're asking but let's just let let me just quickly go through take you through this algorithm and then you can ask if that there are other doubts. So now you are at B. The distance from A to A is zero. It's fixed. And that's exactly what you do in the table. So you you mark zero as fixed. That means the distance you started from A. The distance from A to A is zero. The distance from A to A. B minimum distance from A to B is obviously the distance could be taken as 3 + 2 5 as well. But that's not the minimum distance.
So what our aim is to find the minimum distance. So the minimum distance from A to B is one and we fixed that distance here one. Then this is all this distance is already one and then you find the other ones. So the directly connected ones to B here are these ones.
So it's 2 3 and six. And then you add one to each of them because the distance till B is one. And if you will go to C the total distance will be one from here and two from here. Right? So the total distance till C will be three. The total distance here will be seven. The distance here will be four. And then you choose the minimum. That's what you're doing manually, right? We're doing the same thing in the table. That's it.
>> Yes, we do the same.
>> We've written 3 4 7 here and we choose the minimum then. And that's how we decide that okay, you choose the minimum from here. This is the minimum. So I'll go here. That's what we've done here.
Choose the vertex with the minimum distance. So choose C next.
So once we reach F. So at F we have covered uh um like uh uh four 4 + 1 5. So at F we are five.
So if we go to from E F to E. So 5 + 3 would be 8. So rather than going by there can we direct come from B to E.
>> That's what you have to do. If you have to find the minimum distance till E, it should not be eight. It should be seven because seven is that's why we didn't update seven. Right?
>> But we have not been asked the distance.
The good part here in this question is we don't need the distances. We just need the order. That's it.
>> This is MSQ questions, right? Nor.
>> Yeah. Not MSQ, it's MCQ.
>> I'm I mean, yeah. So, where where is the options?
I already told you I've not taken a screenshot of the options here.
But how does it matter? You anyway have to find this thing.
Okay. So that's it. I guess I don't have any more questions. If you have any doubts, you can discuss. We can discuss those doubts here.
question number. Let me tell you >> ma'am will there be uh any more uh revision session or uh this is the only one >> you will have a mock session with the TAS and please practice one type one one kind of question that I've forgotten here are the those ones the remman some ones please practice those questions because we're already uh running out of already half hour past the usual time. So I'm not doing that questionnaire but we we you have questions from man sam and please practice those questions the remman sam ones.
>> Okay.
Yeah, in a previous session we actually were asking about the weightage for the end term. Uh we were told that we'll get an intimation about that about the syllabus weightage whether now it's going to be more weightage given to 8 to 12 or how it's going to be allocated.
>> Just one sec.
>> Question number three, graded assignment 11.
assignment which >> uh 11 week >> okay let's just first discuss about the weightage part >> yes ma'am very feeling very scared >> uh and ma'am uh like one more thing uh when the TA session the mock like the mock discussion session will be recorded or But I mean quiz two what we understand we what we learned it did not come in exam >> what >> we practiced for this practical and it came theory questions only >> just one second. What >> in Q uh quiz two we practiced a lot practical questions solving questions and in in exam it came only theory theory >> there was there were questions which needed to be solved I don't think it was any the syllabus has nothing theory nothing of theory from week 5 to 8 I guess do we have any theorem theory from week 5 to Those must be conceptual questions.
We don't have any theory there. So, uh, graph theory holds a lot of weightage.
It's around 40%. So, please practice those questions from graph theory.
35 to 40% is from graph theory. And uh yeah, HTML and the other thing also which I realized is that like when we have this uh the quiz one and quiz two, we had two hours of time for the subject but now for the end term there is only of time.
>> Can you hear me now?
>> Yeah.
>> Ma'am, can you hear me?
>> Yes. Yes.
>> Yeah. Uh what my this thing I I see the I see the hall ticket is released today and there it is mentioned for the interm exam the time for the subject is 1 and a half hours whereas in Q quiz one and quiz two we had 2 hours of time for the exam. So I'm wondering how this interm being a full subject from 1 to 12 uh given that 1 and a half hours time will we be able to solve this?
>> Ma'am I did not received my hall ticket yet. What is able to solve it? It's been designed that way.
>> Okay but quiz one quiz two was for one hour.
>> I did not received my hall ticket yet.
Did you check with your dashboard?
>> I checked.
>> Just uh refresh your dashboard.
>> Have to contact the >> Where did you check your uh in your dashboard?
>> In the dashboard, the hall ticket on the left hand side you have the panel number right? Yes.
It's >> still written there. The hall ticket will be uploaded here only.
>> Maybe it takes some time.
Right. I think tonight or tomorrow morning you'll be seeing that. If not, >> okay, I checked this question. It's from the just one second. Yeah, this is you just have to find the matrices a in this question. Someone added out in this question. Just find the matrix A for each of the graphs and then you can find out A square and let >> uh you can solve >> just match it with what's given as for me to write firstly for me to okay >> ma'am what about uh wait is said only about the graph theory >> uh Yeah. The rest and the rest of the part is from week 1 to 9. So from week 1 to 9 you are 60% something in your exam.
The other weeks are equal weightage almost equal and not if not equal they're almost equal.
If you because there's it's been a lot of time this question someone has a doubt in this question it's going to take time for me to construct a for each of them and then find a square. So what you can do is there there are obviously tricks to this question you can uh ask this as doubt in one of your TA sessions. You do have TA sessions right?
Today is Tuesday so you're going to have sessions coming up. You can ask you can raise this question there.
Okay. So, we'll end this session here.
>> Yes.
>> Uh this hand exam questions are made by instructors or professors.
>> Sorry. What?
>> I mean uh this exam questions are made by instructors or professors.
>> You don't need to know that. All you need to know is that from whatever you've been taught and whatever you've learned, you'll be you should be able to solve those questions.
>> Thank you, ma'am. Okay. Right.
>> So, thank you. Thank you for
Related Videos
Escaping the Fog
LogicLemurGaming
760 views•2026-06-03
Olympiad Mathematics | Indian | Can You Solve This One?
PhilCoolMath
650 views•2026-06-03
A Brutal Radical Expression Made Easy! The Shortcut Changes Everything.
tamoshop
112 views•2026-06-02
V : jee main /advance class 11 mathematics : Binomial Theorem class-1 ( 29 may 2026 )
dcamclassesiitjeemainsadva9953
125 views•2026-05-29
Is This Pentomino Tileable?
3cycle
241 views•2026-05-30
This Sudoku Has Many Lines!!
CrackingTheCryptic
2K views•2026-05-29
Olympiad Mathematics | Indian Can You Solve This One?
PhilCoolMath
268 views•2026-06-02
Olympiad Mathematics | Indian | Can You Solve This?
PhilCoolMath
669 views•2026-06-02
