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 and we partition the vertices into two sets, and , of the same colour. We may then represent the graph with a simplified adjacency matrix with rows and columns containing a where an edge joins the corresponding vertices and a where there is no edge.
We say that two 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 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
where a indicates an edge in the matching. Note that all the starred s are line-independent.
A complete matching on a bipartite graph is one that saturates all of the vertices in .
Systems of distinct representatives
A system of distinct representatives is equivalent to a maximal matching on some bipartite graph. Let and be the two sets of vertices in the graph with . Consider the set , which includes the neighborhood of every vertex in . An SDR for this set will be a unique choice of an vertex in for each vertex in . There must be an edge joining these vertices; the set of all such edges forms a matching.
Consider the sets
One SDR for these sets is
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 . As usual, we consider the two sets of vertices and . Replace every edge in the graph with a directed arc from to of capacity , where is some large integer.
Invent two new vertices: the source and the sink. Add a directed arc of capacity from the source to each vertex in . Likewise, add a directed arc of capacity from each vertex in 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 . 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 |