# bipartite matching

A matching on a bipartite graph^{} is called a *bipartite matching*. Bipartite matchings have many interesting properties.

## 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

$$\left(\begin{array}{ccccc}\hfill 1*\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1*\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1*\hfill \\ \hfill 0\hfill & \hfill 1*\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$$ |

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}|\le |{V}_{2}|$. Consider the set $\{v\in {V}_{1}:\mathrm{\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

${S}_{1}$ | $=$ | $\mathrm{\{}A,B,D\}$ | ||

${S}_{2}$ | $=$ | $\mathrm{\{}A,C\}$ | ||

${S}_{3}$ | $=$ | $\mathrm{\{}C,E\}$ | ||

${S}_{4}$ | $=$ | $\mathrm{\{}B,C,E\}$ |

One SDR for these sets is

$A$ | $\in $ | ${S}_{1}$ | ||

$C$ | $\in $ | ${S}_{2}$ | ||

$E$ | $\in $ | ${S}_{3}$ | ||

$B$ | $\in $ | ${S}_{4}$ |

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

## Finding Bipartite Matchings

One method for finding maximal bipartite matchings involves using a network flow^{} algorithm^{}. Before using it, however, we must modify the graph.

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 |
---|---|

Canonical name | BipartiteMatching |

Date of creation | 2013-03-22 12:40:08 |

Last modified on | 2013-03-22 12:40:08 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 7 |

Author | mathcam (2727) |

Entry type | Definition |

Classification | msc 05C70 |

Related topic | Saturate |

Defines | complete matching |