PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (236)
Orphanage
Unclass'd (1)
Unproven (540)
Corrections (46)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Copyright
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
bipartite matching (Definition)

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 $ \vert V_1\vert$ rows and $ \vert V_2\vert$ 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):

\includegraphics[scale=1.0]{bipartite3.eps}

The graph could be represented as the matrix

$\displaystyle \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 $ \vert V_1\vert \leq \vert V_2\vert$. 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 that avoid the overhead of setting up a weighted digraph suitable for network flow.



"bipartite matching" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:

See Also: saturate

Also defines:  complete matching
Log in to rate this entry.
(view current ratings)

Cross-references: weighted digraph, weight, maximum flow, sink, source, integer, capacity, arc, algorithm, network flow, neighborhood, maximal matching, equivalent, system of distinct representatives, saturates, subset, matrix, joins, edge, columns, rows, adjacency matrix, graph, represent, colour, vertices, partition, properties, bipartite graph, matching
There are 3 references to this entry.

This is version 4 of bipartite matching, born on 2002-05-26, modified 2003-11-06.
Object id is 2942, canonical name is BipartiteMatching.
Accessed 25058 times total.

Classification:
AMS MSC: 05C70 (Combinatorics :: Graph theory :: Factorization, matching, covering and packing)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)