Bipartite Matching¶

Definition¶

A bipartite matching pairs entities from two distinct groups, with each selected pair containing one member of each group and no entity used in more than one pair. A complete one-to-one assignment between equally sized groups is a perfect bipartite matching.

Interpretation¶

A bipartite matching pairs members of one group with members of another, such as workers with jobs, where every pair crosses between the groups and nobody is used twice. The question is how many pairs can be formed at once, or which complete pairing is cheapest.

Four workers and three jobs with grey edges for allowed pairs and green edges for a matching of three pairs; worker 4 stays unmatched.

The grey edges are the allowed worker-job pairs and the green edges form a matching: no two green edges share an endpoint. With three jobs, no matching can have more than three edges, so this one is as large as possible, even though worker $4$ stays unmatched. Other largest matchings exist, for example $4$ – $a$ , $1$ – $b$ , $3$ – $c$ .

In network terms, entities are vertices, allowed pairs are edges, and every edge joins the two groups. A matching is perfect when it covers every vertex on both sides, which requires equally many vertices in the two groups. A matching to which no edge can be added is not necessarily largest: in the figure, $1$ – $b$ and $4$ – $c$ block every remaining edge, yet this matching has only two pairs.

The assignment problem asks for a cheapest perfect matching, which the Hungarian algorithm finds using this bipartite structure. A largest matching can be found as a maximum flow. The odd-vertex pairing of the Chinese postman problem is also a matching, but within one group of vertices, so it is not bipartite.

Key Results¶

Agents and tasks form the two groups in an assignment problem.
A matching need not use every entity unless completeness is required.
Maximum zero-cost matching can be represented as a unit-capacity flow problem.

Examples¶

Grey edges are allowed pairs and green edges form the matching. It contains $|M|=3$ pairs, equal to the number of jobs, so no larger matching is possible; the fourth worker remains unmatched. A perfect matching would cover every vertex on both sides and requires equal group sizes.

A machine-job pair connects the machine group to the job group.
The CPP odd-vertex pairing is nonbipartite because all paired vertices belong to one common set.

Prerequisites¶

Network

Sources¶

OR Modelling · Week 5

Aliases: matching in a bipartite graph

Last updated: 20 October 2026 03:02