bipartite matching


A matching on a bipartite graphMathworldPlanetmath is called a bipartite matching. Bipartite matchings have many interesting properties.

Matrix form

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

We say that two 1s 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 1s 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

(1*1010101*0000101*01*101)

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

A complete matching on a bipartite graph G(V1,V2,E) is one that saturates all of the vertices in V1.

Systems of distinct representatives

A system of distinct representatives is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to a maximal matching on some bipartite graph. Let V1 and V2 be the two sets of vertices in the graph with |V1||V2|. Consider the set {vV1:Γ(v)}, which includes the neighborhoodMathworldPlanetmath of every vertex in V1. An SDR for this set will be a unique choice of an vertex in V2 for each vertex in V1. There must be an edge joining these vertices; the set of all such edges forms a matching.

Consider the sets

S1 = {A,B,D}
S2 = {A,C}
S3 = {C,E}
S4 = {B,C,E}

One SDR for these sets is

A S1
C S2
E S3
B S4

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 flowMathworldPlanetmath algorithmMathworldPlanetmath. Before using it, however, we must modify the graph.

Start with a bipartite graph G. As usual, we consider the two sets of vertices V1 and V2. Replace every edge in the graph with a directed arc from V1 to V2 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 V1. Likewise, add a directed arc of capacity 1 from each vertex in V2 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