Matching (graph theory)

For comparisons of two graphs, see Graph matching.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching.

Finding a largest matching in a bipartite graph can be treated as a network flow problem. Finding a largest matching in a general graph is much more difficult; it can be done using Edmonds' blossom algorithm.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.