Hall's Theorem and Condition for Bipartite Matchings | Graph Theory, Hall's Marriage Theorem
Вставка
- Опубліковано 12 вер 2024
- What are Hall's Theorem and Hall's Condition for bipartite matchings in graph theory? Also sometimes called Hall's marriage theorem, we'll be going it in today's video graph theory lesson!
A bipartite graph with partite sets U and W, where U has as many or fewer vertices than W, satisfies Hall's condition if, for every subset S of U, S has as many or fewer vertices than it has neighbors (note that all of S's neighbors are in W, since this is a bipartite graph).
Now let G be a bipartite graph with partite sets U and W, where |U| is less than or equal to |W|. Hall's theorem states that G contains a matching that covers U if and only if G satisfies Hall's condition.
Lesson on matchings: • Matchings, Perfect Mat...
Proof of Hall's theorem: • Proof: Hall's Marriage...
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+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
Around 3:06 my voice comes in quietly from a different point in the video, I haven't the slightest clue why that happened. There are other weird audio issues with this lesson too, I'm sorry for that! You guys are awfully nice for not disliking this a bunch more, I cannot believe these audio errors I let through!
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
Listen man. I am so grateful for you content.
You have everything I'm studying for in class but you teach better.
Appreciate it, thanks for watching!
Ohh thanks for telling me that. I was afraid that my brand-new headphones have malfunctioned.
spooky
Yes bro I also felt same.
Iam on watching on Laptop, when I heard this sound, I felt in my phone, some video started playing.
0 Dislikes so We have perfect matching .
I appreciate your videos so much! You helped me pass Discrete Math, and now you are helping me with Graph Theory!
So glad to help - thanks for watching and good luck!
Hey how'd the rest of Discrete Math go? Did you end up taking more math after that?
Your explanations are so amazing and to the point! It is so easier to study graph theory, all thanks to you
Thanks so much Ria, I am so glad they have been helpful! If you haven't already, check out my graph theory playlist! Let me know if you ever have any questions! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
hey, I just wanted to say that I have watched a few of your videos today for the first time and wowwww I have realized how good you explain the concepts. I can watch and learn from your videos all day long without getting bored. Thank you very much !!
Thanks so much for the kind words, Saeideh, they mean a lot! I'm so glad the lessons have been helpful and hope they will continue to be. If you're looking to have a laugh after some studying, you may get a kick out of my playlist of Math Raps! ua-cam.com/play/PLztBpqftvzxW7a66b0dJPgknWsfbFQP-c.html
You're a beast bro. Need this class to graduate this December and you came in clutch. Love your content. Cheers from ATL 🦾
Wrath of math.. The goat of all time.... Finishing up my fourth year graph theory course, and these videos have been a blessing! Starting my masters in applied math in the fall, and you deserve some credit!
Cheers
Thanks a lot Jon, congrats and good luck! I'm so glad the videos have been helpful, and look forward to the day this playlist is complete, still a lot of topics I want to cover. Cheers!
Ty so much for the super clean explanation! I just finished my Discrete Math final and was watching ur videos last night for preparation. SUPER HELPFUL!!!
So glad to hear it, hope the final went well! Thanks for watching!
Good explanation, helping a lot on understanding Hall's Marriage Theorem!
Such an amazing explication with a high quality , Much respect to you Sir .
Thanks .
Thanks so much and it is my pleasure!
Damn ! you never cease to amaze me!! Fantastic video! Thank you !
Thanks so much! Glad it helped and let me know if you ever have any questions!
Great explanation! Simple and easy to understand!!
Thank you!
you're a really good teacher
Thank you! 😃
Hall yeah, thanks for another amazing video!
It is my pleasure - thanks for watching!
@@WrathofMath No, the pleasure is all mine; these explanations are tite 👌
Your videos are helping me a lot, thank you.
Thank you, Sir!
What a great video, I'm learning graph theory for my undergraduate thesis, but I have some problem with paired domination number and upper bound on paired domination number(the gamma of upper bound and gamma the minimum cardinality). I could not get the exact example cause lack of journal that explain and give the example of them. Would you mind if you make a explanation video about these problem? thankyou
Well explained. Thank you so much
great explaination
Could you please expalin Tutte's theorem
You're the goat of Graph Theory🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐
Great explanation , thx !
Great video as always. Thank you.
You're welcome, thanks for watching!
You just helped me nail my assignments! Super Grateful
Awesome! Thanks for watching!
Great Explanation! Love that!
Thank you, glad it was clear!
thank you sir!!
Most welcome!
Can you show the proof by induction of the vertex induced subgraph generated from G also satisfies Hall's condition
Samuel, if U and W in same order and not be perfect matching. How the graph looks? On the theorem I've read if order is p, then the edges is p/2. Graph look like perfect match. Tx you!
Thanks for sharing.
JFYI, the audio switched from left to right when scene changed :(
I noticed that just now, so weird! It's frustrating to come back to some of my lessons from before I really settled into my current setup, and seeing some of these weird issues. My iMac does this unbelievably irritating thing where it will pan my output audio to the right or left. This might have counterbalanced some weird problem going on with my audio in this video, so I didn't notice while working on it. It feels like my electronics conspired against me!
How would you go about finding all the subsets, especially in a much bigger bipartite graph?
love u man
Great job!
Thanks, Logan! Here is my graph theory playlist: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html if you're looking for more!
great explaination
Thank you!
can you do something on Mycielski's construction
Thanks a lot.
My pleasure, thanks for watching!
0 dislikes. Perfect
Thank you, I agree!
Thank you
No problem, thank you for watching! Be sure to check out the proof if you haven't it's a fun one!
awesome sir awesome.
Thank you! Many more graph theory lessons to come in my playlist: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
saved my life
Glad it helped, thanks for watching!
Hi just a heads up, the link for Lesson on matchings is wrong. It should be .../watch?v=chdr2aj4FUc
Thanks for watching and for letting me know! Someone else let me know this a while ago, and I read the comment, but apparently forgot to update it! It should be right now!