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
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!
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 🙂
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!
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!
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!
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 :)
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 to hear it, thanks for watching! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
So glad it helped! Thanks for watching, and if you're looking for more graph theory be sure to check out my playlist: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Let me know if you have any video requests!
@8:30 maximal definition is little confusing, because in lattice algebra, there is always a unique maximum element which is greatest compared to all other elements. But in graph theory, there can be many maximal matchings.
Glad to help, thanks for watching! If you want more on matchings, check out my lessons on Hall's marriage theorem. ua-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html ua-cam.com/video/4tu-H4ES0fk/v-deo.html
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: ua-cam.com/video/Ihr6gMx7b9c/v-deo.html Proof: ua-cam.com/video/4tu-H4ES0fk/v-deo.html
Thank you! My playlist has a lot of proofs in it: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html A proof of Hall's Marriage theorem I believe follows this video in the playlist. Thanks for watching!
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
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.
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!
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
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.
So glad it helped, thanks for watching! If you're looking for more on graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Let me know if you ever have any video requests!
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
No problem, thanks for watching! If you're looking for more graph theory, be sure to check out my Graph Theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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.
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?
@@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
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.
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.
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.
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
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!
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!
Matchings: 00:00
Maximal matchings: 06:28
Maximum matchings: 08:35
Perfect matchings: 10:55
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!
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!
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!
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?
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!
Extremely helpful for my exam tomorrow, Thanks!
You have the gift of explanning. Thanks for you work
So glad to help, thanks for watching!
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 :)
me to encouraging friend: Oh no, i got an F
Encouraging Friend: 1:29
this gave a me a good chuckle
😆
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!
As someone who’s dabbled in making videos, this is really high quality. Great and thanks
Thanks a lot!
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!
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Beautifully explained with ample amount of examples to make concepts crystal clear. Love it!
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: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you have any video requests!
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!
Great ! I was looking for the topic "Maximum matching"
Glad it helped, thanks for watching!
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!
That augmented path Algo, I learnt from Dr. A.R. Ranadey, IIT BOMBAY, INDIA. He explained it so well
you are also good.
Really nice video! This deserves more upvotes!
Nice explanation...and the last brushing up was also needed...thanks for the video
@8:30 maximal definition is little confusing, because in lattice algebra, there is always a unique maximum element which is greatest compared to all other elements. But in graph theory, there can be many maximal matchings.
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.
ua-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html
ua-cam.com/video/4tu-H4ES0fk/v-deo.html
thank you very much tomorrow is my graph theory final exam and this vids is very helpful wish me luck
Best of luck!
Excellent explanation. Was a very useful primer to solve assignment problems.
That is the best explanation I have heard by far!
So glad to hear it! Thanks for watching!
Excellent video, great and clear explanation. Thank you for posting this.
I'm glad it was clear, thanks a lot for watching!
thx for the clear definition and explanation. You made an easy concept easy.
Glad it helped!
thank you very much! I understand it now. My slides were confusing.
So well explained, amazing!
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!
"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 👍
Very clear explanation. Thank you
You're welcome! Thanks for watching!
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: ua-cam.com/video/Ihr6gMx7b9c/v-deo.html
Proof: ua-cam.com/video/4tu-H4ES0fk/v-deo.html
Simple and clearer..Thank you
My pleasure!
12:00
Don't worry. I sometimes watch your video when I'm dropping my browns.
Really good explanation! It would be good to also do some formal proofs of all this stuf, but still a really good way of getting an intuition
Thank you! My playlist has a lot of proofs in it: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
A proof of Hall's Marriage theorem I believe follows this video in the playlist. Thanks for watching!
Well explained sir! well explained!
Thank you!
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!
you are doing a great job brother..love the way u explain it.
Thanks a lot!
good, clear explanation. keep them coming please.
Thank you, will do!
Holy crap this video is really good. Well-explained dude!
Thanks a lot!
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!
thank you sir for this lesson, it helps me a lot
Glad to hear it, thanks for watching!
Thanks bro.that's really great explanation
The ending was epic
Thank you! Here is a link to that full song: ua-cam.com/video/OKBdXOrpA2w/v-deo.html
Perfect sir. I really appreciate your efforts, very helpfull
Thank you for watching!
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
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.
Very nice explanation, thank you!
Glad it helped!
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!
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
great explanation!
I do my best! Thanks for watching and check out my graph theory playlist for more: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
"Thats a really good f" love it =)
Haha, thank you! Every time I rewatch this video I am impressed by that f!
loved the explanation, thank you :D
You're very welcome, thanks for watching!
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.
Thank you for the clear explanation of matchings. It did help to see an example that is not a bipartite graph.
I loved the way u sum it all
Thank you - I do my best! Matchings is a fun topic!
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any video requests!
Can you please do a detailed video on path partitioning of directed graphs?
Can you post a video on the proof for Tutte's Theorem?
This is amazing, thank you so much !
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Please make a video on alternating path and augmenting path
great video well explained.
Thank you!
best on youtube
Thanks so much!
Pls make a video on augmenting paths as well
Great explaination
Thank you, glad it helped!
Thank u sooo much man! Very clear explanation👌
My pleasure, so glad it was clear and thanks for watching!
thank you! very helpful.
Very good content !
Thank you, Jean!
It was clear. Thank you!
Glad to hear it! You're welcome and thanks for watching!
"That's a really good f"
Same, man, same.
i really forgot whatever i learned . Thanks
Hi, could you make a video about minimum-cost perfect matching and different approaches to finding it?
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Could you explane "Rainbow numbers for matching"?
Thanks! Subscribed.
Thanks for watching and subscribing!
Can you explain what “matching polynomials”?
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.
thank you for your effort, and I have question; the alpha prime (G)=3?🐝💐
Can you teach vizing's theorem please?
Hi! Do you have any lesson regarding linear programming?
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
Can you give an idea about Augmenting and alternating path
Thank you very much!
You're welcome!
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!
Last song 💓🙌
Thank you!
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.
please do a video max matching min vertex cover theorem
Is there a video for Adjacency matrix?
ua-cam.com/video/7AhHGp7EzZ8/v-deo.html&pp=ygUQYWRoYWNlbmN5IG1hdHJpeA%3D%3D
@@WrathofMath ❤❤
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!
integer linear programming for matching would be useful.
Perfect sir.
Thank you!
You are awesome!
Thank you!
Excellent
Thank you!
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.