Matching

← Back to Graph Theory

A set of edges with no common vertices. A maximum matching has the most edges possible. In bipartite graphs, maximum matching can be found in polynomial time (Hopcroft-Karp algorithm). Applications in job assignment, resource allocation, and network design.

mathematics-for-cs discrete-mathematics graph-theory matching