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

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

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