Matchings, Perfect Matchings, Maximum Matchings, and More! | Independent Edge Sets, Graph Theory
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
Пікірлер: 177
Some related lessons! Hall's Marriage Theorem: kzread.info/dash/bejne/e5ymmMmGqJrIacY.html Proof of Hall's Marriage Theorem: kzread.info/dash/bejne/Zqipj6ptdbaWls4.html Regular Bipartite Graphs Have Perfect Matchings: kzread.info/dash/bejne/mG2KtsSMc6XXYLw.html
Did not expect to get an entire video to my question. Thank you!
@WrathofMath
4 жыл бұрын
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!
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!
Nice explanation...and the last brushing up was also needed...thanks for the video
very clean and clear explanation ever watched on this topic...Thank you
@WrathofMath
4 жыл бұрын
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 🙂
@WrathofMath
4 жыл бұрын
Thanks so much for your kind words and for subscribing! I'm glad to be able to help!
Really nice video! This deserves more upvotes!
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!
@WrathofMath
3 жыл бұрын
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!
Excellent explanation. Was a very useful primer to solve assignment problems.
me to encouraging friend: Oh no, i got an F Encouraging Friend: 1:29
@WrathofMath
3 жыл бұрын
this gave a me a good chuckle
Excellent video, great and clear explanation. Thank you for posting this.
@WrathofMath
4 жыл бұрын
I'm glad it was clear, thanks a lot for watching!
You have the gift of explanning. Thanks for you work
@WrathofMath
2 жыл бұрын
So glad to help, thanks for watching!
Thank you so much. It really helped me to clear my concepts. Please keep going! Thanks
@WrathofMath
2 жыл бұрын
So glad it helped! Thanks for watching, and if you're looking for more graph theory be sure to check out my playlist: kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Let me know if you have any video requests!
Thank you. This is super helpful. Missed graph theory last semester because of illness and now I need it.
@WrathofMath
3 жыл бұрын
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!
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 :)
That is the best explanation I have heard by far!
@WrathofMath
4 жыл бұрын
So glad to hear it! Thanks for watching!
Very clean and understanding explaination for starters...
@WrathofMath
2 жыл бұрын
Glad to help, thanks for watching! If you want more on matchings, check out my lessons on Hall's marriage theorem. kzread.info/dron/Q2UBhg5nwWCL2aPC7_IpDQ.html kzread.info/dash/bejne/Zqipj6ptdbaWls4.html
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
@WrathofMath
3 жыл бұрын
Thank you, so glad it helped! Thanks for subscribing and you stay safe as well!
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.
@WrathofMath
3 жыл бұрын
So glad it helped! Thanks for watching and subscribing, and I will continue making the best lessons I can!
You were outstanding in terms of clarifying my understanding
@WrathofMath
2 жыл бұрын
So glad to hear it, thanks for watching! If you're looking for more graph theory, check out my playlist! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Simple and clearer..Thank you
@WrathofMath
Жыл бұрын
My pleasure!
Thanks bro.that's really great explanation
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!
Wow, how an excellent explanation! Thank u so much. Have a nice day!
@WrathofMath
4 жыл бұрын
You're very welcome, I am so glad it helped and thanks for watching! A good day to you as well!
It was an incredible and very helpful video, thanks a lot for your effort!
@WrathofMath
3 жыл бұрын
Thanks so much for watching and I am glad it helped! Let me know if you ever have any questions!
Great ! I was looking for the topic "Maximum matching"
@WrathofMath
3 жыл бұрын
Glad it helped, thanks for watching!
Very clear explanation. Thank you
@WrathofMath
3 жыл бұрын
You're welcome! Thanks for watching!
thank you! very helpful.
thank you sir for this lesson, it helps me a lot
@WrathofMath
Жыл бұрын
Glad to hear it, thanks for watching!
great explanation!
@WrathofMath
2 жыл бұрын
I do my best! Thanks for watching and check out my graph theory playlist for more: kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
good, clear explanation. keep them coming please.
@WrathofMath
2 жыл бұрын
Thank you, will do!
thank you very much! I understand it now. My slides were confusing.
Amazing explanation , thank you sir !
@WrathofMath
3 жыл бұрын
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! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
That augmented path Algo, I learnt from Dr. A.R. Ranadey, IIT BOMBAY, INDIA. He explained it so well you are also good.
you are doing a great job brother..love the way u explain it.
@WrathofMath
2 жыл бұрын
Thanks a lot!
Very nice explanation, thank you!
@WrathofMath
3 жыл бұрын
Glad it helped!
great video well explained.
@WrathofMath
Жыл бұрын
Thank you!
Perfect sir. I really appreciate your efforts, very helpfull
@WrathofMath
8 ай бұрын
Thank you for watching!
Bro, this channel is insanely good for getting into graph theory and combinatorics
@WrathofMath
2 жыл бұрын
That's what I like to hear, thank you! Let me know if you have any requests!
Great explaination
@WrathofMath
3 жыл бұрын
Thank you, glad it helped!
loved the explanation, thank you :D
@WrathofMath
2 жыл бұрын
You're very welcome, thanks for watching!
Holy crap this video is really good. Well-explained dude!
@WrathofMath
3 жыл бұрын
Thanks a lot!
I loved the way u sum it all
@WrathofMath
2 жыл бұрын
Thank you - I do my best! Matchings is a fun topic!
Helps a ton! Thanks a lot! My 80-year old professor was even not able to explain them clearly.
@WrathofMath
3 жыл бұрын
So glad it helped, thank you for watching!
Very good content !
@WrathofMath
3 жыл бұрын
Thank you, Jean!
Thank you for this video😊
@WrathofMath
3 жыл бұрын
No problem, thanks for watching! If you're looking for more graph theory, be sure to check out my Graph Theory playlist! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
As someone who’s dabbled in making videos, this is really high quality. Great and thanks
@WrathofMath
Жыл бұрын
Thanks a lot!
amazing sir , so good explanation ,thanks a lot sir
@WrathofMath
3 жыл бұрын
So glad it helped, thanks for watching! If you're looking for more on graph theory, check out my graph theory playlist! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Let me know if you ever have any video requests!
Thank u sooo much man! Very clear explanation👌
@WrathofMath
3 жыл бұрын
My pleasure, so glad it was clear and thanks for watching!
This video save my discrete math. TY!
@felixlolll6220
3 жыл бұрын
Exam I mean.
@WrathofMath
3 жыл бұрын
So glad it helped! Thanks for watching and let me know if you ever have any questions!
This is amazing, thank you so much !
@WrathofMath
2 жыл бұрын
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
It was clear. Thank you!
@WrathofMath
3 жыл бұрын
Glad to hear it! You're welcome and thanks for watching!
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.
Thank you very much!
@WrathofMath
4 ай бұрын
You're welcome!
Thanks! Subscribed.
@WrathofMath
4 жыл бұрын
Thanks for watching and subscribing!
thank you very much tomorrow is my graph theory final exam and this vids is very helpful wish me luck
@WrathofMath
11 ай бұрын
Best of luck!
Hi, could you make a video about minimum-cost perfect matching and different approaches to finding it?
excellent
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
Pls make a video on augmenting paths as well
Matchings: 00:00 Maximal matchings: 06:28 Maximum matchings: 08:35 Perfect matchings: 10:55
Please make a video on alternating path and augmenting path
Can you please do a detailed video on path partitioning of directed graphs?
Hi! Do you have any lesson regarding linear programming?
Excellent
@WrathofMath
2 жыл бұрын
Thank you!
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
@WrathofMath
3 жыл бұрын
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: kzread.info/dash/bejne/e5ymmMmGqJrIacY.html Proof: kzread.info/dash/bejne/Zqipj6ptdbaWls4.html
Perfect sir.
@WrathofMath
Жыл бұрын
Thank you!
thank you for your effort, and I have question; the alpha prime (G)=3?🐝💐
The ending was epic
@WrathofMath
2 жыл бұрын
Thank you! Here is a link to that full song: kzread.info/dash/bejne/gX92xrqIotOnYto.html
amazing
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
Awesome!
@WrathofMath
2 жыл бұрын
Thanks, Peiman! If you're looking for more graph theory, check out my playlist! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@peimanmohseni9239
2 жыл бұрын
@@WrathofMath Thanks a lot for making these videos. Would you mind adding one on Konig-Egervary theorem and its proof?
Can you give an idea about Augmenting and alternating path
Can you teach vizing's theorem please?
please do a video max matching min vertex cover theorem
Great video. Love your chess board!
@WrathofMath
3 жыл бұрын
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!
tnx man
@WrathofMath
5 ай бұрын
Glad to help!
Can you explain what “matching polynomials”?
"Thats a really good f" love it =)
@WrathofMath
2 жыл бұрын
Haha, thank you! Every time I rewatch this video I am impressed by that f!
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.
@user-qx8xr1sl2r
3 жыл бұрын
maybe you could read Concrete Mathematic by Knuth in chapter 7, it will help you a lot!
Could you explane "Rainbow numbers for matching"?
Thank you for the clear explanation of matchings. It did help to see an example that is not a bipartite graph.
12:00 Don't worry. I sometimes watch your video when I'm dropping my browns.
integer linear programming for matching would be useful.
i really forgot whatever i learned . Thanks
best on youtube
@WrathofMath
3 жыл бұрын
Thanks so much!
Is there a video for Adjacency matrix?
@WrathofMath
3 ай бұрын
kzread.info/dash/bejne/aXWcqqmpZ6jgips.html&pp=ygUQYWRoYWNlbmN5IG1hdHJpeA%3D%3D
@jarvisharleii
3 ай бұрын
@@WrathofMath ❤❤
Wow you're a mathematician, rapper, and guitar player! How long have you been playing guitar? What's your music background?
@WrathofMath
2 жыл бұрын
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?
@peifumo7416
2 жыл бұрын
@@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.
Does matching ( maximal, maximum , perfect) exist for graphs with self loops? That is if we consider the degree of the loop as 1 ?
@WrathofMath
2 жыл бұрын
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.
perfekt!
@WrathofMath
3 жыл бұрын
Thank you!
"That's a really good f" Same, man, same.
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?
@WrathofMath
4 жыл бұрын
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?
@Anteater23
4 жыл бұрын
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?
@WrathofMath
4 жыл бұрын
Exactly!
@Anteater23
4 жыл бұрын
Wrath of Math Thanks. The video was v helpful
@Anteater23
4 жыл бұрын
@@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
Please Explain Minimal Matching too.
@WrathofMath
3 жыл бұрын
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.
Please give explanation of graphs having 1-factors
@WrathofMath
3 жыл бұрын
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!
can you also comment on an Algorithm that finds the maximum Matching of a Graph? btw Thank you
Te amo calvo :)
Would be amazing if you taught my combinatorics lecture how to present charismatically so that students don’t get bored.
@WrathofMath
3 жыл бұрын
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! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Huh, practically identical to the notes/lecture my professor gave me. That's how you know a professor is worth their shit and the class is just hard - when youtube doesn't magically solve all your problems. I just need to connect the dots (well this phrase is a bit awkward in this context lol)
@WrathofMath
2 жыл бұрын
Thanks for watching, graph theory can indeed be hard! Let me know if you have any questions I can help clear up, and check out my playlist if you're looking for more graph theory videos that may help solve some of your problems: kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@Hi_Brien
2 жыл бұрын
@@WrathofMath I've been having a jolly old time going through your videos this morning. Right now I'm just struggling with applying Hall's theorem on more generalized problems. Every example I've found has restrictions that are a bit more obvious to me than tonight's problem. I have a X,Y-bigraph with |X|
bd ,why not matching
@WrathofMath
3 жыл бұрын
Thanks for watching and I am not sure what you mean. A matching is a set of edges which share no end vertices. So if we consider the set containing only the edge bd, as in the set { bd }, that is technically a matching because it doesn't contain any pair of edges that share an end vertex. Does that help?
@muthugowsalya8598
3 жыл бұрын
@@WrathofMath thanks ..