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!
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!" 👍
Thank you, thank you soo muchhh!! 🥺🙌🏻 That’s very helpful of you!
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
Great now I get it! Thanks a lot sir!
Thankyou sir, for easy and simple way of explanation.
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
Co- efficient of chromatic polynomial pls...
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)??
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. 🎉
Aww, the proof for a future video never came, it seems. Awesome video regardless!