Independent Vertex Sets and Independence Numbers | Graph Theory
Вставка
- Опубліковано 12 вер 2024
- What are independent vertex sets in graph theory? We'll go over independent sets, their definition and examples, and some related concepts like the vertex independence number of a graph in today's video graph theory lesson!
A subset of the vertex set of a graph is an independent vertex set if and only if it contains no pair of adjacent vertices. It's like a partite set of a bipartite graph!
If an independent set cannot be made bigger by adding another vertex from the graph, while preserving its independence, then it is called a maximal independent set.
If an independent set is of the greatest cardinality possible for any independent set of its graph, then it is a maximum independent set. Maximum independent sets are not unique. The cardinality of a graphs's maximum independent sets is called the graph's independence number, or vertex independence number.
SOLUTION TO PRACTICE PROBLEM:
The independence number of the graph is 3. The set { b, d, f } is a maximum independent set of this graph. So is the set { c, e, g }.
If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps support Wrath of Math!
PURCHASE "A First Course in Graph Theory": amzn.to/31hgvvJ
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcam...
Vallow Spotify: open.spotify.c...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
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!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
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!
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!
😍😍😍😍😍😍🤣🤣😋😍🤣😍😍😍😍😍😍
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!
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!
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: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
best video, I learned it in one line
So glad it helped! Thanks for watching!
the independence number for the graph that you had given for practice i.e the last graph is 3. Is the answer correct?
Could you please make a video on Vertex Cover? And its relationship with independent sets.
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!
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!
The answer ist three ? Right
Really good work. Thanks
Thank you so much bro ❤️
Glad to help!
Clear and perfect, thanks a lot!
Extremely clear, thank you very much!
Glad to hear it, thanks for watching!
Thank u so much , you clear all my doubt
So glad to help! Thanks for watching!
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.
Please make a video on k-factor (1-factor, 2-factor) in matching.
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! ua-cam.com/video/1KkT7y8nxH0/v-deo.html
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.
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 🔥
Brilliant explanation!
Thank you! I am glad you found it clear!
4
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!
how cold anyone dislike your videos
Maybe some insect rights activists could dislike this one: ua-cam.com/video/rw-OIl0RHpg/v-deo.html
Otherwise, I don't know!
Plz make videos on probability,calculas and numerical aptitude😊
wow thank you
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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!
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!
b,d,f and c,g,e
Plz reply.what is the role of graph theory in computer programming??
Can any when suggest the algorithm to find all independent vertex set in graph?
A video on prims algorithm is needed
Thanks for watching and you're right! Maybe I'll do it soon - no guarantees though!
Bam! ua-cam.com/video/AoV7ml-WzIY/v-deo.html
I haven't released the video yet, but you can watch it early with that link, thanks for the request!
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!
Can you please give me an idea about dominating set
Thank u sir 😍
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Independent vertex sets? More like "Incredible lectures that help people pass classes, I bet!"
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.
No algorithm ?
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Thank you. That was helpful
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!
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.
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