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.
Finding a matching in a bipartite graph can be treated as a network flow problem.
A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M. The following figure shows examples of maximal matchings (red) in three graphs.
The following figure shows examples of maximum matchings in the same three graphs.
In the above figure, only part (b) shows a perfect matching.
If every vertex is unmatched by some near-perfect matching, then the graph is called factor-critical.
This inequality is tight: for example, if G is a path with 3 edges and 4 vertices, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.
A spectral characterization of the matching number of a graph is given by Hassani Monfared and Mallik as follows: Let
zeros, and (b) all real skew-symmetric matrices with graph
[6] Note that the (simple) graph of a real symmetric or skew-symmetric matrix
Let G be a graph and mk be the number of k-edge matchings.
A fundamental problem in combinatorial optimization is finding a maximum matching.
In an unweighted bipartite graph, the optimization problem is to find a maximum cardinality matching.
In a weighted bipartite graph, the optimization problem is to find a maximum-weight matching; a dual problem is to find a minimum-weight matching.
running time with the Dijkstra algorithm and Fibonacci heap.
A maximal matching can be found with a simple greedy algorithm.
Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set.
[9] Both problems can be approximated within factor 2 in polynomial time: simply find an arbitrary maximal matching M.[10] The number of matchings in a graph is known as the Hosoya index of the graph.
[11] It is also #P-complete to count perfect matchings, even in bipartite graphs, because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its biadjacency matrix.
However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.
[12] A remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm.
The number of perfect matchings in a complete graph Kn (with n even) is given by the double factorial (n − 1)!!.
[14] The number of perfect matchings in a graph is also known as the hafnian of its adjacency matrix.
Algorithms for this problem include: The problem of developing an online algorithm for matching was first considered by Richard M. Karp, Umesh Vazirani, and Vijay Vazirani in 1990.
[18] In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded.
This is a natural generalization of the secretary problem and has applications to online ad auctions.
The best online algorithm, for the unweighted maximization case with a random arrival model, attains a competitive ratio of 0.696.
[19] Kőnig's theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover.
Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.
Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.