Matchings, Perfect Matchings, Maximum Matchings, and More! | Independent Edge Sets, Graph Theory
ฝัง
- เผยแพร่เมื่อ 5 ก.ค. 2024
- What are matchings, perfect matchings, complete matchings, maximal matchings, maximum matchings, and independent edge sets in graph theory? We'll be answering that great number of questions in today's graph theory video lesson!
A matching in a graph is a set of edges with no common end-vertices.
Halls' Theorem and Condition: • Hall's Theorem and Con...
Proof of Hall's Theorem: • Proof: Hall's Marriage...
Lesson on edge-induced subgraphs: • What is an Edge-Induce...
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
Some related lessons! Hall's Marriage Theorem: th-cam.com/video/Ihr6gMx7b9c/w-d-xo.html
Proof of Hall's Marriage Theorem: th-cam.com/video/4tu-H4ES0fk/w-d-xo.html
Regular Bipartite Graphs Have Perfect Matchings: th-cam.com/video/f9VTbSCBq0Y/w-d-xo.html
Did not expect to get an entire video to my question. Thank you!
Thanks for watching! Wrath of Math is all about customer service, haha! It was just good timing - I was going to record and edit a lesson last night anyways; and I was perfectly happy to talk about matchings, so it worked out great! Glad to be able to help!
Beautifully explained with ample amount of examples to make concepts crystal clear. Love it!
Really nice video! This deserves more upvotes!
Nice explanation...and the last brushing up was also needed...thanks for the video
I have watched your videos this whole Winter semester to help me with my Graph Theory course. Thank you so much for posting these, they are extremely helpful and so well thought out, your explanations are amazing!
very clean and clear explanation ever watched on this topic...Thank you
Thanks for watching and for your kind words, glad you found the lesson clear!
Well done! Subscribed. You are on the best way of becoming a youtube legend for all computer scientists and mathematicians who are going to be tested in discrete mathematics!
I like the color theory you use btw 🙂
Thanks so much for your kind words and for subscribing! I'm glad to be able to help!
Excellent explanation. Was a very useful primer to solve assignment problems.
Excellent video, great and clear explanation. Thank you for posting this.
I'm glad it was clear, thanks a lot for watching!
This was really helpful, I was lost trying to understand perfect matches in aromaticity (chemical graph theory) but this (and GPT-4) helped me make sense of it. The best part of the video, hands down, was the music at the end, we need more of that!
Well done bro, understood in 15 min what the teacher could not explain in 2h, subscribed for sure :D keep up the great work and stay safe
Thank you, so glad it helped! Thanks for subscribing and you stay safe as well!
Thank you so much. It really helped me to clear my concepts. Please keep going! Thanks
So glad it helped! Thanks for watching, and if you're looking for more graph theory be sure to check out my playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you have any video requests!
So well explained, amazing!
Man, I read like 5 articles preparing for a colloquium and just your video helped to understand. I gave you a sub, keep up the great work and keep educating young engineers and mathematicians.
So glad it helped! Thanks for watching and subscribing, and I will continue making the best lessons I can!
Thank you. This is super helpful. Missed graph theory last semester because of illness and now I need it.
You're welcome, I am so glad it helped! If you ever have any questions let me know, and I hope your illness is all gone!
You have the gift of explanning. Thanks for you work
So glad to help, thanks for watching!
That is the best explanation I have heard by far!
So glad to hear it! Thanks for watching!
me to encouraging friend: Oh no, i got an F
Encouraging Friend: 1:29
this gave a me a good chuckle
😆
Dear Wrath of Math.
I would be very grateful if you make a video on flow networks and about the algorithms like...........Ford and fulkerson ...augmented paths.......max flow min-cut theorem...and topics related to this. And as always....best videos I have seen so far. Too good explanations and I just luv your videos :)
It was an incredible and very helpful video, thanks a lot for your effort!
Thanks so much for watching and I am glad it helped! Let me know if you ever have any questions!
Wow, how an excellent explanation! Thank u so much. Have a nice day!
You're very welcome, I am so glad it helped and thanks for watching! A good day to you as well!
Very clean and understanding explaination for starters...
Glad to help, thanks for watching! If you want more on matchings, check out my lessons on Hall's marriage theorem.
th-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html
th-cam.com/video/4tu-H4ES0fk/w-d-xo.html
thx for the clear definition and explanation. You made an easy concept easy.
Glad it helped!
You were outstanding in terms of clarifying my understanding
So glad to hear it, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Simple and clearer..Thank you
My pleasure!
Bro, this channel is insanely good for getting into graph theory and combinatorics
That's what I like to hear, thank you! Let me know if you have any requests!
Great ! I was looking for the topic "Maximum matching"
Glad it helped, thanks for watching!
good, clear explanation. keep them coming please.
Thank you, will do!
Hi man! Great explanation and a great video! My question is: what videos from your graph theory playlist are essential and must-see(and know) for understanding the matching concept and being able to write a paper on it? I am a newcomer to graph theory and I have this as an assignment, and I think that your channel is a massive help for it. Thanks in advance!
Very clear explanation. Thank you
You're welcome! Thanks for watching!
Thanks bro.that's really great explanation
you are doing a great job brother..love the way u explain it.
Thanks a lot!
Helps a ton! Thanks a lot! My 80-year old professor was even not able to explain them clearly.
So glad it helped, thank you for watching!
Amazing explanation , thank you sir !
No problem, thank you for watching! Check out my Graph Theory playlist if you're looking for more lessons on the topic, many more coming soon! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
thank you sir for this lesson, it helps me a lot
Glad to hear it, thanks for watching!
thank you! very helpful.
Holy crap this video is really good. Well-explained dude!
Thanks a lot!
That augmented path Algo, I learnt from Dr. A.R. Ranadey, IIT BOMBAY, INDIA. He explained it so well
you are also good.
You sir have a talent for explaining things in a manner that anyone can understand! You will get me through this semester of Graph Theory. Thank you!
Thanks so much, Elizabeth! I hope you'll continue to find the lessons helpful and let me know if you ever have any questions! More (spooky) graph theory videos are on the way!
Out of curiosity, how'd your graph theory class go?
Very nice explanation, thank you!
Glad it helped!
As someone who’s dabbled in making videos, this is really high quality. Great and thanks
Thanks a lot!
Perfect sir. I really appreciate your efforts, very helpfull
Thank you for watching!
great explanation!
I do my best! Thanks for watching and check out my graph theory playlist for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
I loved the way u sum it all
Thank you - I do my best! Matchings is a fun topic!
Great explaination
Thank you, glad it helped!
great video well explained.
Thank you!
loved the explanation, thank you :D
You're very welcome, thanks for watching!
Thank you for this video😊
No problem, thanks for watching! If you're looking for more graph theory, be sure to check out my Graph Theory playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank u sooo much man! Very clear explanation👌
My pleasure, so glad it was clear and thanks for watching!
amazing sir , so good explanation ,thanks a lot sir
So glad it helped, thanks for watching! If you're looking for more on graph theory, check out my graph theory playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any video requests!
Very good content !
Thank you, Jean!
This is amazing, thank you so much !
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
thank you very much tomorrow is my graph theory final exam and this vids is very helpful wish me luck
Best of luck!
It was clear. Thank you!
Glad to hear it! You're welcome and thanks for watching!
This video save my discrete math. TY!
Exam I mean.
So glad it helped! Thanks for watching and let me know if you ever have any questions!
Could you possible explain clearly max weight branching and how to condense a weigthed digraph? Thank you for your clear explaining I appreciate so much.
thankyouu soo much this video is very helpful for me bcs tomorrow i've to do an exam but i still dont have any idea about the matching theory
I am glad it was helpful and good luck on your exam! I'm not sure what you mean by "the matching theory". As far as matching theorems go, I have a couple of videos on Hall's theorem which you may be interested in.
Introducing the theorem: th-cam.com/video/Ihr6gMx7b9c/w-d-xo.html
Proof: th-cam.com/video/4tu-H4ES0fk/w-d-xo.html
Hi, could you make a video about minimum-cost perfect matching and different approaches to finding it?
Thank you very much!
You're welcome!
Pls make a video on augmenting paths as well
Please make a video on alternating path and augmenting path
Thanks! Subscribed.
Thanks for watching and subscribing!
Excellent
Thank you!
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
Perfect sir.
Thank you!
Can you please do a detailed video on path partitioning of directed graphs?
excellent
The ending was epic
Thank you! Here is a link to that full song: th-cam.com/video/OKBdXOrpA2w/w-d-xo.html
Matchings: 00:00
Maximal matchings: 06:28
Maximum matchings: 08:35
Perfect matchings: 10:55
thank you for your effort, and I have question; the alpha prime (G)=3?🐝💐
hi i have this question to find maximal in a ring graph:
Let p0, . . . , pn−1 be n processors on a directed ring that Dijkstra considered in his selfstabilizing token circulation algorithm (in which processors are semi-uniform, i.e., there
is one distinguished processor, p0, that runs a different program than all other processors
but processors have no unique identifiers). Recall that in Dijkstra’s directed ring, each
processor pi can only read from pi−1 mod n’s shared variables and each processor can
use shared variables of constant size. Design a deterministic self-stabilizing matching
algorithm that always provides an optimal solution
Can you do a video on generating functions? Personally, I'd like to see how they can be used to solve recurrence relations and get the nth term without iteration.
maybe you could read Concrete Mathematic by Knuth in chapter 7, it will help you a lot!
amazing
"Match"-ing is right, 'cause this playlist is fire 🔥
Appreciate you! 🔥🔥
@@WrathofMath And I appreciate you, what with your helping us to become academically independent, stay at the edge of our seats, and get set 👍
Thank you for the clear explanation of matchings. It did help to see an example that is not a bipartite graph.
It helps me to see a matching as a marriage. A matching edge is a marriage between 2 adjacent vertices. A vertex can belong to only one marriage. As many vertices as possible should get married. If the order of the graph is odd (odd vertex count) then at least 1 vertex will remain single.
please do a video max matching min vertex cover theorem
Awesome!
Thanks, Peiman! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Thanks a lot for making these videos. Would you mind adding one on Konig-Egervary theorem and its proof?
Hi! Do you have any lesson regarding linear programming?
Great video. Love your chess board!
Thank you, Muddassir! The chess board has been replaced by holiday decor for the new lessons coming out this month, but it will be back for 2021 haha!
Can you give an idea about Augmenting and alternating path
Can you teach vizing's theorem please?
tnx man
Glad to help!
"Thats a really good f" love it =)
Haha, thank you! Every time I rewatch this video I am impressed by that f!
Can you explain what “matching polynomials”?
Could you explane "Rainbow numbers for matching"?
12:00
Don't worry. I sometimes watch your video when I'm dropping my browns.
integer linear programming for matching would be useful.
best on youtube
Thanks so much!
i really forgot whatever i learned . Thanks
"That's a really good f"
Same, man, same.
Does matching ( maximal, maximum , perfect) exist for graphs with self loops? That is if we consider the degree of the loop as 1 ?
Thanks for watching and the question! I'd think a loop would have no impact whatsoever on matchings, since it couldn't possibly be included in one, as matchings should induce bipartite subgraphs which a loop would prevent. That said, I've never looked into this topic specifically, a search may yield results that have found it useful to treat this subject differently.
Please Explain Minimal Matching too.
Thanks for watching and I am not sure what you mean. We can make a matching as small as we want, since it is just a set of edges that are not adjacent to each other. We could take any one edge from a graph to be a "minimal" matching, since there would be no matching that is a proper subset of it.
perfekt!
Thank you!
Please give explanation of graphs having 1-factors
Thanks for watching and finally someone asks about 1-factors! Thanks for the request and I'll get to work on some lessons about graph factorizations!
Wow you're a mathematician, rapper, and guitar player! How long have you been playing guitar? What's your music background?
Yes, there is a lot to enjoy in the world! I began with saxophone when I was in 6th grade or so, and then piano, and a bunch of other stuff, I only started learning guitar in college. Mostly self taught in everything aside from saxophone and some piano lessons. Started rapping 2013 or 14. Do you play music?
@@WrathofMath Yes there really is a lot to enjoy :) That's a lot of instruments! I've also been trying to learn the piano and started during covid times.
If you think of matchings in terms of bijections does it mean that the bijection f has to satisfy {v,f(v)} is an edge for every v in vertex set?
Almost, but not quite, there is a little bit of extra detail in there that you may be thinking of but just not writing. Let's say we have a graph G = (V, E) and a matching described by a bijection f. Firstly, the bijection, f, would have to be from some subset of V, say X, to some other subset of V, say Y. So it won't be the case that { v, f(v) } is an edge for every vertex v of V, but rather { v, f(v) } will be an edge for every vertex v of X, since that is the domain of the bijection.
If f represents a complete matching, then every vertex of V will either be an element of X or an element of Y (so X union Y equals V). In other words, every vertex v of V will either be in X, or there will be a vertex u in X so that f(u) = v. Great question! Does that explanation help?
Wrath of Math I think so. So in the case of a bipartite graph G=(U,V,E). Then G has a complete matching from U to V if there exists a bijective function f:U->V such that {u,f(u)} belongs to E for every u in U?
Exactly!
Wrath of Math Thanks. The video was v helpful
@@WrathofMath I have project due today and I'm at the end of a proof with one more thing to show. Could you please help me show why if 𝐴,𝐵⊆𝑋 and |𝑁(𝐴)|=|𝐴| and |𝑁(𝐵)|=|𝐵| in a finite bipartite graph 𝐺 with bipartition 𝑋∪𝑌 then |𝑁(𝐴∪𝐵)|=|𝐴∪𝐵|. Note: Hall's condition holds on 𝑋? It seems obvious but I can figure how to show it
Thank you
Is there a video for Adjacency matrix?
th-cam.com/video/7AhHGp7EzZ8/w-d-xo.html&pp=ygUQYWRoYWNlbmN5IG1hdHJpeA%3D%3D
@@WrathofMath ❤❤
Would be amazing if you taught my combinatorics lecture how to present charismatically so that students don’t get bored.
Haha I appreciate the sentiment! I just enjoy talking about math, so I think any charisma comes from me just being happy when I record videos. To give your professor a break, I might not be a charismatic presenter either if I had to teach the same thing year after year. But, to not give your professor a break - I think I would be. It's fun to teach people new things! If you're looking for more graph theory, check out my playlist, and let me know if you have any video requests! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html