An Algorithm for Bipartite Matching
In class, we learned about the bipartite matching problem, which involves a graph with vertices that can be split into two distinct subsets, such that every edge in the graph connects a graph in one subset to the other. Given this graph, a (maximum) bipartite matching is a set of edges, such that no two edges in this set share a vertex, and that every vertex has an edge. In other words, it is a one-to-one mapping from vertices in one subset to vertices in the other, using some of the edges in the graph. In class we found bipartite matchings by hand, but there are actually cool algorithms which can do this. For instance, see http://planetmath.org/encyclopedia/BipartiteMatching.html
The simplest algorithm to do this is to transform the graph into a network flow problem. A network flow problem is a problem where there is a graph with a source vertex, a sink vertex, and a bunch of other vertices and edges with maximum capacities. Network flow algorithms find the maximum number of “units” we can send through the edges of this graph from the source to the sink, without exceeding the maximum capacity on any edge. It may not seen obvious, but if we have an algorithm to solve the network flow problem, we can find a bipartite matching for any graph. All we need to do is create a source node which connects to every vertex in one subset, create a sink node which connects to every vertex in the other subset, and give every edge a maximum capacity of 1. Now we know a complete bipartite matching exists if the maximum flow in this new graph is equal to the number of vertices in each subset – because that means every vertex from the source is saturated. And thankfully, there are algorithms to solve the network flow problem – without going into too much detail, what they do is repeatedly search for paths from the source to the sink, including paths which remove flow from some edges, and send units of flow along these paths until no more paths exist.
I think this is relevant because it shows an algorithmic way to do something that we learned about in class. While in class we tried to find bipartite matchings manually, by inspecting the graphs, it’s cool that there are ways to do this using a computer. And this is extremely useful – for the many applications of bipartite matching that we learned about in class, such as for creating a mapping from teachers to courses, or from courses to classrooms. Of course it would be impractical for someone to manually find a bipartite matching from teachers to courses, but because of algorithms like this one it can all be automated.