Vertex Covers and Vertex Covering Numbers | Graph Theory
ฝัง
- เผยแพร่เมื่อ 7 ส.ค. 2021
- We introduce vertex covers, minimum vertex covers, and vertex covering numbers! We'll see some examples and non-examples of vertex covers, as well as minimum vertex covers and some that aren't minimum. The number of vertices in a minimum vertex cover is called the vertex covering number of the graph. We'll discuss why the complement of a vertex cover is an independent vertex set, and see how the covering number plus the independence number is the order of a graph (Gallai identity). We'll also discuss covering numbers of complete graphs, cycles, and complete bipartite graphs. #GraphTheory
A vertex is said to cover its incident edges. A set of vertices is a vertex cover is if covers every edge in the graph.
Independent Vertex Sets: • Independent Vertex Set...
Proof Complement of Vertex Cover is Independent Set: • Complement of Vertex C...
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)
Graph Theory playlist: • Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050
Check out the lesson on independent vertex sets if you need a recap! th-cam.com/video/0stavxEccvE/w-d-xo.html
Thank you for your explanations - this was missing in my understanding of the NP Reduction between Independent Set and Vertex Cover
Vertex covering numbers? More like "Very good lectures, that are better than others!" 👍
Great now I get it! Thanks a lot sir!
Thank you, thank you soo muchhh!! 🥺🙌🏻 That’s very helpful of you!
So glad it helped, thanks for watching!
Crystal clear explanation, thank you!!! I love how to explain the definitions of each specific terms, I always get confused by those cause it's hard for me to remember the details, you're literally the math teacher I needed growing up
you*
Thanks so much!
Thankyou sir, for easy and simple way of explanation.
Glad to help!
thanks a lot
Hello and thank you for the helpful video! What is the name of graph theory textbook you mention here?
awesome video!
Thank you!
@@WrathofMath you are welcome!
Thank you
Glad to help!
Co- efficient of chromatic polynomial pls...
Thank you a lot for your videos. Do u have videos on edge covering? And random graphs? If not would like to have a videos on them. Kindly requesting you to do a videos on those topic. Thank you so much again. 🎉
Thanks for watching! I have no videos on either topic. I can see about doing one on edge coverings, probably will be a while for a random graphs lesson though, haven't studied them much.
@@WrathofMath okey okey, please try if you can. Thank you !
th-cam.com/video/7HiUndJKfEQ/w-d-xo.html
Currently unlisted but will be released tonight at midnight.
@@WrathofMath wow!! 🎊🎊 😍
Thank you so much. 😍😍
Really appreciate what you are doing.
Aww, the proof for a future video never came, it seems. Awesome video regardless!
Which one do you mean? Here's one which I just added to the description (had forgot until now): th-cam.com/video/Sl85juLEHBE/w-d-xo.html
And I'll see if I can do the other soon, it has been too long since I made some good graph theory content! Thanks for watching!
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)??