Bipartite matching

A matching in a bipartite graph is a set of edges with no shared endpoints. It pairs vertices from opposite parts without using any vertex more than once.

Augmenting path: A path that alternates between edges outside and inside a matching, starting and ending at unmatched vertices. Flipping its edges increases the matching by one pair.
Bipartite graph: A graph whose vertices can be divided into two sets so every edge joins vertices in opposite sets. Its two vertex sets are the sides that a matching pairs.
Assignment problem: An optimization problem that assigns distinct agents to tasks at minimum total cost. Ignoring costs leaves the question of whether a complete pairing exists.
Maximum matching: A matching with the largest possible number of edges in a graph. It is the principal optimization target, rather than merely any valid matching.
Berge's lemma: A matching is maximum exactly when no augmenting path exists. It gives the stopping condition behind augmenting-path algorithms.
Graph (discrete mathematics): A mathematical structure consisting of vertices joined by edges. A matching is a selected subset of a graph's edges.
Stable marriage problem: A matching problem with preferences on both sides, seeking an assignment with no blocking pair. It adds preference stability, a condition distinct from maximizing the number of pairs.
Maximal matching: A matching to which no edge can be added without sharing an endpoint. Maximality is local and does not guarantee the largest possible size.
Kuhn's algorithm: A depth-first augmenting-path algorithm for finding a maximum matching in a bipartite graph. It repeatedly reroutes existing pairs to match another vertex.
Vertex cover: A set of vertices that includes at least one endpoint of every edge in a graph. In bipartite graphs, its minimum size equals the maximum matching size.

Linked from 14 pages