Unweighted Bipartite Matching | Network Flow | Graph Theory
ฝัง
- เผยแพร่เมื่อ 11 ก.ค. 2024
- What is and how to solve the unweighted bipartite graph matching problem
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on TH-cam:
www.udemy.com/course/graph-th...
Next video: • Bipartite Matching | M...
Previous video: • Max Flow Ford Fulkerso...
Algorithms repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/Algor...
Personal website:
www.williamfiset.com
Audio intro/outro composed by Richard Saney (rnsaney@gmail.com)
![[FULL EP.01] LOL: Last One Laughing Thailand Thailand หัวเราะทีหลังปังกว่า | Prime Thailand](http://i.ytimg.com/vi/t4KunBRKn3s/mqdefault.jpg)
![USAB Showcase: CANADA vs USA [OFFICIAL STREAM]](http://i.ytimg.com/vi/m9Cz3xsdDgc/mqdefault.jpg)
Woah. My brain just expanded a little.
Cuz he's basically explaining how your brain works
Thank you! This is extremely helpful. I was going to spend the next couple of days learning about Max flow and Bipartite matching; never could've imagined learning so much in less than an hour!
Thanks so much for all the series ... it's amazing. And how you link every piece together is really clear.
Awesome and well made. Worth spreading more.
Absolutely amazing.!
I'm having a course of Algorithms and Datastructures atm, and your videos are extremely helpful, thank you so much!
Thank you !!! So well made ! :)
Your videos are awesome. Thanks a lot :)
Great video! Thank you so much!
Thank you this was extremely helpful!
Keep it up, good work!
Thanks! This really helped me with foobar!
"Thank you so much for watching this video". No, THANK YOU for making these wonderful tutorials, amazed by this one.
Excellent explanation Sir. Thank you
This is the best video on the internet
this is so well explained
Very good explanation.
Awesome ! Thank you !
This wo so good! Thanks.
thank you for making the video :)
Great video!
excellent!
Enlightened 😌
Wow Thanks so much
Awesome!! Now I got it, cheers :D
I tried to go to your website, however it is down :(
Sir thanks for sharing the lesson, I have a question how can I limit the matchers dynamically, meaning if I want to match stock buyers to brokers each buyer have a volume ask N and a number x of brokers he's willing to work with, how this can be modeled?
Genius!
Could you try and explain the edmond Blossom algorithm for unweighted graphs?
Hi William, Is bipartite graph a connected graph ? In a graph of n independent nodes with no edges at all, we can color them with only 1 color.
You are awesome
Thx
Great video, but if we do greedy approach based on count of books each guy wants and start with minimum, we can solve it easily it O(n^2)?
Hey William Fiset :
@4:05 -- "weighted, directed, non-bipartite graph" -- min cost perfect match
I've implemented the dynamic programming solution for this
Felt nice :)
I'd to implement this as part of solving the Christofides algo that provides "approximate polynomial solution" to the "exponential" Traveling Salesman Problem
Please write your thoughts on this, if any
Madhukiran
From 2:50, So when are we going to poke around other boxes? Eagerly waiting for those.
GOOD ONE
excellent one
Ok but what do you in a certain scenario(where all capacities are 0,1) with the 2nd person(top to bottom) and the 4th person, they both lead to book 3 but book 3 should only be assigned to the 4th right. Well, if you were to traverse the algorithm using a DFS it would start at the 1st person then go to the 2nd book and augment, and then to the 2nd person it would skip the 2nd book since capacity == 0 and would go down to the 3rd book and augment that entire path. However, the 4th person needs to be assigned to the third book but the capacity of the book is already filled. You could think of removing the flow from that line and set the edge from 2nd person to 3rd book to visited, so that it won't visit it again and on next iteration it would skip to the 4th book, and the 4th person can be assigned the book. But I could only see a case where it can be possible to set a new flow path from the 4th person to the 3rd after a For loop break where the conditional is that an edge needs to have a capacity >0 and not be visited. However, even if there was some logic after a for loop break to reset a path, that logic would apply to every person since eventually they won't have valid edges too.
Could someone help me even a little with this, because it's really preventing me from seeing how the case with (0,1) capacity edges will work in code, or maybe I should go look at more flow algorithms.
I've the same doubt. Based on my understanding, second person (from the bottom) will not have any book assigned to it when max capacity is 1 and last person will be assigned to the 4th book not the 5th book.
Did you understand as to where are we making a mistake? Do reply if you figure out.
Thanks!
Rachit Singh Yeah I guess it would be that way, maybe the video was really just a pure visual tutorial to give some general knowledge on the idea of the topic, which perhaps works completely differently in code.
. I've watched the graph theory algorithms video on FreeCodeCamp and there was a video with the Ford Fulkersons flow algorithm, and in this video William stated that this should work with any flow algorithm but technically, when you compare how the computer chooses what edges go to which and how the DFS searched nodes, the Ford Fulkerson would not work here unless there was a way to slightly modify it so that the 4th could be reassigned to the third book, which I cannot see how that can be done in an effective way. If we augment the flow on the condition that any edge's capacity is 1 then that would automatically set the 2nd person book assignment to the 3rd book, which is what got me confused. However, it could work with a book with a capacity higher with 1, everyone could get a book using the flow algorithm I mentioned efficiently.
really great videos, but I recommend watching them at 1.5x playback speed :D
Nice but bit difficult for a beginner
If I watched this before my assignment would have been much easier