Can we assign everyone a job? (maximum matchings) | Bipartite Matchings

Matching problems are ubiquitous in real life, like matching students to schools, drivers to passengers, airplanes to airports, etc.

Maximum cardinality bipartite matching is the simplest matching problem, but the results and theory are fundamental to more complex matching problems.

We go over a simple example throughout the whole video, where we try to find a way to assign everyone a job. Along the way, we learn about several fundamental theorems in graph theory, such as Hall's marriage theorem and Berge's theorem. A naive greedy approach to matching does not always give a maximum matching. But, using the concept of augmenting paths, we find that iteratively finding augmenting paths and updating our matching, does terminate in a maximum matching. This is also the basis for the Hungarian algorithm for weighted bipartite matchings.


Timestamps:
0:00 Intro
2:20 Hall's Theorem
4:19 Augmenting Paths and Berge's Theorem
7:21 Breadth-First Search to Find Augmenting Paths
9:15 Summary and Runtime

Music:

April by Kai Engel
https://freemusicarchive.org/music/Ka...

June by Kai Engel
https://freemusicarchive.org/music/Ka...

July by Kai Engel
https://freemusicarchive.org/music/Ka...

Remedy for Melancholy by Kai Engel
https://freemusicarchive.org/music/Ka...