Matching
|
|
This article is about mathematical matchings. For matching in the field of electronics, see: Impedance matching and Impedance bridging
In mathematical discipline of graph theory a matching or edge independent set for a graph is a set of edges without common vertices.
| Contents |
Definition
Given a graph G = (V,E) a matching M for G is a set of non-adjacent edges.
A maximum matching is the biggest matching possible.
The matching number for a graph is size of the 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 <math>G_{m,n}<math> has matching number <math>\min\lbrace m,n \rbrace<math>
Notes
Some definitions also allow graphs with an odd number of vertices to have a perfect matching. These 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.
There is a polynomial time algorithm (sometimes called Hungarian algorithm) which, given a 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.
A related problem is, given a graph G, 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 the number of perfect matchings M with error at most εM, with high probability.
Properties
- for a connected graph G with n vertices 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
- graphs with perfect matchings are 2-vertex colorable, that is they have a vertex chromatic number of 2
See also
References
- Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.de: Paarung (Graphentheorie)