[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

A graph (see GraphTheory) is a bipartite graph if its vertex set can be written as X∪Y and every edge is an element of X×Y. Alternatively, a graph is bipartite if it can be 2-colored (the vertices in the two color sets give X and Y). Yet another criterion is that a graph is bipartite if and only if it does not contain a cycle with an odd number of edges.

1. Bipartite matching

Bipartite graphs are often used to model assignment problems, where the vertices of the left-hand side X represent things that need to be assigned, the vertices of the right-hand side Y represent places to put them, and an edge indicates compatibility. A complete bipartite matching is a subset of the edges of a bipartite graph such that every node is the endpoint of exactly one edge: such a matching corresponds to an assignment that assigns every object and fills every niche (it also implies |X|=|Y|). This is a special case of a matching, which is a subset of the edges of an arbitrary graph that hits each vertex at most once, and a maximal matching, a matching that is maximal under inclusion---i.e., one where you can't add any more edges without making it no longer be a matching.

Because of the application to assignment, much is known about bipartite matching. In particular, there is a characterization of exactly which bipartite graphs have a complete matching.

Hall's Theorem
Let G = (X∪Y, E) be a bipartite graph, and for each A⊆X define ∂A = {y∈Y: ∃x∈A such that xy∈E}. Then G has a complete matching if and only if |∂A| ≥ |A| for all A⊆X.

If there is some A with |∂A| < |A| we are clearly in trouble, so the main thing is to show that |∂A| ≥ |A| is sufficient. We do so by showing that when the condition holds, any matching M with |M| < |X| can be extended to a matching of size |M|+1. The procedure is as follows: Let x1 be an unmatched node in M and let X1 = {x1}. We will construct two sequences of nodes x1, x2 ..., xk and y1, y2 ..., yk such that yi is matched to xi+1 when i < k, yk is unmatched, and yi is adjacent to at least one node xj with j ≤ i. The construction proceeds as follows: given x1..xi and y1..yi-1 (i = 1 is the special case where we start with just x1 and no y's), we have |∂{x1...xi}| ≥ i > |{y1..yi-1}|. So there is at least one node in ∂{x1...xi} - {y1..yi-1}; pick that node and call it yi. If yi is unmatched, we are done. Otherwise, let xi+1 be yi's match in M and repeat. Now we have that each yi is adjacent to some xj with j ≤ i, and that that xj is either x1 or is matched with yj-1. So working backwards from yk we construct a sequence of nodes yk = y'mx'my'm-1x'm-1...y'1x'1 = x1 where each y'm is adjacent to x'm but not matched to it in M and each y' or x' except yk and x1 is matched in M (such a sequence is called an augmenting path. So by deleting all of the edges in M between some y' and x' and replacing them with edges between y'i and x'i for each i, we remove m-1 edges and add m, increasing the size of the matching by 1.

A useful corollary of Hall's Theorem is that even if there is no complete matching, there is still a matching that matches all but maxA |A|-|∂A| nodes in X. The essential idea is that we can make Hall's condition hold by adding exactly that many new nodes to Y that can be matched with any node in X. The nodes that are matched with the new nodes in the resulting complete matching become the unmatched losers in the original graph.


2014-06-17 11:57