Maximum Bipartite Matching

A maximum matching is a Matching of maximum cardinality, that is, a matching $M$ such that for any matching $M^{\prime }$, we have $|M|\ge |M^{\prime }|$.

Converting to a Maximum Flow Problem.

This can be done by defining the corresponding Flow Network $G^{\prime }=(V^{\prime },E^{\prime })$ for the bipartite graph $G$.

This can be done by letting the source $s$ and sink $t$ be new vertices not in $V$, and we let $$\begin{gathered} V^{\prime }=V\cup \\ s,t \end{gathered}$$.

If the vertex partition of $G$ is $V=L\cup R$, the directed edges of $G^{\prime }$ are the edges of $E$, directed from $L$ to $R$, along with $|V|$ new directed edges defined by

$$\begin{gathered} E^{\prime }= \\ (s,u):u\in L \\ \cup \\ (u,v):(u,v)\in E \\ \cup \\ (v,t):v\in R \\ . \end{gathered}$$

Finally we assign unit capacity to each edge in $E^{\prime }$.

Examples

A matching with cardinality 2

A maximum matching with cardinality 3

The bipartite graph converted to a flow network

The shades edges have a flow of 1 and the other edges have no flow. This graph has been solved as a Maximum Flow Problem and have the same solution as the maximum matching above.