# bipartite matching

## Matrix form

Suppose we have a bipartite graph $G$ and we partition   the vertices into two sets, $V_{1}$ and $V_{2}$, of the same colour. We may then represent the graph with a simplified adjacency matrix with $|V_{1}|$ rows and $|V_{2}|$ columns containing a $1$ where an edge joins the corresponding vertices and a $0$ where there is no edge.

We say that two $1$s in the matrix are line-independent if they are not in the same row or column. Then a matching on the graph with be a subset of the $1$s in the matrix that are all line-independent.

For example, consider this bipartite graph (the thickened edges are a matching): The graph could be represented as the matrix

 $\begin{pmatrix}1*&1&0&1&0\\ 1&0&1*&0&0\\ 0&0&1&0&1*\\ 0&1*&1&0&1\\ \end{pmatrix}$

where a $1*$ indicates an edge in the matching. Note that all the starred $1$s are line-independent.

A complete matching on a bipartite graph $G(V_{1},V_{2},E)$ is one that saturates all of the vertices in $V_{1}$.

## Systems of distinct representatives

A system of distinct representatives is equivalent      to a maximal matching on some bipartite graph. Let $V_{1}$ and $V_{2}$ be the two sets of vertices in the graph with $|V_{1}|\leq|V_{2}|$. Consider the set $\{v\in V_{1}:\Gamma(v)\}$, which includes the neighborhood  of every vertex in $V_{1}$. An SDR for this set will be a unique choice of an vertex in $V_{2}$ for each vertex in $V_{1}$. There must be an edge joining these vertices; the set of all such edges forms a matching.

Consider the sets

 $\displaystyle S_{1}$ $\displaystyle=$ $\displaystyle\{A,B,D\}$ $\displaystyle S_{2}$ $\displaystyle=$ $\displaystyle\{A,C\}$ $\displaystyle S_{3}$ $\displaystyle=$ $\displaystyle\{C,E\}$ $\displaystyle S_{4}$ $\displaystyle=$ $\displaystyle\{B,C,E\}$

One SDR for these sets is

 $\displaystyle A$ $\displaystyle\in$ $\displaystyle S_{1}$ $\displaystyle C$ $\displaystyle\in$ $\displaystyle S_{2}$ $\displaystyle E$ $\displaystyle\in$ $\displaystyle S_{3}$ $\displaystyle B$ $\displaystyle\in$ $\displaystyle S_{4}$

Note that this is the same matching on the graph shown above.

## Finding Bipartite Matchings

Start with a bipartite graph $G$. As usual, we consider the two sets of vertices $V_{1}$ and $V_{2}$. Replace every edge in the graph with a directed arc from $V_{1}$ to $V_{2}$ of capacity $L$, where $L$ is some large integer.

Invent two new vertices: the source and the sink. Add a directed arc of capacity $1$ from the source to each vertex in $V_{1}$. Likewise, add a directed arc of capacity $1$ from each vertex in $V_{2}$ to the sink.

Now find the maximum flow from the source to the sink. The total weight of this flow will be the of the maximum matching on $G$. Similarly, the set of edges with non-zero flow will constitute a matching.

There also exist algorithms specifically for finding bipartite matchings (http://planetmath.org/MaximalBipartiteMatchingAlgorithm) that avoid the overhead of setting up a weighted digraph suitable for network flow.

Title bipartite matching BipartiteMatching 2013-03-22 12:40:08 2013-03-22 12:40:08 mathcam (2727) mathcam (2727) 7 mathcam (2727) Definition msc 05C70 Saturate complete matching