Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I was so confused on the independent portion. Your videos helped me better understand and solve the Q: Determine whether the Petersen graph is bipartite, and find the size of its largestindependentset. Thank you so much!!!
Thanks for watching and based on what I wrote in the description, that's exactly right! (I didn't look at the problem again so I just go off the solution in the description) Good work!
5:16 WHY IS B AND E a max Independent vertex set of the graph??? B and E are vertices that have an edge right….so how are they in dependent It’s not a direct edge is that why? Or excactly adjacent is that why?
The vertices B and E are not adjacent to each other because there is no edge joining them directly together. The shortest path from B to E consists of two edges and travels through vertex D.
Glad to hear it, thanks for watching! Let me know if you have any questions - and check out my graph theory playlist if you're looking for more: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Hey! Can you please make a video on vertex cover, a topic subsequent to this and is pretty short I guess. The thing is there's no perfect video on vertex cover which provides the concept and some general important points. It'd be highly helpful if you could do that! Thank you so much.
Thanks for the requests, Sophie! Great ideas and I’ll definitely add them to my list. No guarantees we’ll get to in depth lessons on the topics soon but I can probably start to touch on them soon. I like to go in order with the lessons!
Sir if the question is how many independent sets are there in the graph ?? Then should we consider only the maximum Independent set or add other independent sets too ?
Thanks for watching and for the question! If you were simply asked "How many independent sets are there in a graph?" then you would need to consider all independent sets in the graph, not only the maximum independent sets. You then might consider all maximal independent sets of the graph, since by definition every independent set of the graph must be a subset of a maximal independent set. However, some subsets of different maximal independent sets may be the same. For example, consider a graph with vertices {v1, v2, v3, v4} with just one edge joining v1 and v3. In this graph, both {v1, v2, v4} and {v2, v3, v4} are maximal independent sets. Notice they have some subsets in common. Point being - to count all the independent sets, we cannot just count all the subsets of maximal independent sets because if we do that - we may double count some independent sets.
Thank you for watching! I use the app Notability to make the lessons, which is a note taking app. I previously used another app called GoodNotes, which I actually prefer for my personal use. But I think this one looks better for the lessons.
Thanks for watching and good question! Consider a complete bipartite graph with equal partite sets. Does that help? Or, you could consider a complete graph. Or come up with plenty of other examples to answer your question! Let me know if you have any other questions, and if you're looking for more graph theory be sure to check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thanks for watching Raymond and Sarit is exactly right, the independence number is the greatest cardinality of an independent vertex set in the graph. If the independence number was defined as the least cardinality of an independent vertex set then it would be 1 for every graph (because we can always put just one vertex in a set so none of its neighbors are in the set), or 0 if we consider the empty set a trivial independent set.
Thanks for the request! What do you mean exactly? My first thought was that by chromatic partitioning you mean, if we have a proper coloring of a graph, a chromatic partitioning would be a partition of the vertex set into independent sets of same-colored vertices. Is that what you mean? I see various authors using the term to mean quite different things, so let me know what exactly you mean and perhaps I can make a suitable video!
Thanks for watching and I am not sure what you mean. There is no particular notation for independent sets that I am aware of. Remember an independent set is a set of vertices, none of which are adjacent, so at times an independent set may be represented notationally as the complement of some complete graph, but that's all I can think of.
@@WrathofMath welcome....yeah about maximum independent set problem in bipartite graphs.....i mean why bipartite graphs ..and i will be happy if you can give me a real example of that problem.....and the lineair programme of that problem
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I was so confused on the independent portion. Your videos helped me better understand and solve the Q: Determine whether the Petersen graph is bipartite, and find the size of its largestindependentset. Thank you so much!!!
So glad to help, thanks for watching!
The answer for last problem(my opinion) :- Two possibilities {b,d,f} or {g,c,e} anyway alpha(G) = 3
Thanks for watching and based on what I wrote in the description, that's exactly right! (I didn't look at the problem again so I just go off the solution in the description) Good work!
Maximal Independence Set:{b,d,f}@@WrathofMath
@@asadrao5147 yea i thought of this but e wont come it seems
Thanks so much dude...after searching two days I got this clear video..
Now all my doubts cleared..😊😊
I'm glad it helped and thanks a lot for watching!
😍😍😍😍😍😍🤣🤣😋😍🤣😍😍😍😍😍😍
Great video! The independence (max) number of the last graph is 3. Can you also guide what is an independence polynomial and how to construct it?
Your videos are so helpful, thank you for your hard work!
best video, I learned it in one line
So glad it helped! Thanks for watching!
Sir, you are a God thank you for saving me from discrete math,
So glad to help - thanks for watching! Let me know if you have any questions!
Could you please make a video on Vertex Cover? And its relationship with independent sets.
5:16 WHY IS B AND E a max Independent vertex set of the graph??? B and E are vertices that have an edge right….so how are they in dependent
It’s not a direct edge is that why? Or excactly adjacent is that why?
The vertices B and E are not adjacent to each other because there is no edge joining them directly together. The shortest path from B to E consists of two edges and travels through vertex D.
This is what exactly I'm looking for
Glad to hear it, thanks for watching! Let me know if you have any questions - and check out my graph theory playlist if you're looking for more: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
so clear, thanks
Really good work. Thanks
Clear and perfect, thanks a lot!
Thank you so much bro ❤️
Glad to help!
the independence number for the graph that you had given for practice i.e the last graph is 3. Is the answer correct?
Extremely clear, thank you very much!
Glad to hear it, thanks for watching!
Hey! Can you please make a video on vertex cover, a topic subsequent to this and is pretty short I guess. The thing is there's no perfect video on vertex cover which provides the concept and some general important points.
It'd be highly helpful if you could do that! Thank you so much.
Great idea! Thanks for watching and I'll make a vertex cover lesson as soon as I can!
Here is the new lesson! ruclips.net/video/1KkT7y8nxH0/видео.html
Thank u so much , you clear all my doubt
So glad to help! Thanks for watching!
how cold anyone dislike your videos
Maybe some insect rights activists could dislike this one: ruclips.net/video/rw-OIl0RHpg/видео.html
Otherwise, I don't know!
A video on prims algorithm is needed
Thanks for watching and you're right! Maybe I'll do it soon - no guarantees though!
Bam! ruclips.net/video/AoV7ml-WzIY/видео.html
I haven't released the video yet, but you can watch it early with that link, thanks for the request!
Brilliant explanation!
Thank you! I am glad you found it clear!
Would it be possible to cover vertex cover and dominating set and the relationship among the three? Thank you!
Thanks for the requests, Sophie! Great ideas and I’ll definitely add them to my list. No guarantees we’ll get to in depth lessons on the topics soon but I can probably start to touch on them soon. I like to go in order with the lessons!
Sir if the question is how many independent sets are there in the graph ??
Then should we consider only the maximum Independent set or add other independent sets too ?
Thanks for watching and for the question! If you were simply asked "How many independent sets are there in a graph?" then you would need to consider all independent sets in the graph, not only the maximum independent sets. You then might consider all maximal independent sets of the graph, since by definition every independent set of the graph must be a subset of a maximal independent set. However, some subsets of different maximal independent sets may be the same.
For example, consider a graph with vertices {v1, v2, v3, v4} with just one edge joining v1 and v3. In this graph, both {v1, v2, v4} and {v2, v3, v4} are maximal independent sets. Notice they have some subsets in common. Point being - to count all the independent sets, we cannot just count all the subsets of maximal independent sets because if we do that - we may double count some independent sets.
@@WrathofMath thanks a lot sir... It's very clear now ... Your teaching is magnificent 🔥
The best math channel! Helping me so much with my algorithm design class and a great review of discrete mathematics
Thanks so much, Jasmine! So glad to help!
Please make a video on k-factor (1-factor, 2-factor) in matching.
Great videos! Super commendable. Can you please explain interval graphs and chordal graphs in one video? Thank you
Thank you! And thanks for the request, I'll see what I can do - but I am very busy these days!
Thank you :)
Do you use any note taking app to create the videos ?
Thank you for watching! I use the app Notability to make the lessons, which is a note taking app. I previously used another app called GoodNotes, which I actually prefer for my personal use. But I think this one looks better for the lessons.
Can any when suggest the algorithm to find all independent vertex set in graph?
Plz make videos on probability,calculas and numerical aptitude😊
b,d,f and c,g,e
4
Kuratowskis Theorem sir can you explain this?
The answer ist three ? Right
Plz reply.what is the role of graph theory in computer programming??
thank you so much!
Glad to help, thanks for watching!
Independent vertex sets? More like "Incredible lectures that help people pass classes, I bet!"
Can you please give me an idea about dominating set
can we have more than one maximal independent set for a graph or is it unique?
Thanks for watching and good question! Consider a complete bipartite graph with equal partite sets. Does that help? Or, you could consider a complete graph. Or come up with plenty of other examples to answer your question! Let me know if you have any other questions, and if you're looking for more graph theory be sure to check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@@WrathofMath Thank you. That was helpful
Thank u sir 😍
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Is it 3? the last graph
Thanks for watching and nice work, that's exactly right! The set { b, d, f } is a maximum independent set of this graph. Can you find another one?
@@WrathofMath c g e
thank you so much sir
You're very welcome! Thank you for watching!
wow thank you
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
why is the independent set answer not just {a}? since it is only one value which is less than 3 {b, d, f}...?
Independence number is the greatest possible set number. Otherwise there can be multiple independence numbers for a single graph. Hence 3.
Thanks for watching Raymond and Sarit is exactly right, the independence number is the greatest cardinality of an independent vertex set in the graph. If the independence number was defined as the least cardinality of an independent vertex set then it would be 1 for every graph (because we can always put just one vertex in a set so none of its neighbors are in the set), or 0 if we consider the empty set a trivial independent set.
request u to make video on chromatic partitioning please..
Thanks for the request! What do you mean exactly? My first thought was that by chromatic partitioning you mean, if we have a proper coloring of a graph, a chromatic partitioning would be a partition of the vertex set into independent sets of same-colored vertices. Is that what you mean? I see various authors using the term to mean quite different things, so let me know what exactly you mean and perhaps I can make a suitable video!
Please Give notations for independent sets
Thanks for watching and I am not sure what you mean. There is no particular notation for independent sets that I am aware of. Remember an independent set is a set of vertices, none of which are adjacent, so at times an independent set may be represented notationally as the complement of some complete graph, but that's all I can think of.
Cardinality no. OR independence no.=Zero of last given graph.
Thank you Sir!
My pleasure, thank you for watching!
Great
Thank you! Let me know if you ever have any video requests!
No algorithm ?
hello ....could you help me
Thanks for watching, I’d be happy to help if I can! Do you have a question?
@@WrathofMath welcome....yeah about maximum independent set problem in bipartite graphs.....i mean why bipartite graphs ..and i will be happy if you can give me a real example of that problem.....and the lineair programme of that problem