Matching
From Free net encyclopedia
- This article is about mathematical matchings. For other uses see matching (disambiguation).
In the mathematical discipline of graph theory a matching or edge independent set in a graph is a set of edges without common vertices.
Contents |
Definition
Given a graph G = (V,E) a matching M in G is a set of pairwise non-adjacent edges.
We say that a vertex is matched if it is incident to an edge in the matching. Otherwise the vertex is unmatched.
A maximum matching is a matching that is as big (has as many edges) as possible. There may be many maximum matchings.
An alternating path is a path in which the edges belong alternatively to the matching and not to the matching.
An augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.
A matching is maximum if and only if it does not contain any augmenting path.
The matching number of a graph is the size of a maximum matching.
A perfect matching is a matching which covers all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching.
Examples
- A complete bipartite graph Km,n has matching number equal to min(m,n).
Notes
Some people also allow graphs with an odd number of vertices to have a "perfect" matching. These matchings have exactly one unmatched vertex.
The marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.
Hopcroft and Karp proposed an algorithm for computing maximum matchings on bipartite graphs that runs in <math>O(\sqrt{n}m)</math> where n is the number of vertices and m is the number of edges.
There is a polynomial time algorithm (sometimes called the Hungarian algorithm) which, given a bipartite graph G, determines if G has a perfect matching and, if it has, finds a perfect matching. There is also a polynomial time algorithm to find a maximum matching in a graph that is not bipartite; it is due to Edmonds, is called the paths, trees, and flowers method, and uses bidirected edges.
A related problem is, given a graph G, to determine the number of perfect matchings in G. This problem is #P Complete. For bipartite graphs, it can be approximately solved in polynomial time. That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines, with high probability, the number of perfect matchings M within an error of at most εM.
Properties
- for a graph G with n vertices having no isolated vertex the matching number + edge covering number = n (Tibor Gallai 1959)
- a graph with n vertices and a perfect matching has a matching number of n/2
See also
References
- Gallai, Tibor. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.3: Maximum bipartite matching, pp.664–669.de:Paarung (Graphentheorie)
he:שידוך (תורת הגרפים) ja:マッチング (グラフ理論) pl:Skojarzenie (teoria grafów)