Bipartite Matching

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: The stable match problem that we just looked at is one example of a bipartite matching problem. So the setup with a bipartite matching problem is you've got a simple graph. And the vertices are split into two groups, as in the stable matching problem, we can call them the girls and the boys, the G and the b.

So the definition of a bipartite graph is a graph where there are some vertices called the left vertices and a disjoint set of vertices called the right vertices. And every vertex is either left or right. And edges only go between a left vertex and a right vertex.

Now, in this case, the matching problem that we want to consider is that there is a specification that each girl is willing to be paired with certain boys, but not all of them. So we can specify that by adding edges where, if this is the first girl on the list, and she is willing to be paired with the second boy and the last boy. And that's what those two edges indicate. So edges are signaling compatibility constraints on matching up the girls and the boys.

And what we're trying to accomplish is getting all of the girls matched with a unique boy-- match each girl to a unique compatible boy. So there's an example of a match, where there is one highlighted magenta edge out of each girl. And they go to different boys. So formally, we want a bijection from the girls to the boys that follows edges.

Well, let's look at a case where I can't find a match. Suppose that that edge was missing. We used that edge in the match. But let's suppose it was not there. Let's get rid of it.

And what we find now is that this last girl no longer can be matched to this second boy, which is what we previously had. So let's try to find some other match. And there isn't any. And the reason is that if you look at this group of three girls on the left and you look at all of the boys on the right that they are collectively compatible with-- that is, one of these three girls at least is willing to be paired with one of the boys on the right-- there are only two boys that have to be shared among three girls.

And that is one example of what's called a bottleneck. So we have three girls. And collectively, they only like two boys. There just are not enough boys to go around for these girls. That proves that a match is not going to be possible.

So more generally, if you have a set S of girls on the left and you look at the image of S under the edge relation-- that is E of S, which is collectively the set of all of the boys that are compatible with one or more of the girls in S-- then whenever you have-- So we previously just had an example where S was 3 and E of S was 2. And because 3 was greater than 2-- because S was greater than E of S-- we were bottlenecked. And we couldn't possibly find a match.

And more generally, the definition of a bottleneck is that if you have a set where the size of S is greater than the size of the image of S, then that's called a bottleneck. And the first observation we can make is the bottleneck lemma says that a bottleneck is a set S of girls without enough boys. And if S is greater than E of S, that's called a bottleneck. And when there is one, no match is possible, obviously.

So this is a reason why there might not be a match, is that there is a bottleneck. Now, a rather deep theorem is conversely, if there are no bottlenecks, then in fact there is a match. This is known as Hall's theorem. It's not obvious, although we'll find an understandable proof of it. And that's what we're going to do in the next segment.

Free Downloads

Video


Caption

  • English-US (SRT)